1. ## induction proof help.

I 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. here is my work so far

2. ## Re: induction proof help.

Originally Posted by hezhiweitian
I 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.

3. ## Re: induction proof help.

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 .

4. ## Re: induction proof help.

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?

5. ## Re: induction proof help.

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