THE NATURAL NUMBERSare the counting numbers: 1, 2, 3, 4, etc.Mathematical inductionis a technique for proving a statement -- a theorem, or a formula -- that is asserted abouteverynatural number.

By "every", or "all," natural numbers, we mean any one that we might possibly name.

For example,

1 + 2 + 3 + . . . +n= ½n(n+ 1).

This asserts that the sum of consecutive numbers from 1 tonis given by the formula on the right. We want to prove that this will be true forn=1,n= 2,n= 3, and so on. Now we can test the formula for anygivennumber, sayn= 3:

1 + 2 + 3 = ½·3·4 = 6

-- which is true. It is also true forn= 4:

1 + 2 + 3 + 4 = ½·4·5 = 10.

But how are we to prove this rule foreveryvalue ofn?

Themethod of proof is the following. It is called theprinciple of mathematical induction.

If

1) when a statement is true for a natural numbern=k,
then it will also be true for its successor,n=k+ 1;

and

2) the statement is true forn= 1;

then the statement will be true for every natural numbern.

To prove a statement by induction, we must prove parts 1) and2) above. For, when the statement is true forn= 1, then according to1), it will also be true for 2. But that implies it will be true for 3; which implies it will be true for 4. And so on. It will be true for any natural number that we might name.

Thehypothesisof Step 1) -- "The statement is true for n = k" -- is called theinduction assumption, or theinduction hypothesis. It is what weassumewhen we prove a theorem by induction.

Example 1. Prove that the sum of the firstnnatural numbers is given by this formula:

1 + 2 + 3 + . . . +n = n(n+ 1)
2 .

Proof. We will doSteps 1) and 2)above. First, we willassumethat the formula is true forn=k; that is, we will assume:

1 + 2 + 3 + . . . +k = k(k+ 1)
2 . (1)

This is the induction assumption. Assuming this, we must prove that the formula is true for its successor,n=k+ 1. That is, we must show:

1 + 2 + 3 + . . . + (k+ 1) = (k+ 1)(k+ 2)
2 . (2)

To do that, we will simply add thenext term(k+ 1)to both sides of the induction assumption,line (1):

[Induction]

This isline (2), which is the first thing we wanted to show.

Next, we must show that theformulais true forn= 1. We have:

1 = ½·1·2

-- which is true. We have now fulfilled both conditions of theprinciple of mathematical induction. The formula is therefore true for every natural number.

(In theAppendixto Arithmetic, we will establish that formula directly.)

Example 2.Prove that this rule of exponents is true for every natural numbern:

(ab)n=anbn.

Proof. Again, we begin byassumingthat it is true forn=k; that is, we assume:

(ab)k=akbk. . . . . . . . (3)

With this assumption, we must show that the rule is true for its successor,n=(k+1). We must show:

(ab)k+ 1=ak+ 1bk+ 1. . . . . . . (4)

(When using mathematical induction, the student should always write exactly what is to be shown.)

Now, given the assumption, line (3), how can we produce line (4) from it ?

Simply by multiplying both sides of line (3) byab:

(ab)kab = akbkab

= akabkb

since the order of factors does not matter,

= ak+ 1bk+ 1.

This isline (4), which is what we wanted to show.

So, we have shown that if the theorem is true for any specific natural numberk, then it is also true for its successor,k+ 1.

Next, we must show that the rule is true forn= 1; that is, that

(ab)1 = a1b1.

But (ab)1=ab; anda1b1=ab.

This rule is therefore true for every natural numbern.

Example 3. Thesumof consecutive cubes.Prove this remarkable fact of arithmetic:

13+ 23+ 33+ . . . +n3= (1 + 2 + 3 + . . . +n)2.

"The sum ofnconsecutive cubes is equal to thesquare
of the sum of the firstnnumbers."

In other words, according toExample 1:

13+ 23+ 33+ . . . +n3 = n2(n+ 1)2
4

Proof.For convenience, we will denote the sum up tonbyS(n). We assume, then, that the formula is true forn=k; that is, that

S(k) = k2(k+ 1)2
4 (1)

We must now show that the formula is also true forn=k+ 1; that

S(k+ 1) = (k+ 1)2(k+ 2)2
4 (2)

To do that, add the next cube toS(k),line (1):

S(k+ 1) = S(k) + (k+ 1)3

= k2(k+ 1)2
4 + (k+ 1)3

= k2(k+ 1)2+ 4(k+ 1)3
4

= (k+ 1)2[k2+ 4(k+ 1)]
4

-- on taking (k+ 1)2as a common factor,

= (k+ 1)2(k2+ 4k+ 4)
4

= (k+ 1)2(k+ 2)2
4

This isline (2), which is what we wanted to show.

Finally, we must show that theformulais true forn= 1.

13 = 12·22
4

1 = 1·4
4

-- which is true. The formula therefore is true for every natural number.

In theAppendixto Arithmetic, we will show directly that that is true.

Problem 1.According to the principle of mathematical induction, to prove a statement that is asserted about every natural numbern, there are two things to prove.

a) What is the first?

To see the answer, pass your mouse over the colored area.
To cover the answer again, click "Refresh" ("Reload").

Ifthe statement is true forn = k, then it will be true for its successor,k+ 1.

b) What is the second?

The statement is true forn= 1.

c) Part a) contains theinduction assumption. What is it?

The statement is true forn=k.

Problem 2.LetS(n) = 2n− 1. Evaluate

a) S(k)= 2k− 1

b) S(k+ 1)= 2(k+ 1) − 1 = 2k+ 2 − 1 = 2k + 1

Problem 3.The sum of the first n odd numbers is equal to the nth square.

1 + 3 + 5 + 7 + . . . + (2n− 1) =n2.

a) To prove that by mathematical induction, what will be the induction
a)assumption?

The statement is true forn=k:

1 + 3 + 5 + 7 + . . . + (2k− 1) =k2.

b) On the basis of this assumption, what must we show?

The statement is true for its successor,k+ 1:

1 + 3 + 5 + 7 + . . . + (2k− 1) +2k+ 1= (k+ 1)2.

c) Show that.

On adding 2k+ 1 to both sides of the induction assumption:

1 + 3 + 5 + 7 + . . . + (2k− 1) +2k+ 1 = k2+2k+ 1

= (k+ 1)2

d) To complete the proof by mathematical induction, what must we
a)show?

The statement is true forn= 1.

e) Show that.

1 = 12

Problem 4.Proveby mathematical induction:

[Induction]

If we denote that sum byS(n), then assume that the formula is true forn=k; that is, assume

S(k) = k
2k+ 1 .

Now show that the formula is true forn=k+ 1; that is, show:

S(k+ 1) = k+ 1
2k+ 3 .

Begin:

S(k+ 1) = S(k) + Thenext term, whose denominator
is the product of thenextodd numbers.

= [Induction]

= [Induction]

= [Induction]

= [Induction]

= [Induction]

Next,

The formula is true forn= 1:

[Induction]

Therefore it is true for all natural numbers.