Answer to Question #142110 in Discrete Mathematics for Promise Omiponle

Question

Use Mathematical Induction to prove the Binomial Theorem.

Answer 1

Let us give a proof of the Binomial Theorem using mathematical induction. We will need to use Pascal's identity in the form:

$\left(\begin{array}{c}n\\r-1\end{array}\right)+\left(\begin{array}{c}n\\r\end{array}\right)=\left(\begin{array}{c}n+1\\r\end{array}\right)$ for $0<r\le n$.

We aim to prove that

$(a+b)^n=a^n+\left(\begin{array}{c}n\\1\end{array}\right)a^{n−1}b+\left(\begin{array}{c}n\\2\end{array}\right)a^{n−2}b^2+⋯+\left(\begin{array}{c}n\\r\end{array}\right)a^{n−r}b^r +⋯+\left(\begin{array}{c}n\\n-1\end{array}\right)ab^{n−1}+ b^n.$

We first note that the result is true for n=1 and n=2: $(a+b)^1=a+b$ and $(a+b)^2=a^2+2ab+b^2=a^2+\left(\begin{array}{c}2\\1\end{array}\right)ab+b^2$.

Let $k$ be a positive integer with $k≥2$ for which the statement is true. So

$(a+b)^k=a^k+\left(\begin{array}{c}k\\1\end{array}\right)a^{k−1}b+\left(\begin{array}{c}k\\2\end{array}\right)a^{k−2}b^2+⋯+\left(\begin{array}{c}k\\r\end{array}\right)a^{k−r}b^r +⋯+\left(\begin{array}{c}k\\k-1\end{array}\right)ab^{k−1}+ b^k$

Now consider the expansion

$(a+b)^{k+1}=(a+b)(a+b)^k=$

$=(a+b)(a^k+\left(\begin{array}{c}k\\1\end{array}\right)a^{k−1}b+\left(\begin{array}{c}k\\2\end{array}\right)a^{k−2}b^2+⋯+\left(\begin{array}{c}k\\r\end{array}\right)a^{k−r}b^r +⋯+\left(\begin{array}{c}k\\k-1\end{array}\right)ab^{k−1}+ b^k)=$

$=a^{k+1}+\left[1+\left(\begin{array}{c}k\\1\end{array}\right)\right]a^{k}b+\left[\left(\begin{array}{c}k\\1\end{array}\right)+\left(\begin{array}{c}k\\2\end{array}\right)\right]a^{k−1}b^2+⋯+\left[\left(\begin{array}{c}k\\r-1\end{array}\right)+\left(\begin{array}{c}k\\r\end{array}\right)\right]a^{k+1−r}b^r +⋯+\left[\left(\begin{array}{c}k\\k-1\end{array}\right)+1\right]ab^{k}+ b^{k+1}$

From Pascal's identity, it follows that

$(a+b)^{k+1}=a^{k+1}+\left(\begin{array}{c}k+1\\1\end{array}\right)a^{k}b+\left(\begin{array}{c}k+1\\2\end{array}\right)a^{k−1}b^2+⋯+\left(\begin{array}{c}k+1\\r\end{array}\right)a^{k+1−r}b^r +⋯+\left(\begin{array}{c}k+1\\k\end{array}\right)ab^{k}+ b^{k+1}$

Hence the result is true for $k+1$. By induction, the result is true for all positive integers $n$.