2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ This is my attempt: 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 $\endgroup$ Oct 23, 2017 at 12:47
  • $\begingroup$ If $a+b+c$ is even then so is $a+b+c+2$ $\endgroup$
    – jonsno
    Oct 23, 2017 at 13:08

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.