Prove by induction that $(1 + x)^n = ...$ (binomial expansion) 
*

*First, let $\binom{n}{k} = \frac{n!}{k!(n-k!)}$ for any integers $0 \le k \le n$

*Show that $\binom{n-1}{k-1}+\binom{n-1}{k} = \binom{n}{k}$ for any $1 \le k \le n$
(I don't need help with this part, I have worked it out and it is true. This must be a hint for how to use induction, but I can't figure out exactly how to apply it, hmm...)


*Now, using point (2) and induction, prove that for any integer $n \ge 1$ and any real number $x$,
$$
(1+x)^n = \sum_{k=0}^n x^k \binom{n}{k}
$$


I'm guessing that the solution will require strong induction, i.e. I'll need to assume that for some integer a, the equivalence holds for all b in the range $1 \le b \le a$ and using this assumption show that the equivalence holds for $a+1$ as well. Perhaps multiply both sides by $(1+x)$? But that really messes up the binomial terms... Any help would be greatly appreciated! Thank you :)
 A: Suppose the statement is true for $n$.
$$\begin{align}
(1+x)^{n+1} & =(1+x)(1+x)^n\\
& =(1+x)\sum_{k=0}^n\binom nkx^k\\
& = \sum_{k=0}^n\binom nkx^k+\sum_{k=0}^n\binom nkx^{k+1}\\
& = 1+\sum_{k=1}^n\binom nkx^k+\sum_{k=1}^{n+1}\binom{n-1}kx^k.
\end{align}$$
Can you get it from here?
A: I did it by induction, it is easy to check case for n=1, assume it holds for n and prove n+1 case:
$\text{Ind. Hyp : }(1+x)^n=\sum_{k=0}^{n}{n\choose k}x^k \\
\text{Now we need to show }(1+x)^{n+1}=\sum_{k=0}^{n+1}{n+1\choose k}x^k \\
(1+x)^{n+1}=(1+x)(1+x)^n = \text{(by induction hypothesis)} (1+x)\sum_{k=0}^{n}{n\choose k}x^k \\
(1+x)\sum_{k=0}^{n}{n\choose k}x^k=\sum_{k=0}^{n}{n\choose k}x^k+\sum_{k=0}^{n}{n\choose k}x^{k+1} \text{ , simply by expanding parentheses stuffs}\\
\text{Notice two things:}\\
(1) \sum_{k=0}^{n}{n\choose k}x^k=1+\sum_{k=1}^{n}{n\choose k}x^k \\
(2) \sum_{k=0}^{n}{n\choose k}x^{k+1}=\sum_{k=1}^{n+1}{n\choose k-1}x^{k}=x^{n+1}+\sum_{k=1}^{n}{n\choose k-1}x^k \\
\text{The expression that we have: }\\ \sum_{k=0}^{n}{n\choose k}x^k+\sum_{k=0}^{n}{n\choose k}x^{k+1}=(1)+(2)=1+\sum_{k=1}^{n}{n\choose k}x^k +x^{n+1}+\sum_{k=1}^{n}{n\choose k-1}x^k=(3) \\
(3)=1+x^{n+1}+\sum_{k=1}^{n}\Big({n\choose k}+{n\choose k-1}\Big)x^k\\
\text{Using the identity: } {n\choose k}+{n\choose k-1}={n+1\choose k} \text{ we substitute into (3) to obtain:}\\
(3)=1+x^{n+1}+\sum_{k=1}^{n}{n+1\choose k}x^k=x^0{n+1\choose 0}+{n+1\choose n+1}x^{n+1}+\sum_{k=1}^{n}{n+1\choose k}x^k=\sum_{k=0}^{n+1}{n+1\choose k}x^k \\
\text{Which is the desired result.}
$
A: Assume it is true for $n$. Here is a start.
$$\sum_{k=0}^{n+1} {n+1 \choose k} x^k
= \sum_{k=0}^{n+1} \left( {n\choose k-1} + {n\choose k}\right) x^k.{{}}$$
Now split this sum in two.  One piece will yield $(1+x)^n$ and the other will  yield $x(1 +x)^n$.
