Mathematical Induction

Mathematical induction is a method of proving statements that depend on a natural number $n$: formulas for sums, divisibility, inequalities. On this page we will see where the name of the method comes from, why the method is valid and how to use it.

On this page: Incomplete induction · Complete induction · Principle of mathematical induction · Examples · Induction from ${n=m}$ · Conjecture and proof · Problems

Incomplete Induction

A method of investigation in which we look at individual elements of a set and use them to discover properties of the whole set is called the inductive method. When not all cases have been examined, we say that incomplete induction has been used.

Here is an example from the history of mathematics. The 17th-century French mathematician Pierre de Fermat looked at the numbers

${2^{2^1}+1=5}$, ${2^{2^2}+1=17}$, ${2^{2^3}+1=257}$, ${2^{2^4}+1=65{,}537}$

and noticed that all of them are prime. He conjectured that the number ${2^{2^n}+1}$ is prime for every natural $n$. For ${n=5}$ we get ${2^{2^5}+1=4{,}294{,}967{,}297}$, and Fermat could not check whether it has nontrivial divisors. Later Euler showed that it is divisible by 641: ${4{,}294{,}967{,}297}={641\cdot 6{,}700{,}417}$. So Fermat's conjecture is false.

There are also examples in which the first case that disproves a conjecture made by incomplete induction is so far away that no amount of checking can reach it. For example, it seems that the number ${991n^2+1}$ is never a perfect square. This is indeed true for every natural $n$ less than

${n}={12{,}055{,}735{,}790{,}331}\allowbreak{{,}359{,}447{,}442{,}538{,}767}$,

but for this 29-digit number ${991n^2+1}$ is a perfect square. So many checks are beyond even the fastest computers.

These examples show that a conclusion based on incomplete induction can be false, so incomplete induction must be used with care. It is useful because particular cases suggest a pattern and help us state a conjecture. The truth of the conjecture, however, has to be proved in another way.

Complete Induction

If there are finitely many particular cases and all of them have been examined, the conclusion is justified. For example, to find how many prime numbers there are among the numbers from 1 to 10, it is enough to check each of them: 2, 3, 5 and 7 are prime. The conclusion "there are 4 primes among the first ten numbers" needs no other justification.

A method in which we examine all elements of a set and draw a conclusion about the whole set is called complete induction (also proof by exhaustion). A conclusion reached by complete induction is completely reliable, so it is a method of rigorous proof.

Complete induction, however, is rarely used: it is cumbersome when there are many cases and impossible when there are infinitely many. An infinite set can be examined with it only if it is split into finitely many parts, each of which is examined separately.

Example. Prove that the square of a natural number cannot end in 2.

The last digit of a square depends only on the last digit of the number. So we split the natural numbers into 10 parts according to their last digit and check each part:

$n$ ends in	0	1	2	3	4
$n^2$ ends in	0	1	4	9	6
$n$ ends in	5	6	7	8	9
$n^2$ ends in	5	6	9	4	1

The digit 2 does not appear in the rows for $n^2$, and the problem is solved.

Principle of Mathematical Induction

When the set of cases is infinite and cannot be split into finitely many parts, other methods are used. One of them is the method of mathematical induction. It is based on one of the axioms of the natural numbers stated by the Italian mathematician Giuseppe Peano (1889). That is why, despite its name, mathematical induction is a deductive method.

Induction axiom. If a set $M$ of natural numbers contains the number 1 and, together with every number $k$, it also contains the next number ${k+1}$, then $M$ contains all natural numbers.

For proofs it is used in the following form.

Principle of mathematical induction. Let $T(n)$ be a statement about the natural number $n$. If $T(1)$ is true and, for every natural $k$, the truth of $T(k)$ implies the truth of ${T(k+1)}$, then $T(n)$ is true for every natural $n$.

Indeed, let $M$ be the set of natural numbers for which $T(n)$ is true. By the hypothesis ${1\in M}$, and if ${k\in M}$, then ${k+1\in M}$. By the induction axiom $M$ contains all natural numbers, that is, $T(n)$ is true for every natural $n$.

So a proof by induction has three stages:

Base case: we check that the statement is true for ${n=1}$.
Inductive step: we assume that it is true for some ${n=k}$ (the inductive hypothesis) and prove that it is also true for ${n=k+1}$.
Conclusion: by the principle of mathematical induction the statement is true for every natural $n$. It is true for ${n=1}$, therefore also for ${n=2}$, then also for ${n=3}$, and so on.

Both the base case and the step are needed. Let $T(n)$ be the statement "the number ${n^2+n}$ is odd". The step is true: if ${k^2+k}$ is odd, then ${(k+1)^2+(k+1)}={(k^2+k)+2(k+1)}$ is odd too. The base case, however, is false (${1^2+1=2}$), and in fact ${n^2+n=n(n+1)}$ is even for every $n$.

Examples

Example 1. Prove that

${S_n}={1\cdot 2\cdot 3+2\cdot 3\cdot 4+\dots}+{n(n+1)(n+2)}={\frac{n(n+1)(n+2)(n+3)}{4}}$.

Base case. For ${n=1}$ the left side is ${S_1=1\cdot 2\cdot 3=6}$, and the right side is ${\frac{1\cdot 2\cdot 3\cdot 4}{4}=6}$.

Step. Assume that the formula is true for ${n=k}$, that is, ${S_k}={\frac{k(k+1)(k+2)(k+3)}{4}}$. Then

${S_{k+1}}={S_k}+{(k+1)(k+2)(k+3)}={\frac{k(k+1)(k+2)(k+3)}{4}}+{(k+1)(k+2)(k+3)}={\frac{(k+1)(k+2)(k+3)(k+4)}{4}}$,

because ${\frac{k}{4}+1=\frac{k+4}{4}}$. This is the formula for ${n=k+1}$.

Conclusion. The formula is true for ${n=1}$, and its truth for ${n=k}$ implies its truth for ${n=k+1}$. By the principle of mathematical induction it is true for every natural $n$.

Example 2. Prove that for every natural $n$ the number ${11^{n+2}+12^{2n+1}}$ is divisible by 133.

Base case. For ${n=1}$: ${11^3+12^3}={1331+1728}={3059}={133\cdot 23}$.

Step. Let ${11^{k+2}+12^{2k+1}=133p}$, where $p$ is an integer. Since ${144=11+133}$,

${11^{k+3}+12^{2k+3}}={11\cdot 11^{k+2}}+{144\cdot 12^{2k+1}}={11\left(11^{k+2}+12^{2k+1}\right)}+{133\cdot 12^{2k+1}}={133\left(11p+12^{2k+1}\right)}$.

Conclusion. The expression is divisible by 133 for ${n=1}$, and if it is divisible for ${n=k}$, it is also divisible for ${n=k+1}$. Therefore it is divisible by 133 for every natural $n$.

Example 3. Prove that the set ${M_n=\{a_1,a_2,\dots,a_n\}}$ has $2^n$ subsets.

Base case. For ${n=1}$ the set ${M_1=\{a_1\}}$ has two subsets: the empty set and $M_1$ itself. Their number is ${2^1}$.

Step. Assume that ${M_k=\{a_1,\dots,a_k\}}$ has $2^k$ subsets, and consider ${M_{k+1}}={\{a_1,\dots,a_k,a_{k+1}\}}$. The subsets of $M_{k+1}$ that do not contain $a_{k+1}$ are exactly the subsets of $M_k$, so there are $2^k$ of them. The subsets that contain $a_{k+1}$ are obtained by adding $a_{k+1}$ to each subset of $M_k$, so there are also $2^k$ of them. In total ${2^k+2^k=2\cdot 2^k=2^{k+1}}$.

Conclusion. By the principle of mathematical induction $M_n$ has $2^n$ subsets for every natural $n$.

Induction Starting from ${n=m}$

In applications the following form of the principle is also often used.

Let $m$ be a natural number. If the statement $T(m)$ is true and, for every ${k\ge m}$, the truth of $T(k)$ implies the truth of ${T(k+1)}$, then $T(n)$ is true for every natural ${n\ge m}$.

Here the base case is a check of the statement for ${n=m}$.

Example 4. Prove that ${2^n\gt 2n+1}$ for every natural ${n\ge 3}$.

Base case. For ${n=3}$: ${2^3=8\gt 7=2\cdot 3+1}$. (For ${n=2}$ the inequality is false: ${2^2=4\lt 5}$.)

Step. Let ${2^k\gt 2k+1}$ for some ${k\ge 3}$. We will prove that ${2^{k+1}\gt 2(k+1)+1}$. Besides the inductive hypothesis we also use ${2^k\gt 2}$:

${2^{k+1}}={2^k+2^k}\gt{(2k+1)+2}={2(k+1)+1}$.

Conclusion. By the principle of mathematical induction (the last form) ${2^n\gt 2n+1}$ for every natural ${n\ge 3}$.

Conjecture and Proof

In research we often first have to discover the pattern, state a claim about it and only then prove it for every natural $n$. In that case we use incomplete induction to form a conjecture from particular cases, and then mathematical induction to prove it. There are three stages:

experiment and observation;
forming a conjecture;
proving the conjecture.

Example 5. Find the sum of the first $n$ odd numbers.

The problem asks for a shorter formula for the sum ${S_n}={1+3+5+\dots}+{(2n-1)}$ than adding the terms directly.

First stage. We compute $S_n$ for several consecutive values of $n$: ${S_1=1}$, ${S_2=1+3=4}$, ${S_3=1+3+5=9}$, ${S_4=1+3+5+7=16}$, and so on:

$n$	1	2	3	4	5	6
$S_n$	1	4	9	16	25	36

We look for a rule that gives each number in the second row from the number above it. We notice that ${S_1=1^2}$, ${S_2=2^2}$, ${S_3=3^2}$, ${S_4=4^2}$, ${S_5=5^2}$ and ${S_6=6^2}$.

Second stage. The rule holds for ${n=1,2,\dots,6}$, and it is natural to conjecture that it holds for every $n$:

${1+3+5+\dots}+{(2n-1)}={n^2}$.

Finding such a conjecture depends on our ability to observe, to guess and to test our guesses, on our experience with similar problems and on analogies with problems we already know.

Third stage. We prove the conjecture by mathematical induction. For ${n=1}$ it is true: ${S_1=1=1^2}$. Let ${S_k=k^2}$. Then

${S_{k+1}}={S_k+(2k+1)}={k^2+2k+1}={(k+1)^2}$.

By the principle of mathematical induction ${S_n=n^2}$ for every natural $n$, that is, the conjecture is true.

Here we deliberately split the solution into three stages so that its path is clearly visible. In practice the stages naturally merge into one another.

Problems

In problems 1–6 prove that the statement is true for every natural $n$.

1. ${\frac{1}{1\cdot 3}+\frac{1}{3\cdot 5}+\frac{1}{5\cdot 7}+\dots}+{\frac{1}{(2n-1)(2n+1)}}={\frac{n}{2n+1}}$

Base case: ${\frac{1}{1\cdot 3}=\frac{1}{3}=\frac{1}{2\cdot 1+1}}$.

Step: ${\frac{k}{2k+1}}+{\frac{1}{(2k+1)(2k+3)}}={\frac{2k^2+3k+1}{(2k+1)(2k+3)}}={\frac{(2k+1)(k+1)}{(2k+1)(2k+3)}}={\frac{k+1}{2k+3}}$.

2. ${\frac{1}{1\cdot 4}+\frac{1}{4\cdot 7}+\frac{1}{7\cdot 10}}+{\dots+\frac{1}{(3n-2)(3n+1)}}={\frac{n}{3n+1}}$

Base case: ${\frac{1}{1\cdot 4}=\frac{1}{4}=\frac{1}{3\cdot 1+1}}$.

Step: ${\frac{k}{3k+1}}+{\frac{1}{(3k+1)(3k+4)}}={\frac{3k^2+4k+1}{(3k+1)(3k+4)}}={\frac{(3k+1)(k+1)}{(3k+1)(3k+4)}}={\frac{k+1}{3k+4}}$.

3. ${\frac{1}{a(a+1)}}+{\frac{1}{(a+1)(a+2)}}+{\dots+\frac{1}{(a+n-1)(a+n)}}={\frac{n}{a(a+n)}}$, where ${a\gt 0}$

Base case: for ${n=1}$ both sides are equal to ${\frac{1}{a(a+1)}}$.

Step: ${\frac{k}{a(a+k)}}+{\frac{1}{(a+k)(a+k+1)}}={\frac{k(a+k+1)+a}{a(a+k)(a+k+1)}}={\frac{(a+k)(k+1)}{a(a+k)(a+k+1)}}={\frac{k+1}{a(a+k+1)}}$, because ${ka+k^2+k+a}={(a+k)(k+1)}$.

4. ${2^{3n}-7n-1}$ is divisible by 49

${2^{3n}=8^n}$. Base case: ${8-7-1=0}$ is divisible by 49.

Step: ${8^{k+1}-7(k+1)-1}={8\left(8^k-7k-1\right)+49k}$. Both terms are divisible by 49.

5. ${2^{2n}+15n-1}$ is divisible by 9

${2^{2n}=4^n}$. Base case: ${4+15-1=18=9\cdot 2}$.

Step: ${4^{k+1}+15(k+1)-1}={4\left(4^k+15k-1\right)}-{9(5k-2)}$. Both terms are divisible by 9.

6. ${2^{n+2}\cdot 3^n+5n-4}$ is divisible by 25

Let ${A_n=2^{n+2}\cdot 3^n+5n-4}$. Base case: ${A_1=8\cdot 3+5-4=25}$.

Step: ${A_{k+1}}={6\cdot 2^{k+2}\cdot 3^k+5k+1}={6A_k-25(k-1)}$, and $6A_k$ and ${25(k-1)}$ are divisible by 25.

In problems 7–10 find the sum. Compute it for several values of $n$, state a conjecture and prove it by induction.

7. ${1+2+3+\dots+n}$

${\frac{n(n+1)}{2}}$. Step: ${\frac{k(k+1)}{2}+(k+1)}={\frac{(k+1)(k+2)}{2}}$.

8. ${2+4+6+\dots+2n}$

${n(n+1)}$. Step: ${k(k+1)+2(k+1)}={(k+1)(k+2)}$.

9. ${1\cdot 2+2\cdot 3+3\cdot 4}+{\dots+n(n+1)}$

${\frac{n(n+1)(n+2)}{3}}$. Step: ${\frac{k(k+1)(k+2)}{3}}+{(k+1)(k+2)}={\frac{(k+1)(k+2)(k+3)}{3}}$.

10. ${\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}}+{\dots+\frac{1}{n(n+1)}}$

The sums are ${\frac{1}{2}}$, ${\frac{2}{3}}$, ${\frac{3}{4}}$, …, so the conjecture is ${\frac{n}{n+1}}$. Step: ${\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}}={\frac{k^2+2k+1}{(k+1)(k+2)}}={\frac{k+1}{k+2}}$.