Skip to content

Mathematics · Ch 9 — Binomial Theorem

Proof by Mathematical Induction

3

Proof by Mathematical Induction

Setting Up the Induction

Let P(n)P(n) be the statement

P(n):(a+b)n=∑r=0nnCr an−rbr=nC0an+nC1an−1b+⋯+nCnbn.P(n):\qquad (a+b)^n = \sum_{r=0}^{n} {}^{n}C_r\, a^{n-r}b^r = {}^{n}C_0a^n+{}^{n}C_1a^{n-1}b+\cdots+{}^{n}C_nb^n.

We prove P(n)P(n) is true for every positive integer nn using the principle of mathematical induction.

Proof.

Base case (n=1n=1). The left side is (a+b)1=a+b(a+b)^1 = a+b. The right side is 1C0 a1+1C1 b1=a+b^{1}C_0\,a^1+{}^{1}C_1\,b^1 = a+b, since 1C0=1C1=1^{1}C_0={}^{1}C_1=1. Both sides agree, so P(1)P(1) is true.

Inductive hypothesis. Assume P(k)P(k) is true for some positive integer kk, i.e.

(a+b)k=kC0ak+kC1ak−1b+kC2ak−2b2+⋯+kCk−1abk−1+kCkbk.(a+b)^k = {}^{k}C_0a^k+{}^{k}C_1a^{k-1}b+{}^{k}C_2a^{k-2}b^2+\cdots+{}^{k}C_{k-1}ab^{k-1}+{}^{k}C_kb^k.

Inductive step. We must show P(k+1)P(k+1) follows, i.e. that

(a+b)k+1=∑r=0k+1k+1Cr ak+1−rbr.(a+b)^{k+1} = \sum_{r=0}^{k+1}{}^{k+1}C_r\,a^{k+1-r}b^r.

Multiply both sides of the inductive hypothesis by (a+b)(a+b):

(a+b)k+1=(a+b)⋅(a+b)k=(a+b)[kC0ak+kC1ak−1b+⋯+kCkbk].(a+b)^{k+1} = (a+b)\cdot(a+b)^k = (a+b)\left[{}^{k}C_0a^k+{}^{k}C_1a^{k-1}b+\cdots+{}^{k}C_kb^k\right].

Distribute, multiplying the bracket once by aa and once by bb:

a⋅[⋯ ]=kC0ak+1+kC1akb+kC2ak−1b2+⋯+kCk−1a2bk−1+kCkabk,a\cdot[\cdots] = {}^{k}C_0a^{k+1}+{}^{k}C_1a^{k}b+{}^{k}C_2a^{k-1}b^2+\cdots+{}^{k}C_{k-1}a^2b^{k-1}+{}^{k}C_kab^k,

b⋅[⋯ ]=kC0akb+kC1ak−1b2+⋯+kCk−2a2bk−1+kCk−1abk+kCkbk+1.b\cdot[\cdots] = {}^{k}C_0a^{k}b+{}^{k}C_1a^{k-1}b^2+\cdots+{}^{k}C_{k-2}a^2b^{k-1}+{}^{k}C_{k-1}ab^k+{}^{k}C_kb^{k+1}.

Adding these two expansions, the first term kC0ak+1^{k}C_0a^{k+1} (from the first row) and the last term kCkbk+1^{k}C_kb^{k+1} (from the second row) have no matching term to combine with. Every other term, however, appears once in each row: the term in ak+1−rbra^{k+1-r}b^r (for 1≤r≤k1\le r\le k) gets a contribution kCr^{k}C_r from the first row and a contribution kCr−1^{k}C_{r-1} from the second row, so its combined coefficient is kCr−1+kCr^{k}C_{r-1}+{}^{k}C_r.

Lemma (used here, and revisited pictorially in the next section). For 1≤r≤k1\le r\le k,

kCr−1+kCr=k+1Cr.{}^{k}C_{r-1}+{}^{k}C_r = {}^{k+1}C_r.

Proof of the lemma. Using nCr=n!r!(n−r)!^{n}C_r=\dfrac{n!}{r!(n-r)!}:

kCr−1+kCr=k!(r−1)!(k−r+1)!+k!r!(k−r)!=k!(r−1)!(k−r)![1k−r+1+1r]=k!(r−1)!(k−r)!⋅r+(k−r+1)r(k−r+1).{}^{k}C_{r-1}+{}^{k}C_r = \frac{k!}{(r-1)!(k-r+1)!}+\frac{k!}{r!(k-r)!} = \frac{k!}{(r-1)!(k-r)!}\left[\frac{1}{k-r+1}+\frac{1}{r}\right] = \frac{k!}{(r-1)!(k-r)!}\cdot\frac{r+(k-r+1)}{r(k-r+1)}.

The numerator r+(k−r+1)r+(k-r+1) simplifies to k+1k+1, so

kCr−1+kCr=k!(r−1)!(k−r)!⋅k+1r(k−r+1)=(k+1)!r!(k+1−r)!=k+1Cr.■{}^{k}C_{r-1}+{}^{k}C_r = \frac{k!}{(r-1)!(k-r)!}\cdot\frac{k+1}{r(k-r+1)} = \frac{(k+1)!}{r!(k+1-r)!} = {}^{k+1}C_r. \qquad\blacksquare …

Start your 14-day free trial to unlock the full solution →
← Previous · 2Statement of the Binomial Theorem for Positive Integral IndexNext · 4 →Pascal's Triangle