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$
  • $\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$ – Ravnesh Kumar Oct 23 '17 at 12:47
  • $\begingroup$ If $a+b+c$ is even then so is $a+b+c+2$ $\endgroup$ – jonsno Oct 23 '17 at 13:08
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.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\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.