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:

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

1. A 1-1 correspondence
2. A Low Bound for 1/2 * 3/4 * 5/6 * ... * (2n-1)/2n
3. A Problem of Divisibility by 5ⁿ
4. A Problem of Satisfying Inequalities
5. A Proof by Game for a Sum of a Convergent Series
6. A Property of the fusc() Function
7. All Powers of x are Constant
8. An Equation in Reciprocals
9. An Extension of the AM-GM Inequality
10. An Extension of van Schooten's Theorem
11. An Inequality for Grade 8
12. An infinite exponent
13. Another pigeonhole problem
14. Binary Euclid's algorithm
15. Book Index Range
16. Breaking Chocolate Bars
17. Chinese Remainder Theorem
18. Committee Chairs
19. Constructible Numbers
20. Construction Problem
21. Factorial Products
22. Continued Fractions
23. Counting Triangles
24. Counting Triangles II
25. Cutting Squares
26. Diagonal Count
27. Difference of the Cantor Sets
28. Diophantine Quadratic Equation in Three Variables
29. Divisibility by Powers of 2
30. Euclid's Algorithm
31. Farey series
32. Fermat's Little Theorem
33. Fractions on a Binary Tree II
34. Four Weighings Suffice
35. Geometric Illustration of a Convergent Series
36. Golden Ratio is Irrational
37. Golomb's inductive proof of a tromino theorem
38. Groups of Permutations
39. Guessing Two Consecutive Integers
40. Hamming and Levenshtein distance functions
41. Helly's Theorem
42. Inequality 1/2·3/4·5/6· ... ·99/100 < 1/10
43. Inequality (1 + 1^-3)(1 + 2^-3)(1 + 2^-3)...(1 + n^-3) < 3
44. Inequality 1 + 2^-2 + 3^-2 + 4^-2 + ... + n^-2 < 2
45. Inequality between arithmetic and geometric means
46. Inequality of a Series of Square Roots
47. Infinite Latin Squares
48. Infinitude of Primes Via Fermat Numbers
49. Infinitude of Primes Via Lower Bounds
50. Infinitude of Primes Via *-Sets
51. Integers and Rectangles: a Proof by Induction
52. Integers With Digits 1 and 2 and Residues Modulo Powers of 2
53. Integral Domains: Remarks and Examples
54. Josephus problem
55. Linear Functions
56. Many Jugs to One II
57. Marriage Problem
58. Mathematical Induction
59. Mathematicians Doze Off
60. Morley's Pursuit of Incidence
61. Nested Radicals
62. Nontrivial Ramsey numbers R(m, n) exist for all natural n and m
63. Numbers That Divide the Others' Sum
64. Pennies in Boxes
65. Pigeonhole problem
66. Pigeonhole principle complements math induction
67. Poncelet Theorem
68. Prim's and Kruskal's algorithms find a minimum spanning tree
69. Problem on an Infinite Checkerboard
70. Property of irriducible fractions on the Stern-Brocot tree
71. Property of the Powers of 2
72. Ramsey's Numbers
73. Rabbits Reproduce; Integers Don't
74. Right Replacement
75. Sierpinski Gasket
76. Sierpinski Gasket and Tower of Hanoi
77. Simple Cellular Automaton
78. Solitaire on the Circle
79. Splitting piles
80. Stern-Brocot Tree
81. Stern-Brocot Tree II
82. Strange Integers: Divisors and Primes
83. Subsets and Intersections
84. The Somos sequences
85. Three Jugs - Equal Amounts
86. Tromino Puzzle: Deficient Squares
87. Two Color Coloring of the Plane
88. The union of a finite number of cycles of a connected (di)graph is a cycle.
89. 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

|Contact| |Front page| |Contents| |Algebra| |Store|