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 proven 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:

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 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

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

1. Often it's impractical to start with n = 1. MI applies with any starting integer n₀. The result is then proven for all n from n₀ on.
2. 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.

There are other examples proven by MI:

1. A 1-1 correspondence
2. An Extension of van Schooten's Theorem
3. An infinite exponent
4. Another pigeonhole problem
5. A Problem of Divisibility by 5ⁿ
6. Binary Euclid's algorithm
7. Book Index Range
8. Breaking Chocolate Bars
9. Committee Chairs
10. Constructible Numbers
11. Construction Problem
12. Continued Fractions
13. Counting Triangles
14. Counting Triangles II
15. Cutting Squares
16. Diagonal Count
17. Difference of the Cantor Sets
18. Euclid's Algorithm
19. Farey series
20. Fractions on a Binary Tree II
21. Geometric Illustration of a Convergent Series
22. Golomb's inductive proof of a tromino theorem
23. Groups of Permutations
24. Guessing Two Consecutive Integers
25. Hamming and Levenshtein distance functions
26. Inequality 1/2·3/4·5/6· ... ·99/100 < 1/10
27. Inequality (1 + 1^-3)(1 + 2^-3)(1 + 2^-3)...(1 + n^-3) < 3
28. Inequality 1 + 2^-2 + 3^-2 + 4^-2 + ... + n^-2 < 2
29. Inequality between arithmetic and geometric means
30. Infinite Latin Squares
31. Infinitude of Primes Via Fermat Numbers
32. Infinitude of Primes Via *-Sets
33. Integers and Rectangles: a Proof by Induction
34. Integral Domains: Remarks and Examples
35. Josephus problem
36. Linear Functions
37. Marriage Problem
38. Mathematical Induction
39. Mathematicians Doze Off
40. Morley's Pursuit of Incidence
41. Pennies in Boxes
42. Pigeonhole problem
43. Pigeonhole principle complements math induction
44. Poncelet Theorem
45. Prim's and Kruskal's algorithms find a minimum spanning tree
46. Problem on an Infinite Checkerboard
47. Property of irriducible fractions on the Stern-Brocot tree
48. Property of the Powers of 2
49. Right Replacement
50. Sierpinski Gasket
51. Sierpinski Gasket and Tower of Hanoi
52. Simple Cellular Automaton
53. Solitaire on the Circle
54. Splitting piles
55. Stern-Brocot Tree
56. Stern-Brocot Tree II
57. Strange Integers: Divisors and Primes
58. The Somos sequences
59. Ways To Count

Reference

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

On the Web

1. An online and iPod video by Julio de la Yncera

Copyright © 1996-2008 Alexander Bogomolny