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