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) = n2
(2) If x1, x2, ..., xn > 0 then (x1 + x2 + ... + xn)/n ≥ (x1·x2·...·xn)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 = 12 which is incidentally true. P(2) says that 1 + 3 = 22, P(3) means that 1 + 3 + 5 = 32. 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) = k2. Let's derive P(k+1) from this assumption. We have

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

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 n0. The result is then proved for all n from n0 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 consider 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 conjectures on the basis of a finite set of observations.

There are other examples proved by MI:

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

Copyright © 1996-2015 Alexander Bogomolny

 49552158

Google
Web CTK