Skip to main content
Logo image

Applied Combinatorics

Section 3.6 Mathematical Induction

Now we move on to induction, the powerful twin of recursion.
Let \(n\) be a positive integer. Consider the following mathematical statements, each of which involve \(n\text{:}\)
  1. \(2n+7 = 13\text{.}\)
  2. \(3n-5=9\text{.}\)
  3. \(n^2-5n+9=3\text{.}\)
  4. \(8n-3 \lt 48\text{.}\)
  5. \(8n-3 > 0\text{.}\)
  6. \((n+3)(n+2) =n^2+5n+6\text{.}\)
  7. \(n^2 -6n + 13 \ge 0\text{.}\)
Such statements are called open statements. Open statements can be considered as equations, i.e., statements that are valid for certain values of \(n\text{.}\) Statement 1 is valid only when \(n=3\text{.}\) Statement 2 is never valid, i.e., it has no solutions among the positive integers. Statement 3 has exactly two solutions, and Statement 4 has six solutions. On the other hand, Statements 5, 6 and 7 are valid for all positive integers.
At this point, you are probably scratching your head, thinking that this discussion is trivial. But let’s consider some statements that are a bit more complex.
  1. The sum of the first \(n\) positive integers is \(n(n+1)/2\text{.}\)
  2. The sum of the first \(n\) odd positive integers is \(n^2\text{.}\)
  3. \(n^n \ge n! + 4,000,000,000n2^n\) when \(n\ge 14\text{.}\)
How can we establish the validity of such statements, provided of course that they are actually true? The starting point for providing an answer is the following property:
With a little thought, you should see that the Principle of Mathematical Induction is logically equivalent to the Well Ordered Property of the Positive Integers. If you haven’t already done so, now might be a good time to look over Appendix B on background material.