# math induction help? [duplicate]

I've been stuck on this question for a good while now, and I think I need some pointers.

$(1+x)^n = nC_0 + nC_1x + nC_2x^2 ... + nC_{n-1}x^{n-1} + nCnx^n$ where n greater than or equal to 1

I'm at the point where I replace n with k+1 and solve, but no matter what I do I cannot get the sides of the equation to look the same.

## marked as duplicate by JMoravitz, Claude Leibovici, Lord Shark the Unknown, kingW3, user223391 Sep 8 '17 at 18:09

So to be clear: We are proving the binomial theorem by mathematical induction?

For speed of typing, I will use $\dbinom n k$ rather than ${^n\mathrm C_k}$

It rather sounds like you are at this stage:

Assume for any $n\geq 1$ that: $(1+x)^n = \sum\limits_{k=0}^n \dbinom nk x^k$

Then it would be that: $(1+x)^{n+1} ~{= (1+x)\sum\limits_{k=0}^n \dbinom nk x^k \\ = \dbinom n 0 +\sum\limits_{k=1}^n \left({\dbinom nk+\dbinom n{k-1}}\right)x^k + \dbinom nn x^{n+1} }$

Well, there is an identity: $\dbinom{n+1}{k}=\dbinom n k+\dbinom n{k-1}$

You should now be able to continue.

Is there a way to do this without putting it in summation form, and only using the last two terms listed as the sum?

That would be:

\begin{align} & (1+x)^{n+1} \\ =~& (1+x)^n + (1+x)^n x \\ = ~& (\tbinom n0+\tbinom n1x+\ldots+\tbinom nkx^k+\ldots+\tbinom nn x^n)+(\tbinom n0x+\ldots+\tbinom n{k-1}x^k+\ldots+\tbinom n{n-1}x^n+\tbinom nn x^{n+1}) \\ = ~& \tbinom n0+(\tbinom n1+\tbinom n0)x+\ldots+(\tbinom nk+\tbinom n{k-1})x^k+\ldots+(\tbinom nn+\tbinom n{n-1}) x^n+\tbinom nn x^{n+1} \\ \vdots ~& \end{align}

• Is there a way to do this without putting it in summation form, and only using the last two terms listed as the sum? – faunaflora Sep 8 '17 at 6:51
• Yes, just expand the series demonstrating the pattern, then gather like terms. – Graham Kemp Sep 8 '17 at 8:16