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

Copyright © 1996-2018 Alexander Bogomolny

71471199