enter image description here

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...

  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ How do I go about proving it for n=k+1? $\endgroup$ – Vladimir Nabokov Oct 23 '13 at 13:19
  • $\begingroup$ $$(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}$$ $\endgroup$ – Daniel Fischer Oct 23 '13 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.