# 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 $\displaystyle S_n=\{1,2,\cdots,n\}$ then $\displaystyle S_n$ contains $\displaystyle \left\lfloor {\frac{{n}}{2}} \right\rfloor$ even numbers.

Hence $\displaystyle \math{P}(S_n)$ contains $\displaystyle {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 $\displaystyle S_n=\{1,2,\cdots,n\}$ then $\displaystyle S_n$ contains $\displaystyle \left\lfloor {\frac{{n}}{2}} \right\rfloor$ even numbers.

Hence $\displaystyle \math{P}(S_n)$ contains $\displaystyle {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 $\displaystyle (S_n)$ contains $\displaystyle {\left\lfloor {\frac{n}{2}} \right\rfloor }}$ even numbers.

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

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

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

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

If $\displaystyle K+1$ is even then $\displaystyle (S_{K+1})$ contains one more even number than $\displaystyle S_K$.
Note that if $\displaystyle K+1$ is even then $\displaystyle \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 $\displaystyle (S_n)$ contains $\displaystyle {\left\lfloor {\frac{n}{2}} \right\rfloor }}$ even numbers.

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

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

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

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

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

Can you finish?

Thank you very much