# 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*:

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

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

and so on.

### A Special Case

The following case is seen often:

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:

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

Solution:

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

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

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

### Problem 2

Prove for all natural numbers *n* that *x ^{n} - y^{n}* is divisible by

*x - y*, for all integers

*x*and

*y*.

Solution:

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

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

From the sum of powers formula, *Q* is an integer. Since *Q + y ^{n}* is an integer, this satisfies P(

*n*+ 1). Therefore, we have proven the claim

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

### 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

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

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

Solution:

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

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

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

then consider two cases:

*n*+ 1 is odd. Then, P(n + 1) by the second claim.*n*+ 1 is even. Then, since- therefore P((
*n*+ 1) / 2) by the inductive hypothesis, and P(*n*+ 1) by the first claim.

We have now proven

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