Recursive induction

Question

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

Answer 1

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.

Answer 2

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.