Newton's binomial by induction

Statement

Prove Newton’s binomial $\displaystyle(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k$ by induction on $n$.

Solution

Base ($n=0$): $(a+b)^0=1=\binom{0}{0}a^0b^0$. True.

Step: suppose it holds for $n$ and multiply by $(a+b)$: $(a+b)^{n+1}=(a+b)\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k = \sum_{k=0}^n\binom{n}{k}a^{n+1-k}b^k + \sum_{k=0}^n\binom{n}{k}a^{n-k}b^{k+1}.$ Realigning the indices and collecting the term of degree $b^k$, we use Stifel’s rule $\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$: $(a+b)^{n+1}=\sum_{k=0}^{n+1}\binom{n+1}{k}a^{n+1-k}b^k,$ which is the formula for $n+1$. ∎

Links

Topics: Set theory
Concepts: Principle of induction
Methods: Induction
Skills: Proving
People: Isaac Newton
Exercise type: Proof