Proof that $(1 + t)^n = \sum\limits_{k = 0}^{n} \binom{n}{k} t^k$

Question

I'm not understanding this proof from Combinatorics: Topics, Techniques, Algorithms by Peter J. Cameron. Here is his proof of this theorem:

The theorem can be proven by induction on $n$. It is trivially true for $n = 0$. Assuming the result for $n$, we have $\displaystyle(1 + t)^{n + 1} = (1+t)^{n} \cdot (1 + t) = \left( \sum\limits_{k = 0}^{n} \binom{n}{k} t^k \right) \cdot (1 + t)$

the coefficient of $t^k$ on the right is $\displaystyle \binom{n}{k - 1} + \binom{n}{k}$ (the first term coming from $t^{k - 1} \cdot t$ and the second coming from $t^k \cdot 1$ and $\displaystyle \binom{n}{k - 1} + \binom{n}{k} = \binom{n + 1}{k}$

I'm very lost and don't see how this shows that the formula holds for $(1 + t)^{n + 1}$

Answer 1

Well we have that \begin{align} (1+t)^{n+1} &= \left(\sum_{k=0}^{n}\begin{pmatrix}n \\ k \end{pmatrix}t^k\right)(1+t) \\ &= \sum_{k=0}^{n}\begin{pmatrix}n \\ k \end{pmatrix}t^k + \sum_{k=0}^{n}\begin{pmatrix}n \\ k \end{pmatrix}t^{k+1} \\ &= \begin{pmatrix}n \\ 0 \end{pmatrix} + \sum_{k=1}^{n}\begin{pmatrix}n \tag{1}\\ k \end{pmatrix}t^k + \sum_{k=1}^{n}\begin{pmatrix}n \\ k-1 \end{pmatrix}t^k + \begin{pmatrix}n \\ n \end{pmatrix}t^{n+1} \\ &= \begin{pmatrix}n \\ 0 \end{pmatrix} + \sum_{k=1}^{n}\left[\begin{pmatrix}n \\ k \end{pmatrix} + \begin{pmatrix}n \\ k-1 \end{pmatrix}\right]t^k + \begin{pmatrix}n \\ n \end{pmatrix}t^{n+1} \\ &= \begin{pmatrix}n \\ 0 \end{pmatrix} + \sum_{k=1}^{n}\begin{pmatrix}n + 1 \\ k \end{pmatrix} t^k + \begin{pmatrix}n \\ n \end{pmatrix}t^{n+1}, \tag{2} \end{align} where at $(1)$ we have used the fact that \begin{align} \sum_{k=0}^{n}\begin{pmatrix}n \\ k \end{pmatrix}t^{k+1} &= \sum_{k=1}^{n+1}\begin{pmatrix}n \\ k-1 \end{pmatrix}t^{k} \\ &= \sum_{k=1}^{n}\begin{pmatrix}n \\ k-1 \end{pmatrix}t^{k} + \begin{pmatrix}n \\ n \end{pmatrix}, \end{align} (which follows by relabelling the summands via $k \mapsto k-1$) and at $(2)$ we have used the identity \begin{align} \begin{pmatrix}n \\ k \end{pmatrix} + \begin{pmatrix}n \\ k-1 \end{pmatrix} = \begin{pmatrix}n +1 \\ k \end{pmatrix}. \end{align} Can you take it from here?

Now, we can take this a step further by the following: by the above calculations \begin{align} (1+t)^{n+1} &= \begin{pmatrix}n \\ 0 \end{pmatrix} + \sum_{k=1}^{n}\begin{pmatrix}n + 1 \\ k \end{pmatrix} t^k + \begin{pmatrix}n \\ n \end{pmatrix}t^{n+1} \\ &= \begin{pmatrix}n \\ 0 \end{pmatrix} - \begin{pmatrix}n+1 \\ 0 \end{pmatrix} + \sum_{k=0}^{n+1}\begin{pmatrix}n + 1 \\ k \end{pmatrix} t^k + \begin{pmatrix}n \\ n \end{pmatrix}t^{n+1} - \begin{pmatrix}n + 1 \\ n+1 \end{pmatrix}t^{n+1} \\ &= \sum_{k=0}^{n+1}\begin{pmatrix}n + 1 \\ k \end{pmatrix} t^k,\end{align} where the last equality follows since $ \begin{pmatrix} N \\ 0 \end{pmatrix} = \begin{pmatrix} N \\ N \end{pmatrix} = 1$ for any $N \in \mathbb{N}$.

Answer 2

Suppose, say, that you know that the statement holds when $n=3$ whan that you want to prove that it holds when $n=4$.

Then you are assuming that$$(1+t)^3=\binom 30+\binom 31t+\binom32t^2+\binom33t^3.$$So\begin{align}(1+t)^4&=(1+t)^3(1+t)\\&=\left(\binom30+\binom31t+\binom32t^2+\binom33t^3\right)(1+t)\\&=\binom30+\left(\binom30+\binom31\right)t+\left(\binom31+\binom32\right)t^2+\left(\binom32+\binom33\right)t^3+\binom33t^4.\end{align}But:

• $\displaystyle\binom30=1=\binom40$;
• $\displaystyle\binom30+\binom31=\binom41$;
• $\displaystyle\binom31+\binom32=\binom42$;
• $\displaystyle\binom32+\binom33=\binom43$;
• $\displaystyle\binom33=1=\binom44$.

And therefore$$(1+t)^4=\binom40+\binom41t+\binom42t^2+\binom43t^3+\binom44t^4$$indeed. This is what the author of that textbook is doing.