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

Printable View

- Sep 20th 2013, 01:02 PMhezhiweitianinduction 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 PMPlatoRe: induction proof help.
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 PMhezhiweitianRe: induction proof help.
- Sep 20th 2013, 02:36 PMPlatoRe: induction proof help.
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 PMhezhiweitianRe: induction proof help.