# Basic Proof By Induction, Assistance Required

With the following question. Is it better to start the proof by proving it for n=0, n=1 or both? Once I've done that, I prove it for n=p where p is any integer equal to or greater than 0. For the third part I prove it for n=p+1. It's easier to prove it for n=p+1 once I have proved it already for n=1, am I correct? All help would be appreciated...

• I think you're really confused. Your aim is to prove it for p, where p is any integer greater than 0. If you did it, then you're done. Making and induction has three steps: 1. Prove it for the first n that the proposition should satisfy. In this example, n=0. 2. Assume that the proposition is true for n=m. 3. Using the assumption you've made in step 2, prove that proposition is true for n=m+1. You're done, as you proved the proposition for the first number, and proved that sequent of every number that satisfies the proposition, also satisfies the proposition. – Zafer Sernikli Oct 23 '13 at 13:35

If $$(1+x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k$$ then $$(1+x)^{n+1}=(1+x)\sum_{k=0}^{n}\binom{n}{k}x^k=$$ $$=\sum_{k=0}^{n}\binom{n}{k}x^k+x\sum_{k=0}^{n}\binom{n}{k}x^k$$ $$=\sum_{k=0}^{n}\binom{n}{k}x^k+\sum_{k=0}^{n}\binom{n}{k}x^{k+1}=$$ $$=\sum_{k=0}^{n}\binom{n}{k}x^k+\sum_{k=1}^{n+1}\binom{n}{k-1}x^{k}=$$ $$=\sum_{k=0}^{n+1}\binom{n}{k}x^k+\sum_{k=0}^{n+1}\binom{n}{k-1}x^{k}=$$
$$=\sum_{k=0}^{n+1}\left(\binom{n}{k}+\binom{n}{k-1}\right)x^k=$$ $$=\sum_{k=0}^{n+1}\binom{n+1}{k}x^k$$ we use fact that $\binom{n}{k}=0$ if $k<0,k>n$ and Pascal identity
You start with $n = 0$. Then assume it's true for $n = k$ (so no need to prove it). Then prove that if it is true for $n = k$, it must be true for $n = k+1$. The result follows by induction on $n$.
• $$(1+x)^{k+1} = (1+x)(1+x)^k = (1+x) \sum_{j=0}^k \binom{k}{j}x^j = \sum_{j=0}^k\binom{k}{j}x^j + \sum_{j=0}^k\binom{k}{j}x^{j+1}$$ – Daniel Fischer Oct 23 '13 at 13:23