The Principle of Mathematical Induction

Sequences of Statements

Statements about the natural numbers can often be regarded as sequences of statements $ P_{n} $

EXAMPLE 42.1 The statement, “The sum of the first n natural numbers is equal to $ $ ,” can be written as $ P_{n} $ : $ 1 + 2 + 3 + + n = $ or $ P_{n} $ : $ {k=1}^{n} k = $ . Then $ P{1} $ is the statement $ 1 = $ , $ P_{2} $ is the statement $ 1 + 2 = $ , and so on.

EXAMPLE 42.2 The statement, “For each natural number n, $ n^{2} - n + 41 $ is a prime number,” can be written as $ P_{n}: n^{2} - n + 41 $ is a prime number. Then $ P_{1} $ is the statement: $ 1^{2} - 1 + 41 $ , or 41, is a prime number, $ P_{2} $ is the statement: $ 2^{2} - 2 + 41 $ , or 43, is a prime number, and so on.

Principle of Mathematical Induction (PMI)

Given any statement about the natural numbers $ P_{n} $ , if the following conditions hold:

  1. $ P_{1} $ is true.

  2. Whenever $ P_{k} $ is true, $ P_{k+1} $ is true.

Then $ P_{n} $ is true for all n.

Proof by Mathematical Induction

To apply the principle of mathematical induction to a sequence of statements $ P_{n} $ :

  1. Write out the statements $ P_{1}, P_{k} $ , and $ P_{k+1} $ .

  2. Show that $ P_{} $ is true.

  3. Assume that $ P_{k} $ is true. From this assumption (it is never necessary to prove $ P_{k} $ explicitly), show that the truth of $ P_{k+1} $ follows. This proof is often called the induction step.

  4. Conclude that $ P_{n} $ holds for all n.

Failure of Proof by PMI

A sequence of statements may only be true for some values of n, or it may be true for no values of n. In these cases, the principle of mathematical induction will not apply, and the proof will fail.

EXAMPLE 42.3 In the previous example, $ P_{1} $ , $ P_{2} $ , $ P_{3} $ , and so on, up to $ P_{40} $ are all true. ( $ P_{40} $ is the statement: $ 40^{2} - 40 + 41 $ , or 1601, is a prime number.) However, $ P_{41} $ , the statement: $ 41^{2} - 41 + 41 $ , or $ 41^{2} $ , is a prime number, is clearly false. Thus the sequence of statements $ P_{n} $ is regarded as false in general, and certainly cannot be proved, although some individual statements are true.

Extended Principle of Mathematical Induction

If there is some natural number m such that all statements $ P_{n} $ of a sequence are true for $ n m $ , then the extended principle of mathematical induction may be used; if the following conditions hold:

  1. $ P_{m} $ is true.

  2. Whenever $ P_{k} $ is true, $ P_{k+1} $ is true.

Then $ P_{n} $ is true for all $ n m $ .

EXAMPLE 42.4 Let $ P_{n} $ be the statement: $ n! ^{n} $ . $ P_{1} $ , $ P_{2} $ , and $ P_{3} $ are false. (For example, $ P_{2} $ is the false statement $ 2! ^{2} $ or $ 2 $ .) However, $ P_{4} $ is the true statement $ 4! ^{4} $ or $ 24 $ , and the statement can be proved true for all $ n $ by the extended principle of mathematical induction.

SOLVED PROBLEMS

42.1. Prove the statement $ P_{n}: 1 + 2 + 3 + + n = $ by mathematical induction.

Note that the left side can be thought of as the sum of the natural numbers up to and including n. Then

$ P_{1} $ is the statement $ 1 = $ .

$ P_{k} $ is the statement $ 1 + 2 + 3 + + k = $ .

$ P_{k+1} $ is the statement $ 1 + 2 + 3 + + (k + 1) = $ .

Now $ P_{1} $ is true, since $ 1 = = = 1 $ is true. Assume that $ P_{k} $ is true for an arbitrary value of k.

To show that $ P_{k+1} $ holds under this assumption, note that the left side can be thought of as the sum of the natural numbers up to and including $ k+1 $ , thus the term on the left before the last is k, and $ P_{k+1} $ can be rewritten as

\[ P_{k+1}\colon1+2+3+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2} \]

Thus the left side of $ P_{k+1} $ differs from the left side of $ P_{k} $ only by the single additional term $ (k+1) $ . Hence, starting with $ P_{k} $ , which is assumed to be true, add $ (k+1) $ to both sides:

\[ 1+2+3+\cdots+k=\frac{k(k+1)}{2} \]

\[ 1+2+3+\cdots+k+(k+1)=\frac{k(k+1)}{2}+(k+1) \]

Simplifying the right side yields:

\[ \frac{k(k+1)}{2}+(k+1)=\frac{k(k+1)}{2}+\frac{2(k+1)}{2}=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2} \]

Thus, from the assumption that $ P_{k} $ is true, it follows that

\[ 1+2+3+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2} \]

holds. But this is precisely the statement $ P_{k+1} $ . Thus the truth of $ P_{k+1} $ follows from the truth of $ P_{k} $ . Thus, by the principle of mathematical induction, $ P_{n} $ holds for all n.

42.2. Prove the statement $ P_{n}: 1 + 3 + 5 + + (2n - 1) = n^{2} $ by mathematical induction.

Proceed as in the previous problem.

$ P_{1} $ is the statement $ 1 = 1^{2} $ .

$ P_{k} $ is the statement $ 1 + 3 + 5 + + (2k - 1) = k^{2} $

\[ P_{k+1}\text{ is the statement }1+3+5+\cdots+[2(k+1)-1]=(k+1)^{2} \]

\[ 1+3+5+\cdots+(2k-1)+(2k+1)=(k+1)^{2} \]

Now $ P_{1} $ is obviously true. Assume the truth of $ P_{k} $ and, comparing it to $ P_{k+1} $ , note that the left side of $ P_{k+1} $ differs from the left side of $ P_{k} $ only by the single additional term $ (2k+1) $ . Hence, starting with $ P_{k} $ , add $ (2k+1) $ to both sides.

\[ \begin{align*}1+3+5+\cdots+(2k-1)&=k^{2}\\1+3+5+\cdots+(2k-1)+(2k+1)&=k^{2}+(2k+1)\end{align*} \]

The right side is immediately seen to be $ k^{2} + 2k + 1 = (k + 1)^{2} $ , thus

\[ 1+3+5+\cdots+(2k-1)+(2k+1)=(k+1)^{2} \]

holds. But this is precisely the statement $ P_{k+1} $ . Thus the truth of $ P_{k+1} $ follows from the truth of $ P_{k} $ . Thus, by the principle of mathematical induction, $ P_{n} $ holds for all n.

42.3. Prove the statement $ P_{n}: 1 + 2 + 2^{2} + + 2^{n-1} = 2^{n} - 1 $ by mathematical induction.

Proceed as in the previous problems.

$ P_{1} $ is the statement $ 1 = 2^{1} - 1 $ .

$ P_{k} $ is the statement $ 1 + 2 + 2^{2} + + 2^{k-1} = 2^{k} - 1 $ .

\[ P_{k+1}\text{is the statement }1+2+2^{2}+\cdots+2^{(k+1)-1}=2^{k+1}-1\text{, which can be rewritten as} \]

\[ 1+2+2^{2}+\cdots+2^{k-1}+2^{k}=2^{k+1}-1 \]

Now $ P_{1} $ is true, since $ 1 = 2^{1} - 1 = 2 - 1 = 1 $ is true. Assume the truth of $ P_{k} $ and, comparing it to $ P_{k+1} $ , note that the left side of $ P_{k+1} $ differs from the left side of $ P_{k} $ only by the single additional term $ 2^{k} $ . Hence, starting with $ P_{k} $ , add $ 2^{k} $ to both sides.

\[ \begin{align*}1+2+2^{2}+\cdots+2^{k-1}&=2^{k}-1\\1+2+2^{2}+\cdots+2^{k-1}+2^{k}&=2^{k}+2^{k}-1\end{align*} \]

Simplifying the right side yields:

\[ \begin{aligned}&2^{k}+2^{k}-1=2\cdot2^{k}-1=2^{1}\cdot2^{k}-1=2^{k+1}-1,thus\\&1+2+2^{2}+\cdots+2^{k-1}+2^{k}=2^{k+1}-1\\ \end{aligned} \]

holds. But this is precisely the statement $ P_{k+1} $ . Thus the truth of $ P_{k+1} $ follows from the truth of $ P_{k} $ . Thus, by the principle of mathematical induction, $ P_{n} $ holds for all n.

42.4. Prove the statement $ P_{n}:_{j=1}{n}j{2}= $ by mathematical induction.

Proceed as in the previous problems.

\[ P_{1}\text{ is the statement}\sum_{j=1}^{1}j^{2}=\frac{1(1+1)(2\cdot1+1)}{6}. \]

\[ P_{k}\text{ is the statement }\sum_{i=1}^{k}j^{2}=\frac{k(k+1)(2k+1)}{6}\text{or}1^{2}+2^{2}+\cdots+k^{2}=\frac{k(k+1)(2k+1)}{6}. \]

\[ P_{k+1}\text{is the statement}\sum_{i=1}^{k+1}j^{2}=\frac{(k+1)[(k+1)+1][2(k+1)+1]}{6},\text{which can be rewritten as} \]

\[ 1^{2}+2^{2}+\cdot\cdot\cdot+k^{2}+(k+1)^{2}=\frac{(k+1)(k+2)(2k+3)}{6} \]

Now $ P_{1} $ is true, since the left side is merely $ 1^{2} $ and the right side is $ $ , that is, 1. Assume the truth of $ P_{k} $ and, comparing it to $ P_{k+1} $ , note that the left side of $ P_{k+1} $ differs from the left side of $ P_{k} $ only by the single additional term $ (k+1)^{2} $ . Hence, starting with $ P_{k} $ , add $ (k+1)^{2} $ to both sides.

\[ \begin{aligned}1^{2}+2^{2}+\cdots+k^{2}&=\frac{k(k+1)(2k+1)}{6}\\1^{2}+2^{2}+\cdots+k^{2}+(k+1)^{2}&=\frac{k(k+1)(2k+1)}{6}+(k+1)^{2}\end{aligned} \]

Simplifying the right side yields:

\[ \begin{aligned}\frac{k(k+1)(2k+1)}{6}+(k+1)^{2}&=\frac{k(k+1)(2k+1)}{6}+\frac{6(k+1)^{2}}{6}\\&=\frac{(k+1)[k(2k+1)+6(k+1)]}{6}\\&=\frac{(k+1)[2k^{2}+7k+6]}{6}\\&=\frac{(k+1)(k+2)(2k+3)}{6}\end{aligned} \]

Thus $ 1^{2} + 2^{2} + + k^{2} + (k + 1)^{2} = $ holds. But this is precisely the statement $ P_{k+1} $ . Thus the truth of $ P_{k+1} $ follows from the truth of $ P_{k} $ . Thus, by the principle of mathematical induction, $ P_{n} $ holds for all n.

42.5. Prove the statement $ P_{n}: n < 2^{n} $ for any positive integer n by mathematical induction.

$ P_{1} $ is the statement $ 1 < 2^{1} $ .

$ P_{k} $ is the statement $ k < 2^{k} $ .

$ P_{k+1} $ is the statement $ k + 1 < 2^{k+1} $

Now $ P_{1} $ is obviously true. Assume the truth of $ P_{k} $ , and, comparing it with $ P_{k+1} $ , note that the right side of $ P_{k+1} $ is 2 times the right side of $ P_{k} $ . Hence, starting with $ P_{k} $ , multiply both sides by 2:

\[ \begin{aligned}2^{k}&>k\\2\cdot2^{k}&>2k\\2^{k+1}&>2k\end{aligned} \]

But $ 2k = k + k k + 1 $ . Hence

\[ 2^{k+1}>2k\geq k+1\qquad and\qquad2^{k+1}>k+1. \]

But this is precisely the statement $ P_{k+1} $ . Thus the truth of $ P_{k+1} $ follows from the truth of $ P_{k} $ . Thus, by the principle of mathematical induction, $ P_{n} $ holds for all positive integers n.

42.6. Prove the statement $ P_{n}: n! > 2^{n} $ is true for any integer $ n $ by the extended principle of mathematical induction. $ P_{4} $ is the statement $ 4! > 2^{4} $ .

$ P_{k} $ is the statement $ k! > 2^{k} $ , or $ 1 k > 2^{k} $ .

\[ P_{k+1}\text{ is the statement }(k+1)!>2^{k+1},\text{ or }1\cdot2\cdot3\cdot\cdot\cdot\cdot k\cdot(k+1)>2^{k+1}. \]

Now $ P_{4} $ is true, since $ 4! = 1 = 24 $ and $ 2^{4} = 16 $ . Assume the truth of $ P_{k} $ , and, comparing it with $ P_{k+1} $ , note that the left side of $ P_{k+1} $ is $ k + 1 $ times the left side of $ P_{k} $ . Hence, starting with $ P_{k} $ , multiply both sides by $ k + 1 $ :

\[ \begin{aligned}&1\cdot2\cdot3\cdot\cdots\cdot k>2^{k}\\&1\cdot2\cdot3\cdot\cdots\cdot k\cdot(k+1)>2^{k}(k+1)\\ \end{aligned} \]

But, since \(k>1, k+1>2\), hence \(2^{k}(k+1)>2^{k}\cdot2=2^{k}\cdot2^{1}=2^{k+1}\). Therefore

\[ 1\cdot2\cdot3\cdot\cdot\cdot\cdot\cdot k\cdot(k+1)>2^{k+1} \]

holds. But this is precisely the statement $ P_{k+1} $ . Thus the truth of $ P_{k+1} $ follows from the truth of $ P_{k} $ . Thus, by the extended principle of mathematical induction, $ P_{n} $ holds for all $ n $ .

42.7. Prove the statement $ P_{n}: x - y $ is a factor of $ x^{n} - y^{n} $ for any positive integer n by mathematical induction.

$ P_{1} $ is the statement: x - y is a factor of $ x^{1} - y^{1} $ .

\(P_{k}\) is the statement: \(x - y\) is a factor of \(x^{k} - y^{k}\).

$ P_{k+1} $ is the statement: x - y is a factor of $ x^{k+1} - y^{k+1} $

Now \(P_{1}\) is true, since any number is a factor of itself. Assume the truth of \(P_{k}\); the statement can be rewritten as \(x^{k}-y^{k}=(x-y)Q(x)\), where \(Q(x)\) is some polynomial. Similarly \(P_{k+1}\) can be rewritten as \(x^{k+1}-y^{k+1}=(x-y)R(x)\), where \(R(x)\) is some (other) polynomial. To show that \(P_{k+1}\) holds under the assumption of the truth of \(P_{k}\), note that

\[ \begin{aligned}x^{k+1}-y^{k+1}&=x^{k+1}-xy^{k}+xy^{k}-y^{k+1}\\&=(x^{k+1}-xy^{k})+(xy^{k}-y^{k+1})\\&=x(x^{k}-y^{k})+y^{k}(x-y)\\ \end{aligned} \]

Since by assumption $ x{k}-y{k}=(x-y)Q(x) $ , then

\[ \begin{aligned}x^{k+1}-y^{k+1}&=x(x^{k}-y^{k})+y^{k}(x-y)\\&=x(x-y)Q(x)+y^{k}(x-y).\\&=(x-y)[xQ(x)+y^{k}]\end{aligned} \]

In other words, the required polynomial $ R(x) $ is equal to $ xQ(x) + y^{k} $ and x - y is a factor of $ x^{k+1} - y^{k+1} $ . But this is precisely the statement $ P_{k+1} $ . Thus the truth of $ P_{k+1} $ follows from the truth of $ P_{k} $ . Thus, by the principle of mathematical induction, $ P_{n} $ holds for all positive integers n.

42.8. Use the principle of mathematical induction to prove DeMoivre’s theorem: If $ z = r(+ i) $ is a complex number in trigonometric form, then for any positive integer n, $ z^{n} = r^{n} (n+ in) $ .

Here $ P_{n} $ is the statement $ z{n}=r{n}(n+in) $ . Then

$ P_{1} $ is the statement $ z{1}=r{1}(+i) $ .

\[ P_{k}\text{ is the statement }z^{k}=r^{k}(\cos k\theta+i\sin k\theta). \]

\[ P_{k+1}\text{ is the statement }z^{k+1}=r^{k+1}[\cos(k+1)\theta+i\sin(k+1)\theta]. \]

Now $ P_{1} $ is obviously true. Assume the truth of $ P_{k} $ , and, comparing it with $ P_{k+1} $ , note that the left side of $ P_{k+1} $ is z times the left side of $ P_{k} $ . Hence, starting with $ P_{k} $ , multiply both sides by z:

\[ \begin{aligned}z^{k}&=r^{k}(\cos k\theta+i\sin k\theta)\\zz^{k}&=z(r^{k}(\cos k\theta+i\sin k\theta))\end{aligned} \]

\[ z^{k+1}=r(\cos\theta+i\sin\theta)r^{k}(\cos k\theta+i\sin k\theta) \]

\[ z^{k+1}=r r^{k}(\cos\theta+i\sin\theta)(\cos k\theta+i\sin k\theta) \]

\[ z^{k+1}=r^{k+1}(\cos\theta+i\sin\theta)(\cos k\theta+i\sin k\theta) \]

But by the rule for multiplying complex numbers in trigonometric form,

\[ (\cos\theta+i\sin\theta)(\cos k\theta+i\sin k\theta)=\cos(\theta+k\theta)+i\sin(\theta+k\theta)=\cos(k+1)\theta+i\sin(k+1)\theta \]

Thus $ z{k+1}=r{k+1}[(k+1)+i(k+1)] $ holds. But this is precisely the statement $ P_{k+1} $ . Thus the truth of $ P_{k+1} $ follows from the truth of $ P_{k} $ . Thus, by the principle of mathematical induction, $ P_{n} $ , that is, DeMoivre’s theorem, holds for all positive integers n.

SUPPLEMENTARY PROBLEMS

42.9. Prove by mathematical induction: $ 2 + 4 + 6 + + 2n = n(n + 1) $ .

42.10. Prove by mathematical induction: $ 3 + 7 + 11 + + (4n - 1) = n(2n + 1) $ .

42.11. Prove by mathematical induction: $ 1 + 3 + 3^{2} + + 3^{n-1} = $ .

42.12. Prove by mathematical induction: $ 1^{3} + 2^{3} + 3^{3} + + n^{3} = $ .

42.13. Deduce from Problems 42.1 and 42.12 that $ {k=1}{n}k{3}=({k=1}{n}k){2} $

42.14. Prove by mathematical induction: $ ++++= $

42.15. Prove $ + + + + > , n $ , by the extended principle of mathematical induction.

42.16. Prove by mathematical induction: $ x + y $ is a factor of $ x^{2n-1} + y^{2n-1} $ for any positive integer n.