Binomial theorem $(a+b)^n=\sum \limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k}$

Question

I'm trying to understand the proof by induction of: $$ (a+b)^n = \sum \limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k} $$ I'm at the point of deriving the inductive step and am getting next: $$ (a+b)^{n+1} = (a+b)(a+b)^n=\dotsb = a^{n+1} + b^{n+1} + \sum_{k=1}^{n}\binom{n}{k}a^{n+1-k}b^{k} + \sum_{k=1}^{n}\binom{n}{k-1}a^{n-1-k}b^{k} $$

Now, I also have a solution to this problem, and in the solution the two summations are turned into exactly the middle elements of the series (since $a^{n+1}$ and $b^{n+1}$ are the first and the last elements of the series correspondingly) and we get a perfect proof. However, I don't understand how next was achieved:

$$ \sum_{k=1}^{n}\binom{n}{k}a^{n+1-k}b^{k} + \sum_{k=1}^{n}\binom{n}{k-1}a^{n-1-k}b^{k} = \sum_{k=1}^{n}\binom{n+1}{k}a^{n+1-k}b^{k} $$

Any advises and hints are welcome.

Answer 1

I think that you made a mistake in the first formula you got, it should be $$(a+b)^{n+1}=a^{n+1} + b^{n+1} + \sum_{k=1}^{n}\binom{n}{k}a^{n+1-k}b^{k} + \sum_{k=1}^{n}\binom{n}{k-1}a^{n+1-k}b^{k}$$ (in last term, $a^{n+1-k}$)

and then use the formula: $$\binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k}$$

Answer 2

You made a mistake in your indices. Here is the full derivation.

$$(a+b)^{n+1} = (a+b)(a+b)^n = \text{(use induction)} = (a+b)\sum_{k=0}^n{n\choose k}a^{n-k}b^k=\\ =a\sum_{k=0}^n{n\choose k}a^{n-k}b^k + b\sum_{k=0}^n{n\choose k}a^{n-k}b^k =\\ =\sum_{k=0}^n{n\choose k}a^{n-k+1}b^k+\sum_{k=0}^n{n\choose k}a^{n-k}b^{k+1}\\$$

Now, take the first element "out" of the first sum and the last element "out" of the second sum, so that you get

$$(a+b)^{n+1} = \left[a^{n+1}+\sum_{k=1}^n{n\choose k}a^{n-k+1}b^k\right] + \left[\sum_{k=0}^{n-1}{n\choose k}a^{n-k}b^{k+1} + b^{n+1}\right]=\\ =\sum_{k=1}^n{n\choose k}a^{n-k+1}b^k +\sum_{k=0}^{n-1}{n\choose k}a^{n-k}b^{k+1} + a^{n+1}+b^{n+1}.$$

Now, in the second sum (running from $0$ to $n-1$), replace $k$ with $l=k+1$, meaning $k=l-1$, to get $$\sum_{k=0}^{n-1}{n\choose k}a^{n-k}b^{k+1} =\sum_{l=1}^{n}{n\choose l-1}a^{n-l+1}b^{l}.$$ Plugging this equality in the original derivation gives $$(a+b)^{n+1} = \sum_{k=1}^n{n\choose k}a^{n-k+1}b^k +\sum_{l=1}^{n}{n\choose l-1}a^{n-l+1}b^{l} + a^{n+1}+b^{n+1}.$$

Now you can see that the index $k$ in the first sum and $l$ in the second both run from $1$ to $n$, so the $2$ sums can be joined: $$(a+b)^{n+1} = a^{n+1}+b^{n+1} +\sum_{k=1}^n\left({n\choose k} + {n\choose k-1}\right)a^{n-k+1}b^k$$

using the formula $${n\choose k}+{n\choose k-1}={n+1\choose k},$$ you now get the final result $$(a+b)^{n+1} = a^{n+1}+b^{n+1} +\sum_{k=1}^n{n+1\choose k}a^{n-k+1}b^k$$

Answer 3

Essential is the well-known equality: $$\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$$ Under the 'convenient' convention that $\binom{n}{k}=0$ if $k\notin\left\{ 0,\dots,n\right\} $ this is true for each $k\in\mathbb{Z}$.

In the following summation $k$ ranges over $\mathbb{Z}$:

$$\left(a+b\right)^{n+1}=\left(a+b\right)\sum\binom{n}{k}a^{k}b^{n-k}=\sum\binom{n}{k}a^{k+1}b^{n-k}+\sum\binom{n}{k}a^{k}b^{n+1-k}$$

$$=\sum\left[\binom{n}{k-1}+\binom{n}{k}\right]a^{k}b^{n+1-k}=\sum\binom{n+1}{k}a^{k}b^{n+1-k}$$