Principle of Mathematical Induction, a Generic Outline

Principle of Mathematical Induction (a generic outline)

Let P(n) be a statement involving the positive integer n. If

P(m) is true for m ³ n, and
the truth of P(k) implies the truth of P(k + 1), for every particular but arbitrarily chosen integer k, k ³ m.

then P(n) must be true for all positive integers n ³ m.

Mathematical induction consists of two distinct parts.

The basis step: you must show that the formula is true for n = m, where m is your starting point, typically 0 or 1.
The inductive step:
a. Formulate the inductive hypothesis, assume that the formula is valid for some integer k,
k ³ m.
b. Use this assumption to prove that the formula is valid for the next integer, k + 1.

Combining the results of parts (1) and (2), you can conclude by mathematical induction that the formula is valid for all positive integer values of n ³ m.

Remarks:	Proof:
Show the statement works for n = m.	(1)
[Assume it works for some arbitrary integer k, and show that it works for k + 1.] Write out our initial statement as an assumption in k, say S_k.	(2a)
Write out our statement adding the next term to the left hand side (LHS) and substituting k + 1 for k in the right hand side, (RHS). The LHS then becomes S_k + a_{k + 1}. Utilize your assumption: substitute the RHS of your assumption for S_k. Now simplify both sides to see if the statement is true for k + 1.	(2b)