Mathematical Induction

Mathematical Induction (MI) is an extremely important tool in Mathematics.

First of all you should never confuse MI with Inductive Attitude in Science. The latter is just a process of establishing general principles from particular cases.

MI is a way of proving math statements for all integers (perhaps excluding a finite number) [1] says:

Statements proved by math induction all depend on an integer, say, n. For example,

(1) 1 + 3 + 5 + ... + (2n - 1) = n²
(2) If x₁, x₂, ..., x_n > 0 then (x₁ + x₂ + ... + x_n)/n ≥ (x₁·x₂·...·x_n)^1/n

etc. n here is an "arbitrary" integer.

It's convenient to talk about a statement P(n). For (1), P(1) says that 1 = 1² which is incidently true. P(2) says that 1 + 3 = 2², P(3) means that 1 + 3 + 5 = 3². And so on. These particular cases are obtained by substituting specific values 1, 2, 3 for n into P(n).

Assume you want to prove that for some statement P, P(n) is true for all n starting with n = 1. The Principle (or Axiom) of Math Induction states that, to this end, one should accomplish just two steps:

Prove that P(1) is true.
Assume that P(k) is true for some k. Derive from here that P(k+1) is also true.

The idea of MI is that a finite number of steps may be needed to prove an infinite number of statements P(1), P(2), P(3), ....

Let's prove (1). We already saw that P(1) is true. Assume that, for an arbitrary k, P(k) is also true, i.e. 1 + 3 + ... + (2k-1) = k². Let's derive P(k+1) from this assumption. We have

1 + 3 + ... + (2k-1) + (2k+1)	= [1 + 3 + ... + (2k-1)] + (2k+1)
	= k² + (2k+1)
	= (k+1)²

Which exactly means that P(k+1) holds. (For 2k+1 = 2(k+1)-1.) Therefore, P(n) is true for all n starting with 1.

Intuitively, the inductive (second) step allows one to say, look P(1) is true and implies P(2). Therefore P(2) is true. But P(2) implies P(3). Therefore P(3) is true which implies P(4) and so on. Math induction is just a shortcut that collapses an infinite number of such steps into the two above.

In Science, inductive attitude would be to check a few first statements, say, P(1), P(2), P(3), P(4), and then assert that P(n) holds for all n. The inductive step "P(k) implies P(k + 1)" is missing. Needless to say nothing can be proved this way.

Remark

Often it's impractical to start with n = 1. MI applies with any starting integer n₀. The result is then proved for all n from n₀ on.
Sometimes, instead of 2., one assumes 2':

Assume that P(m) is true for all m < (k + 1).

Derive from here that P(k+1) is also true. The two approaches are equivalent, because one may consnider a statement Q: Q(n) = P(1) and P(2) and ... and P(n), so that Q(n) is true iff P(1), P(2), ..., P(n) are all true.

This variant goes by the name of Complete Induction or Strong Induction.

In problem solving, mathematical induction is not only a means of proving an existing formula, but also a powerful methodology for finding such formulas in the first place. When used in this manner MI shows to be an outgrowth of (scientific) inductive reasoning - making on conjectures on the basis of a finite set of observations.

There are other examples proved by MI:

Reference

D. Fomin, S. Genkin, I. Itenberg, Mathematical Circles (Russian Experience), AMS, 1996
R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
R.Courant and H.Robbins, What is Mathematics?, Oxford University Press, 1996

On the Web

An online and iPod video by Julio de la Yncera

41170164