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

Question

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

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

3. 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 :)

Answer 1

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

Answer 2

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?

Answer 3

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