induction proof help.

• Sep 20th 2013, 01:02 PM
hezhiweitian
induction proof help.
Attachment 29211I really stuck on the induction step , my TA suggest me to set cases for even quantity of P(n) and odd quantity of P(n) and start from there.Attachment 29212 here is my work so far
• Sep 20th 2013, 01:36 PM
Plato
Re: induction proof help.
Quote:

Originally Posted by hezhiweitian
Attachment 29211I really stuck on the induction step , my TA suggest me to set cases for even quantity of P(n) and odd quantity of P(n) and start from there.

Let $S_n=\{1,2,\cdots,n\}$ then $S_n$ contains $\left\lfloor {\frac{{n}}{2}} \right\rfloor$ even numbers.

Hence $\math{P}(S_n)$ contains ${2^{\left\lfloor {\frac{n}{2}} \right\rfloor }}$ sets with no odd numbers.
• Sep 20th 2013, 02:16 PM
hezhiweitian
Re: induction proof help.
Quote:

Originally Posted by Plato
Let $S_n=\{1,2,\cdots,n\}$ then $S_n$ contains $\left\lfloor {\frac{{n}}{2}} \right\rfloor$ even numbers.

Hence $\math{P}(S_n)$ contains ${2^{\left\lfloor {\frac{n}{2}} \right\rfloor }}$ sets with no odd numbers.

i understand the logical idea behind this , however I couldn't translate it into a formal induction proof .
• Sep 20th 2013, 02:36 PM
Plato
Re: induction proof help.
Quote:

Originally Posted by hezhiweitian
i understand the logical idea behind this , however I couldn't translate it into a formal induction proof .

Oh, come on.
Use induction to prove $(S_n)$ contains ${\left\lfloor {\frac{n}{2}} \right\rfloor }}$ even numbers.

That is true for $S_1$: no even numbers.

Suppose that $(S_K)$ contains ${\left\lfloor {\frac{K}{2}} \right\rfloor }}$ even numbers.

Now $(S_{K+1})=S_K\cup\{K+1\}$. RIGHT?

If $K+1$ is odd then $(S_{K+1})$ contains just as many even numbers as $S_K$. WHY?

If $K+1$ is even then $(S_{K+1})$ contains one more even number than $S_K$.
Note that if $K+1$ is even then $\left\lfloor {\frac{{K + 1}}{2}} \right\rfloor = \left\lfloor {\frac{K}{2}} \right\rfloor + 1$

Can you finish?
• Sep 20th 2013, 02:42 PM
hezhiweitian
Re: induction proof help.
Quote:

Originally Posted by Plato
Oh, come on.
Use induction to prove $(S_n)$ contains ${\left\lfloor {\frac{n}{2}} \right\rfloor }}$ even numbers.

That is true for $S_1$: no even numbers.

Suppose that $(S_K)$ contains ${\left\lfloor {\frac{K}{2}} \right\rfloor }}$ even numbers.

Now $(S_{K+1})=S_K\cup\{K+1\}$. RIGHT?

If $K+1$ is odd then $(S_{K+1})$ contains just as many even numbers as $S_K$. WHY?

If $K+1$ is even then $(S_{K+1})$ contains one more even number than $S_K$.
Note that if $K+1$ is even then $\left\lfloor {\frac{{K + 1}}{2}} \right\rfloor = \left\lfloor {\frac{K}{2}} \right\rfloor + 1$

Can you finish?

Thank you very much