Mathematical Induction

Mathematical induction is a proof technique used to prove that a statement is true for all natural numbers. Despite being commonly perceived as difficult to apply, it is actually a simple technique based on a logical inference rule. Like all techniques, practice makes proficiency.

Form

Recall the inference rule known as modus ponens:

$a\rightarrow b$

$a$

$\therefore b$

Now suppose we have a property P(n) for a natural number n. First, prove the claim

$P(n)\rightarrow P(f(n))$

where f(n) is some function on n. The left-hand side of the claim is called the inductive hypothesis.

Then, prove P(n) for n = x. This is called a base premise.

Then, apply modus ponens, resulting in

$P(n)\rightarrow P(f(n))$

$P(x)$

$\therefore P(f(x))$

$\therefore P(f(f(x)))$

and so on.

A Special Case

The following case is seen often:

$P(n)\rightarrow P(n+1)$

$P(x)$

$\therefore P(x+1)$

$\therefore P(x+2)$

and so on. This simply proves P(n) for all n greater than or equal to x.

Strong Induction

Sometimes, the inductive hypothesis can be changed in order to express proofs more elegantly. One such change is the following:

$P(k){\text{ for all }}k{\text{ such that }}c\leq k\leq n\rightarrow P(n+1)$

$P(k){\text{ for all }}k{\text{ such that }}c\leq k\leq x$

$\therefore P(x+1)$

$\therefore P(x+2)$

and so on. Here, we prove P(n) for all n greater or equal to c. This is called "strong induction" because its hypothesis is stricter, or stronger.

Note that "all" is taken to mean all possible values within the domain of the problem.

Final Thoughts

All proofs using induction consist of a proof of an inductive claim and one or more proofs of base premises. Other claims can support the inductive claim, if needed. Examples will follow.

Examples

Problem 1

Prove for all natural numbers n that

$1+2+3+\cdots +n={\frac {n(n+1)}{2}}$

Solution:

Let P(n) be the above property. If P(n), then

${\begin{aligned}1+2+3+\cdots +n+(n+1)&={\frac {n(n+1)}{2}}+(n+1)\\&={\frac {n(n+1)+2(n+1)}{2}}\\&={\frac {(n+1)(n+2)}{2}}\\&={\frac {(n+1)((n+1)+1)}{2}}\\\end{aligned}}$

This satisfies P(n + 1). Therefore, we have proven the claim

$P(n)\rightarrow P(n+1)$

Now let n = 1. By substitution, the property holds true. It follows that the property holds true for all natural numbers. $\blacksquare$

Problem 2

Prove for all natural numbers n that xⁿ - yⁿ is divisible by x - y, for all integers x and y.

Solution:

Let P(n) be the above property, formally written

$x^{n}-y^{n}=k(x-y)$

for some integer k. If P(n), then

${\begin{aligned}x^{n+1}-y^{n+1}&=x^{n+1}-xy^{n}+xy^{n}-y^{n+1}\\&=x(x^{n}-y^{n})+y^{n}(x-y)\\&=Q(x-y)+y^{n}(x-y)\\&=(Q+y^{n})(x-y)\\\end{aligned}}$

From the sum of powers formula, Q is an integer. Since Q + yⁿ is an integer, this satisfies P(n + 1). Therefore, we have proven the claim

$P(n)\rightarrow P(n+1)$

Now let n = 1. By substitution, the property holds true. It follows that the property holds true for all natural numbers. $\blacksquare$

Problem 3

Suppose only two kinds of coins existed, having 3 and 5 units of value. Prove that it is possible to make values of all natural numbers greater than 7 using just these coins.

Solution:

This can be proven using strong induction. Let P(n) be the property that it is possible to make a value of n. We note that when

n = 8, we can make 8 units using 3, 5.

n = 9, we can make 9 units using 3, 3, 3.

n = 10, we can make 10 units using 5, 5.

Therefore, we have

$P(k){\text{ for all }}k{\text{ such that }}8\leq k\leq n$

for n = 10. We can add a 3-unit coin to n - 2, giving n + 1. Thus

$P(k){\text{ for all }}k{\text{ such that }}8\leq k\leq n\rightarrow P(n+1)$

Therefore, P(n) for all natural numbers n greater than 7.

Problem 4

Without using the fundamental theorem of arithmetic, prove that for every natural number n there exists an integer x and an odd integer y such that

$n=2^{x}y$

Solution:

Let P(n) be the above property. If P(n), then

${\begin{aligned}2n&=2\cdot 2^{x}y\\&=2^{x+1}y\\\end{aligned}}$

Since x + 1 is also an integer, this satisfies P(2n). Therefore, we have proven the claim

$P(n)\rightarrow P(2n)$

Let n be any odd integer. Then, letting x = 0 and y = n satisfies P(n). Therefore, we have proven the claim that P(n) for all odd integers n.

Now, we use strong induction to complete the proof. If

$P(k){\text{ for all }}k{\text{ such that }}1\leq k\leq n$

then consider two cases:

n + 1 is odd. Then, P(n + 1) by the second claim.

n + 1 is even. Then, since

$1\leq {\frac {n+1}{2}}\leq n$

therefore P((n + 1) / 2) by the inductive hypothesis, and P(n + 1) by the first claim.

We have now proven

$\forall k\;(1\leq k\leq n):P(n)\rightarrow P(n+1)$

Since P(1), it follows that the property holds true for all natural numbers. $\blacksquare$