Question:
Let the set $S$ be defined recursively as follows:
Basis Step: $(0,0,2)\in S$
Recursive Step: If $(a,b,c)\in S$, then $(a+1,b+1,c)\in S$ and $(a+1,b,c+1) \in S$
Use structural induction to prove that $a+b+c$ is even when $(a,b,c) ∈ S$.
Thanks
Let $S_0=\bigl\{(0,0,2)\bigr\}$ and for each $n\in\mathbb N$, let $S_n$ be the union of $S_{n-1}$ with the set$$\{a+1,b+1,c)\,|\,(a,b,c)\in S_{n-1}\}\cup\{(a+1,b,c+1)\,|\,(a,b,c)\in S_{n-1}\}.$$Then $S=\bigcup_{n\in\mathbb{Z}^+}S_n$. I will prove by induction that $\bigl(\forall(a,b,c)\in S_n\bigr):a+b+c$ is even.
If $n=0$, this is trivial. Pick $n\in\mathbb{N}$ and suppose that $\bigl(\forall(a,b,c)\in S_{n-1}\bigr):a+b+c$ is even. Let $(a,b,c)\in S_n$. Then there is a $(a',b',c')\in S_{n-1}$ such that $a=a'+1$, $b=b'+1$ and $c=c'$ or that $a=a'+1$, $b=b'$ and $c=c'+1$. Furthermore, since $(a',b',c')\in S_{n-1}$, $a'+b'+c'$ is even. But $a+b+c=a'+b'+c'+2$, and therefore it is even too.
It suffices to map the parity property to the set definition.
$$(0,0,2)\in S\to \text{even}(0+0+2)=\text{true}$$
$$(a,b,c)\in S\implies (a+1,b+1,c)\in S\to \text{even}(a+1+b+1+c)=\text{even}(a+b+c)$$
$$(a,b,c)\in S\implies (a+1,b,c+1)\in S\to \text{even}(a+1+b+c+1)=\text{even}(a+b+c)$$
So any element of $S$ that is built from these rules has an even sum.
Basis: 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.
Thanks
– Ravnesh Kumar Oct 23 '17 at 12:47