Dear Brant:

Induction is such an important tool in Mathematics that I have no chance to pay it a sufficient tribute in a short reply. I'll try to start you with this but you should look into other sources as well. I do not know of a book specifically devoted to the math induction but the following two both offer a good introduction and quite a few examples:

1. Graham, Knuth, Patashnik, Concrete Mathematics
2. Courant and H.Robbins, What is Mathematics?

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

Mathematical Induction is a way of proving math statements for all integers (perhaps excluding a finite number.) Ref 1 says:

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

(1) 1+2+3+...+n = n(n+1)/2
(2) If x₁,x₂,...,x_n>0 then (x₁+x₂+...+x_n)/n (x₁*x₂*...*x_n)^1/n

etc.

It's convenient to talk about statement P(n). For (1), P(1) says that 1 = 1*(1+1)/2 which is incidently true. P(2) says that 1+2 = 2*(2+1)/2, P(3) means that 1+2+3 = 3*(3+1)/2. And so on. These particular cases are obtained by substituting specific values 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 for this purpose you should accomplish just two steps:

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

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

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

1+2+...+k+(k+1) = [1+2+...+k] + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2 = (k+1)[(k+1) + 1]/2.

Which exactly means that P(k+1) holds. 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.

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.

Hope this puts you on the right track.

Best regards,
Alexander Bogomolny

P.S.

With time I started a page on math induction where I placed this response, more examples and links to other pages that use induction.

Copyright © 1996-2010 Alexander Bogomolny

35712505