Prove usingStructural Induction

[SaasuKe]

Homework Statement

[/B]
Let the set S be defined recursively as follows:

Basis Step: (0, 0, 2) ∈ S
Recursive Step: If (a, b, c) ∈ S, then (a + 1, b + 1, c) ∈ S and (a+1, b, c+1) ∈ S
Use structural induction to prove that a + b + c is even when (a, b, c) ∈ S

The Attempt at a Solution

Basis[/B]: 0 + 0 + 2 = 2 = 2 ∗ 1
2 is even, therefore, base case holds
Inductive: Assume w, x, y, z ∈ S and w = 2k, where k is any integer
Now, (x + 1) +(y + 1) + z = w

I know that we have to prove the recursive step here but I'm not quite sure how to do so. Any suggestions/hints?

Thanks

 

[stevendaryl]

Homework Statement

[/B]
Let the set S be defined recursively as follows:

Basis Step: (0, 0, 2) ∈ S
Recursive Step: If (a, b, c) ∈ S, then (a + 1, b + 1, c) ∈ S and (a+1, b, c+1) ∈ S
Use structural induction to prove that a + b + c is even when (a, b, c) ∈ S

The Attempt at a Solution

Basis[/B]: 0 + 0 + 2 = 2 = 2 ∗ 1
2 is even, therefore, base case holds
Inductive: Assume w, x, y, z ∈ S and w = 2k, where k is any integer
Now, (x + 1) +(y + 1) + z = w

I know that we have to prove the recursive step here but I'm not quite sure how to do so. Any suggestions/hints?

Thanks

The idea behind structural induction is that you imagine the set S being built up in stages, where each stage except the first is built using previous stages. Then to prove that all elements have a certain property, it's enough to know that

1. All elements in the initial stage have that property.
   
2. If all the elements created by one stage have the property, then any elements created at the next stage will also have that property.

There's actually a constraint on the type of properties that can be used: They have to be a property such that, if an element has that property at one stage, it must have that property at later stages. That's certainly true for the property of (x,y,z) being such that x+y+z is even.

So the inductive step is:

Assume that all elements of the form (x,y,z) that have been put into S at or before a certain stage have the property that x+y+z is even.
Prove that any new element added at the next stage must have that property.

So the only new elements that can be added at the next stage are:

• (x+1, y+1, z) where (x,y,z) is an existing element
• (x+1, y, z+1) where (x,y,z) is an existing element

So you just have to prove the two implications:

• If (x,y,z) has the property, then so does (x+1, y+1, z)
• If (x,y,z) has the property, then so does (x+1, y, z+1)

 

[SaasuKe]

The idea behind structural induction is that you imagine the set S being built up in stages, where each stage except the first is built using previous stages. Then to prove that all elements have a certain property, it's enough to know that

1. All elements in the initial stage have that property.
   
2. If all the elements created by one stage have the property, then any elements created at the next stage will also have that property.

There's actually a constraint on the type of properties that can be used: They have to be a property such that, if an element has that property at one stage, it must have that property at later stages. That's certainly true for the property of (x,y,z) being such that x+y+z is even.

So the inductive step is:

Assume that all elements of the form (x,y,z) that have been put into S at or before a certain stage have the property that x+y+z is even.
Prove that any new element added at the next stage must have that property.

So the only new elements that can be added at the next stage are:

• (x+1, y+1, z) where (x,y,z) is an existing element
• (x+1, y, z+1) where (x,y,z) is an existing element

So you just have to prove the two implications:

• If (x,y,z) has the property, then so does (x+1, y+1, z)
• If (x,y,z) has the property, then so does (x+1, y, z+1)