# Mathematical Induction

### Text-only Preview

000.3 - Mathematical Induction

c 2010 Treasure Trove of Mathematics

Mathematical induction is a method of mathematical proof typically used to

establish that a given statement is true of all natural numbers (non-negative

integers).1 It is done by proving that the ﬁrst statement in the inﬁnite se-

quence of statements is true, and then proving that if any one statement in

the inﬁnite sequence of statements is true, then so is the next one.

Mathematical induction should not be misconstrued as a form of inductive

reasoning, which is considered non-rigorous in mathematics. In fact, math-

ematical induction is a form of rigorous deductive reasoning.

1

Introduction

The natural numbers, N, is the set of all non-negative integers:

N = {0, 1, 2, 3, . . .}.

Very often we want to prove some mathematical statement involving every

member of N. The simplest and most common form of mathematical in-

duction proves that a statement involving a natural number n holds for all

values of n. The proof consists of two steps:

1. The basis (base case): showing that the statement holds when n is

equal to the lowest value that n is given in the question. Usually,

n = 0 or n = 1.

2. The inductive step: showing that if the statement holds for some n,

then the statement also holds when n + 1 is substituted for n.

The assumption in the inductive step that the statement holds for some

n is called the induction hypothesis (or inductive hypothesis). To perform

1This document may be freely distributed, but not altered.

1

the inductive step, one assumes the induction hypothesis and then uses this

assumption to prove the statement for n + 1.

The choice between n = 0 and n = 1 in the base case is speciﬁc to the

context of the proof: If 0 is considered a natural number, as is common in

the ﬁelds of combinatorics and mathematical logic, then n = 0. If, on the

other hand, 1 is taken as the ﬁrst natural number, then the base case is

given by n = 1.

This method works by ﬁrst proving the statement is true for a starting

value, and then proving that the process used to go from one value to the

next is valid. If these are both proven, then any value can be obtained by

performing the process repeatedly. It may be helpful to think of the domino

eﬀect; if one is presented with a long row of dominoes standing on end, one

can be sure that:

1. The ﬁrst domino will fall.

2. Whenever a domino falls, its next neighbor will also fall.

So it is concluded that all of the dominoes will fall, and that this fact is

inevitable. Consider the following statement:

n(n + 1)

0 + 1 + 2 + 3 + · · · + n =

(1)

2

for every n ≥ 0. Suppose that the statement happens to be true for a

particular value of n, say n = k. Then we have:

k(k + 1)

0 + 1 + 2 + 3 + · · · + k =

.

(2)

2

We want to start from here, and convince ourselves that the statement is

also true for the next value, n = k + 1. Plug k + 1 into (1),

(k + 1)(k + 2)

0 + 1 + 2 + 3 + · · · + k + (k + 1) =

.

(3)

2

Notice that the left-hand side of (3) is the same as the left-hand side of (2)

except that there is an extra k + 1 added to it. So if (2) is true, then we can

add k + 1 to both sides of it to get:

2

k(k + 1)

0 + 1 + 2 + 3 + · · · + k + (k + 1)

=

+ (k + 1)

2

k(k + 1) + 2(k + 1)

=

2

(k + 1)(k + 2)

=

2

showing that (3) is true if (2) is true. To complete the proof, we need only

conﬁrm the base case. To do so, simply plug n = 0 into the original equation

and verify the equality.

2

Formal Deﬁnition of Induction

Let S(n) be any statement about a natural number n. If S(0) is true and,

if S(k) is true then S(k + 1) is also true, then S(n) is true for every n ∈ N.

3

Examples

1. Show that

n(n + 1)(2n + 1)

02 + 12 + 22 + · · · + n2 =

.

6

Solution. If n = 0 we have the trivial case:

02 = 0(1)(1)/6.

Assume that the equation is true for n = k:

k(k + 1)(2k + 1)

02 + 12 + · · · + k2 =

.

(4)

6

From (4), we want to show that:

(k + 1)((k + 1) + 1)(2(k + 1) + 1)

02 + 12 + · · · + k2 + (k + 1)2

=

6

(k + 1)(k + 2)(2k + 3)

=

6

Begin with (4) and add (k + 1)2 to both sides:

k(k + 1)(2k + 1)

02 + 12 + · · · + k2 + (k + 1)2 =

+ (k + 1)2

6

3

Now just rearrange to complete the proof:

k(k + 1)(2k + 1) + 6(k + 1)2

02 + 12 + · · · + (k + 1)2 =

6

(k + 1)(2k2 + k + 6k + 6)

02 + 12 + · · · + (k + 1)2

=

6

(k + 1)(k + 2)(2k + 3)

=

6

2. Let Fk be the Fibonacci numbers deﬁned by: F0 = 0, F1 = 1, and if

k > 1, Fk = Fk−1 + Fk−2. Show that:

Fn−1Fn+1 = F 2

n + (−1)n

and that

n

F 2

i = FnFn+1

i=0

Solution. Part 1:

First check for n = 1:

F0F2 = 0 · 2 = 0 = F 2

1 + (−1)1 = 1 − 1 = 0.

If we assume it is true for n = k, we have:

Fk−1Fk+1 = F 2

k + (−1)k .

(5)

From (5), we need to show that the equality continues to hold for

n = k + 1, i.e., we need to show that if we start with (5) we can show

that:

FkFk+2 = F 2

k+1 + (−1)k+1.

Since Fk+2 = Fk + Fk+1, the equation above is equivalent to:

Fk(Fk + Fk+1) = F 2

k+1 + (−1)k+1.

or to

F 2

k + Fk Fk+1 = F 2

k+1 + (−1)k+1.

Substitute F 2 from the right-hand side of (5):

k

Fk−1Fk+1 − (−1)k + FkFk+1 = F 2

k+1 + (−1)k+1

4

or

Fk+1(Fk−1 + Fk) = F 2

k+1 + (−1)k+1 + (−1)k = F 2

k+1

or

F 2

k+1 = F 2

k+1

Part 2:

For n = 0:

0

F 2

i = F 2

0 = 0 = F0F1 = 0 · 1 = 0

i=0

If it is true for n = k:

k

F 2

i = Fk Fk+1

(6)

i=0

then we can F 2

to both sides of (6) to get:

k+1

k+1

F 2

i = Fk Fk+1 + F 2

k+1 = Fk+1(Fk + Fk+1) = Fk+1Fk+2

i=0

3. Show that:

1

1

1

√

1 + √ + √ + · · · + √

≤ 2 n.

2

3

n

Solution. For the n = 1 case we have

√

1 ≤ 2 1 = 2.

Assume the equation is true for n = k:

1

1

1

√

1 + √ + √ + · · · + √

≤ 2 k.

2

3

k

√

To show it is also true for n = k + 1, add 1/ k + 1 to both sides:

1

1

1

√

1

1 + √ + · · · + √ + √

≤ 2 k + √

.

2

k

k + 1

k + 1

Thus if we can show that

√

1

√

2 k + √

≤ 2 k + 1

k + 1

5

√

then the proof is complete. Multiply both sides by

k + 1 and then

square both sides to obtain:

4k(k + 1) + 4

k(k + 1) + 1 ≤ 4(k2 + 2k + 1).

4

k(k + 1) ≤ 4k + 3

Squaring again:

16k2 + 16k ≤ 16k2 + 24k + 9

which is always true.

4. Show that:

2! · 4! · 6! · · · (2n)! ≥ ((n + 1)!)n.

Solution. First show it is true for n = 1:

2! = 2 ≥ (2!)1 = 2.

Next assume it is true for n = k:

2! · 4! · 6! · · · (2k)! ≥ ((k + 1)!)k.

(7)

If we multiply both sides of (7) by (2(k + 1))!, we get:

2! · 4! · · · (2k)! · (2k + 2)! ≥ ((k + 1)!)k · (2k + 2)!.

If it can be shown that the right-hand side of the equation above is

larger than ((k + 2)!)k+1, the proof is complete. The term (2k + 2)! on

the right-hand side can be written:

(2k + 2)! = (2k + 2)(2k + 1)(2k) · · · (k + 3)(k + 2)!

This consists of k terms, all greater than k + 2, multiplied by (k + 2)!,

so

((k + 1)!)k(2k + 2)!

>

((k + 1)!)k(k + 2)k(k + 2)!

=

((k + 2)!)k(k + 2)! = ((k + 2)!)k+1

6

5. Show that:

√

π

2 +

2 +

2 + · · · +

2 = 2 cos 2n+1

where there are n 2s in the expression on the left.

Solution. For n = 1 case we have:

√

π

√

√

2 = 2 cos

= 2 cos π/4 = 2 2/2 =

2.

22

Now assume it is true for k nested square roots:

√

π

2 +

2 +

2 + · · · +

2 = 2 cos

.

2k+1

Add 2 to both sides and take the square root, so the LHS will have

k + 1 nested square roots, and the right hand side will be:

π

2 + 2 cos

.

(8)

2k+1

All we need to show is that the value above is equal to

π

2 cos

.

(9)

2k+2

We know that for any angle θ we have:

1 + cos 2θ

cos θ =

.

(10)

2

Substitute π/2k+2 for θ in 10 and the equality of 8 and 9 becomes

immediately obvious.

4

References

1. H. Amann, J. Esher, Analysis 1, Birkhauser Basel; 1st edition, 2010.

2. H. Amann, J. Esher, Analysis 2, Birkhauser Basel; 1st edition, 2008.

3. H. Amann, J. Esher, Analysis 3, Birkhauser Basel; 1st edition, 2009.

4. S. Lay, Analysis: With an Introduction to Proof, Prentice Hall; 4th

edition, 2004.

7

5. S. Hedman, A First course in Logic: An Introduction to Model The-

ory, Proof Theory, Computability, and Complexity, Oxford University

Press; 2004.

6. R. Larson, B. Edwards, Calculus, Brooks Cole; 9th edition, 2009.

7. R. Larson, R. Hostetler, B. Edwards, Calculus (With Analytic Geom-

etry), Brooks Cole; 8th edition, 2005.

8. M. Lial, J. Hornsby, D. Schneider, College Algebra, Addison Wesley;

10th edition, 2008.

9. C. Mckeague, M. Turner, Trigonometry, Brooks Cole; 6th edition,

2007.

10. M. Lial, J. Hornsby, D. Schneider, Trigonometry, Addison Wesley; 9th

edition, 2008.

11. R. Larson, Trigonometry, Brooks Cole; 8th edition, 2010.

12. R. Moyer, F. Ayres, Schaum’s Outline of Trigonometry, McGraw-Hill;

4th edition, 2008.

13. G.F. Simmons, Precalculus Mathematics in a Nutshell, Wipf & Stock

Publishers; 2003.

14. M. Sullivan, Trigonometry: A Unit Circle Approach, Prentice Hall;

8th edition, 2007.

15. R. Larson, Algebra and Trigonometry, Brooks Cole; 5th edition, 2000.

8

c 2010 Treasure Trove of Mathematics

Mathematical induction is a method of mathematical proof typically used to

establish that a given statement is true of all natural numbers (non-negative

integers).1 It is done by proving that the ﬁrst statement in the inﬁnite se-

quence of statements is true, and then proving that if any one statement in

the inﬁnite sequence of statements is true, then so is the next one.

Mathematical induction should not be misconstrued as a form of inductive

reasoning, which is considered non-rigorous in mathematics. In fact, math-

ematical induction is a form of rigorous deductive reasoning.

1

Introduction

The natural numbers, N, is the set of all non-negative integers:

N = {0, 1, 2, 3, . . .}.

Very often we want to prove some mathematical statement involving every

member of N. The simplest and most common form of mathematical in-

duction proves that a statement involving a natural number n holds for all

values of n. The proof consists of two steps:

1. The basis (base case): showing that the statement holds when n is

equal to the lowest value that n is given in the question. Usually,

n = 0 or n = 1.

2. The inductive step: showing that if the statement holds for some n,

then the statement also holds when n + 1 is substituted for n.

The assumption in the inductive step that the statement holds for some

n is called the induction hypothesis (or inductive hypothesis). To perform

1This document may be freely distributed, but not altered.

1

the inductive step, one assumes the induction hypothesis and then uses this

assumption to prove the statement for n + 1.

The choice between n = 0 and n = 1 in the base case is speciﬁc to the

context of the proof: If 0 is considered a natural number, as is common in

the ﬁelds of combinatorics and mathematical logic, then n = 0. If, on the

other hand, 1 is taken as the ﬁrst natural number, then the base case is

given by n = 1.

This method works by ﬁrst proving the statement is true for a starting

value, and then proving that the process used to go from one value to the

next is valid. If these are both proven, then any value can be obtained by

performing the process repeatedly. It may be helpful to think of the domino

eﬀect; if one is presented with a long row of dominoes standing on end, one

can be sure that:

1. The ﬁrst domino will fall.

2. Whenever a domino falls, its next neighbor will also fall.

So it is concluded that all of the dominoes will fall, and that this fact is

inevitable. Consider the following statement:

n(n + 1)

0 + 1 + 2 + 3 + · · · + n =

(1)

2

for every n ≥ 0. Suppose that the statement happens to be true for a

particular value of n, say n = k. Then we have:

k(k + 1)

0 + 1 + 2 + 3 + · · · + k =

.

(2)

2

We want to start from here, and convince ourselves that the statement is

also true for the next value, n = k + 1. Plug k + 1 into (1),

(k + 1)(k + 2)

0 + 1 + 2 + 3 + · · · + k + (k + 1) =

.

(3)

2

Notice that the left-hand side of (3) is the same as the left-hand side of (2)

except that there is an extra k + 1 added to it. So if (2) is true, then we can

add k + 1 to both sides of it to get:

2

k(k + 1)

0 + 1 + 2 + 3 + · · · + k + (k + 1)

=

+ (k + 1)

2

k(k + 1) + 2(k + 1)

=

2

(k + 1)(k + 2)

=

2

showing that (3) is true if (2) is true. To complete the proof, we need only

conﬁrm the base case. To do so, simply plug n = 0 into the original equation

and verify the equality.

2

Formal Deﬁnition of Induction

Let S(n) be any statement about a natural number n. If S(0) is true and,

if S(k) is true then S(k + 1) is also true, then S(n) is true for every n ∈ N.

3

Examples

1. Show that

n(n + 1)(2n + 1)

02 + 12 + 22 + · · · + n2 =

.

6

Solution. If n = 0 we have the trivial case:

02 = 0(1)(1)/6.

Assume that the equation is true for n = k:

k(k + 1)(2k + 1)

02 + 12 + · · · + k2 =

.

(4)

6

From (4), we want to show that:

(k + 1)((k + 1) + 1)(2(k + 1) + 1)

02 + 12 + · · · + k2 + (k + 1)2

=

6

(k + 1)(k + 2)(2k + 3)

=

6

Begin with (4) and add (k + 1)2 to both sides:

k(k + 1)(2k + 1)

02 + 12 + · · · + k2 + (k + 1)2 =

+ (k + 1)2

6

3

Now just rearrange to complete the proof:

k(k + 1)(2k + 1) + 6(k + 1)2

02 + 12 + · · · + (k + 1)2 =

6

(k + 1)(2k2 + k + 6k + 6)

02 + 12 + · · · + (k + 1)2

=

6

(k + 1)(k + 2)(2k + 3)

=

6

2. Let Fk be the Fibonacci numbers deﬁned by: F0 = 0, F1 = 1, and if

k > 1, Fk = Fk−1 + Fk−2. Show that:

Fn−1Fn+1 = F 2

n + (−1)n

and that

n

F 2

i = FnFn+1

i=0

Solution. Part 1:

First check for n = 1:

F0F2 = 0 · 2 = 0 = F 2

1 + (−1)1 = 1 − 1 = 0.

If we assume it is true for n = k, we have:

Fk−1Fk+1 = F 2

k + (−1)k .

(5)

From (5), we need to show that the equality continues to hold for

n = k + 1, i.e., we need to show that if we start with (5) we can show

that:

FkFk+2 = F 2

k+1 + (−1)k+1.

Since Fk+2 = Fk + Fk+1, the equation above is equivalent to:

Fk(Fk + Fk+1) = F 2

k+1 + (−1)k+1.

or to

F 2

k + Fk Fk+1 = F 2

k+1 + (−1)k+1.

Substitute F 2 from the right-hand side of (5):

k

Fk−1Fk+1 − (−1)k + FkFk+1 = F 2

k+1 + (−1)k+1

4

or

Fk+1(Fk−1 + Fk) = F 2

k+1 + (−1)k+1 + (−1)k = F 2

k+1

or

F 2

k+1 = F 2

k+1

Part 2:

For n = 0:

0

F 2

i = F 2

0 = 0 = F0F1 = 0 · 1 = 0

i=0

If it is true for n = k:

k

F 2

i = Fk Fk+1

(6)

i=0

then we can F 2

to both sides of (6) to get:

k+1

k+1

F 2

i = Fk Fk+1 + F 2

k+1 = Fk+1(Fk + Fk+1) = Fk+1Fk+2

i=0

3. Show that:

1

1

1

√

1 + √ + √ + · · · + √

≤ 2 n.

2

3

n

Solution. For the n = 1 case we have

√

1 ≤ 2 1 = 2.

Assume the equation is true for n = k:

1

1

1

√

1 + √ + √ + · · · + √

≤ 2 k.

2

3

k

√

To show it is also true for n = k + 1, add 1/ k + 1 to both sides:

1

1

1

√

1

1 + √ + · · · + √ + √

≤ 2 k + √

.

2

k

k + 1

k + 1

Thus if we can show that

√

1

√

2 k + √

≤ 2 k + 1

k + 1

5

√

then the proof is complete. Multiply both sides by

k + 1 and then

square both sides to obtain:

4k(k + 1) + 4

k(k + 1) + 1 ≤ 4(k2 + 2k + 1).

4

k(k + 1) ≤ 4k + 3

Squaring again:

16k2 + 16k ≤ 16k2 + 24k + 9

which is always true.

4. Show that:

2! · 4! · 6! · · · (2n)! ≥ ((n + 1)!)n.

Solution. First show it is true for n = 1:

2! = 2 ≥ (2!)1 = 2.

Next assume it is true for n = k:

2! · 4! · 6! · · · (2k)! ≥ ((k + 1)!)k.

(7)

If we multiply both sides of (7) by (2(k + 1))!, we get:

2! · 4! · · · (2k)! · (2k + 2)! ≥ ((k + 1)!)k · (2k + 2)!.

If it can be shown that the right-hand side of the equation above is

larger than ((k + 2)!)k+1, the proof is complete. The term (2k + 2)! on

the right-hand side can be written:

(2k + 2)! = (2k + 2)(2k + 1)(2k) · · · (k + 3)(k + 2)!

This consists of k terms, all greater than k + 2, multiplied by (k + 2)!,

so

((k + 1)!)k(2k + 2)!

>

((k + 1)!)k(k + 2)k(k + 2)!

=

((k + 2)!)k(k + 2)! = ((k + 2)!)k+1

6

5. Show that:

√

π

2 +

2 +

2 + · · · +

2 = 2 cos 2n+1

where there are n 2s in the expression on the left.

Solution. For n = 1 case we have:

√

π

√

√

2 = 2 cos

= 2 cos π/4 = 2 2/2 =

2.

22

Now assume it is true for k nested square roots:

√

π

2 +

2 +

2 + · · · +

2 = 2 cos

.

2k+1

Add 2 to both sides and take the square root, so the LHS will have

k + 1 nested square roots, and the right hand side will be:

π

2 + 2 cos

.

(8)

2k+1

All we need to show is that the value above is equal to

π

2 cos

.

(9)

2k+2

We know that for any angle θ we have:

1 + cos 2θ

cos θ =

.

(10)

2

Substitute π/2k+2 for θ in 10 and the equality of 8 and 9 becomes

immediately obvious.

4

References

1. H. Amann, J. Esher, Analysis 1, Birkhauser Basel; 1st edition, 2010.

2. H. Amann, J. Esher, Analysis 2, Birkhauser Basel; 1st edition, 2008.

3. H. Amann, J. Esher, Analysis 3, Birkhauser Basel; 1st edition, 2009.

4. S. Lay, Analysis: With an Introduction to Proof, Prentice Hall; 4th

edition, 2004.

7

5. S. Hedman, A First course in Logic: An Introduction to Model The-

ory, Proof Theory, Computability, and Complexity, Oxford University

Press; 2004.

6. R. Larson, B. Edwards, Calculus, Brooks Cole; 9th edition, 2009.

7. R. Larson, R. Hostetler, B. Edwards, Calculus (With Analytic Geom-

etry), Brooks Cole; 8th edition, 2005.

8. M. Lial, J. Hornsby, D. Schneider, College Algebra, Addison Wesley;

10th edition, 2008.

9. C. Mckeague, M. Turner, Trigonometry, Brooks Cole; 6th edition,

2007.

10. M. Lial, J. Hornsby, D. Schneider, Trigonometry, Addison Wesley; 9th

edition, 2008.

11. R. Larson, Trigonometry, Brooks Cole; 8th edition, 2010.

12. R. Moyer, F. Ayres, Schaum’s Outline of Trigonometry, McGraw-Hill;

4th edition, 2008.

13. G.F. Simmons, Precalculus Mathematics in a Nutshell, Wipf & Stock

Publishers; 2003.

14. M. Sullivan, Trigonometry: A Unit Circle Approach, Prentice Hall;

8th edition, 2007.

15. R. Larson, Algebra and Trigonometry, Brooks Cole; 5th edition, 2000.

8

# Document Outline

- Introduction
- Formal Definition of Induction
- Examples
- References