In some disciplines the word Induction refers to the act of assuming the truth of a principle based upon many observations. Mathematical Induction is quite different. It is a valid method of proof. The method is both subtle and powerful. A basic form of induction may be characterized as follows:

We first prove that a proposition P(n) is true for certain integer values less than or equal to a specific integer K. These values are the base cases and this step in the proof is called the basis step. Next we show that

P(n) Þ P(n+1)

We then use repeated applications of the rule of inference called Hypothetical Syllogism (see pg. 170).

Hypothetical Syllogism: ((p Þ q) /\ (q Þ r)) Þ (p Þ r)

We conclude that P(n) is true for all values of n >= K. The assumption that P(n) is true is called the Inductive Hypothesis. (Recall that in order to prove P(n) Þ P(n+1) we need only prove P(n+1) is true if P(n) is true.)

The above description is a common but limited application of the principle of mathematical induction. A more sophisticated and comprehensive characterization of the method, applicable to a wider array of problems, could be given here but the above suffices for our immediate purposes.

One important point is common to all applications of mathematical induction. We must start with a statement to prove. I.e. induction is not a method for generating formulas. It is a method of proof. For most of the exercises in our text the statement to be proven is a formula for the integers. However, other interesting applications of induction are also given (see exercise 12 pg. 195).

Prove that 1 + n· h <= (1 + h)ⁿ if h is an integer and h > -1

P( n) is the statement 1 + n· h <= (1 + h)ⁿ

Basis Step:

Show that P(n) is true for certain n <= K

P(0) is 1 + 0· h <= (1 + 0)ⁿ

I.e. 1 + 0 <= 1 which is true

Show that P(n) Þ P(n+1)

P(n) is

1 + n· h <= (1 + h)ⁿ

(1 + n· h)(1 + h) <= (1 + h)^n· (1+h) = (1 + h)ⁿ⁺¹ (multiply both sides by 1+h)

1+ n· h + h + n· h² <= (1 + h)ⁿ⁺¹

1 + n· h + h <= 1+ n· h + h + n· h² <= (1 + h)ⁿ⁺¹

1 + (n + 1)· h <= (1 + h)ⁿ⁺¹

P(n+1) is 1 + (n + 1)· h <= (1 + h)ⁿ⁺¹

Thus we have proven that P(n) Þ P(n+1)