Mathematical Induction and Proof by Induction

One form of proof is by Mathematical Induction, a method where the result of the proof is to demonstrate that a mathematical formula is true for every positive integer.

The Principal of Mathematical Induction is that for each positive integer of statement s(n) two properties are satisfied:

1) s(1) is correct, and

2) The Inductive Hypothesis; whenever s(k) is true, then s(k + 1) is also true.

Then s(n) is true for every positive integer n.

Often a mathematical formula, s(n), is true for every positive integer n and it can be proved:

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

For each n, it can be shown that each statement,

s(1) = 1 (1 + 1) / 2

s(2) = 2 (2 + 1) / 2

s(3) = 3 (3 + 1) / 2

… and continues,

s(25) = 25 (25 + 1) / 2

… the pattern continues infinitely.

The claim of the proof is that for every positive integer the formula is true. We also quickly discover that as n increases so does the effort to evaluate the formula s(n) and that statements of s(n) are infinite. It is therefore impossible to evaluate all statements of s(n). This inability to evaluate all statements can lead to an incorrect conclusion that the pattern represented by formula s(n) is true.

There are many examples in which a pattern appears to be developing for small values of n and then at some point the pattern fails. One famous case of pattern failure is the Prime Conjecture by the French mathematician Pierre de Fermat (1601 - 1665), who speculated that:

Fn = 2x + 1, n = 0, 1, 2 , 3 . . .

Where x = 2n

F0 = 21 + 1 = 3

F1 = 22 + 1 = 5

F2 = 24 + 1 = 17

F3 = 28 + 1 = 257

F4 = 216 + 1 = 65,537

The next Fermat number is F5 (F5 = 4,294,967,297) and is so large that it was difficult for Fermat to determine whether it was or was not prime. During the next century another well-known mathematician, Leonhard Euler, found the factorization F5:

F5 = 641 (6,700,417)

This proved that F5 is not a prime number and therefore Fermat’s Conjecture is false.

Proof by Induction Examples:

Example 1:

Show that (ab)n = an bn by the Principal of Inductive Reasoning.

s(1) asserts (ab)1 = a1 b1

Each side of the equation simplifies to ab so s(1) is true.

Next assume s(k) is true,

s(k) asserts (ab)k = ak bk

To establish s(k +1) is true we use the Inductive Hypothesis,

(ab)k + 1

= (ab)k (ab)

= (ak bk) (ab)

= (ak a) (bk b)

= (ak + 1) (bk + 1)

Both properties 1 and 2 have been established. Therefore s(n) is true for every positive integer n.

Example 2:

Using the Principal of Inductive Reasoning prove that for every positive integer n that
(n + 1)! = (n + 1) n!

s(1) asserts (1 + 1)! = (1 + 1) 1!

This is true; 2! = 2 × 1

Now suppose s(k) is true,

s(k) asserts (k + 1)! = (k + 1) k!

For n = k + 1,

(k + 1 + 1)!

= (k + 2)!

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

= (k + 2) [(k + 1) k (k − 1) . . . 3 × 2 × 1]

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

= [(k + 1) + 1] (k + 1)!

By Mathematical Induction we have proven (n + 1)! = (n + 1) n!

Top of Page

About Privacy