Mathematical Induction Proof Technique
TECTechnics Classroom   TECTechnics Overview

Mathematical Induction Proof Technique

Mathematical induction proof technique is well suited for proof problems of the type:
For a given population of integers, some event occurs. An example of this type of proof problem is as follows:

For all integers n ≥ 1, nΣk=1 = [n(n+1)]/2

(a) Prove, by induction, that, for every integer ≥ 5, 2n > n2.
(b) Prove, by induction, that any integer n ≥ 2 can be expressed as a finite product of primes.

The strings: S7P2A21 (Identity - Physical Property).

The math:
Pj Problem of Interest is of type identity (physical property). Proofs establish truths. So they are identity problems.

Figure 121.2 illustrates the steps for proving by induction:
(1) Establish the truth of the statement for n = 1
(2) Assume the statement is true for n
(3) Establish the truth for n + 1.

(a) In this problem we have 5 as the lower bound instead of 1
So, for n=5, we have 25 = 32 and 52 = 25
So, 25 > 52
Assume 2n > n2
We need to show that 2n+1 > (n+1)2
2(2n) > 2(n)2
We need to show that 2(n)2 >(n+1)2 for n > 5.
2(n)2 - (n2 +2n -1) = (n-1)2
(n+1)2 - (n2 +2n -1) = 2
So, for n > 5, 2(n)2 > (n+1)2.

(b) Statement is true for n = 2.
Assume statement is true for all integers j, where 2 < j < n.
If n + 1 is prime, then statement is proved
If n + 1 is not prime, then it has a prime divisor, p.
So, there is an integer q, where 2 < q < n such that (n + 1) = pq.
But q can be expressed as a finite product of primes
So, n + 1 can be expressed as a finite product of primes.

Blessed are they that have not seen, and yet have believed. John 20:29