Proofs and induction · Definition

Mathematical induction

discrete mathematicsproofs

Before you start you need to know

It proves a property for infinitely many integers at once, reducing the problem to a starting case and one step that repeats.

Definition

Mathematical induction proves that a property \(P(n)\) holds for every integer \(n\ge n_0\): one checks the base case \(P(n_0)\) and proves that, for each \(k\ge n_0\), \(P(k)\) implies \(P(k+1)\).

\[\big[P(n_0)\wedge\forall k\ge n_0\,(P(k)\Rightarrow P(k+1))\big]\Rightarrow\forall n\ge n_0\,P(n)\]

The idea is a row of dominoes: the base case knocks down the first one and the inductive step guarantees that, if domino \(k\) falls, the next one falls too. Then all of them fall from the first on. Formally it rests on the well-ordering principle of the nonnegative integers: if \(P(n)\) failed for some \(n\ge n_0\), there would be a least \(n\) where it fails, contradicting the inductive step applied to its predecessor.

In practice the inductive step is written like this: assume \(P(k)\) (the inductive hypothesis) and rewrite the statement of \(P(k+1)\) until the hypothesis can be used. For sums, split off the last term; for divisibility, write the expression at \(k+1\) as a multiple of the one at \(k\) plus something divisible. For example, for \(1+2+\cdots+n=\tfrac{n(n+1)}2\), adding \(k+1\) to both sides of \(P(k)\) gives \(\tfrac{(k+1)(k+2)}2\).

There are three typical mistakes: omitting the base case (as in «\(n=n+1\)», whose step is valid but whose conclusion is false), starting the chain at an \(n_0\) where the property no longer holds, and using in the step the property for \(k+1\), which is exactly what must be proved. It helps to write down, before starting, what \(P(k)\) says and what \(P(k+1)\) says.

This method prepares strong induction, where the hypothesis includes all earlier cases, and the recursive definition of sequences and structures, whose properties are almost always proved by induction.

Think about it

Why is it not enough to check \(P(n)\) for \(n=1,\dots,1000\)?

A thousand cases prove nothing about \(n=1001\); induction does, because the inductive step covers every \(k\) at once. Some properties hold up to huge numbers and then fail.

In a proof by induction, what is assumed and what is proved in the step?

One assumes \(P(k)\) and proves \(P(k+1)\); assuming \(P(k+1)\) would be circular reasoning.

Exercises 10

  1. A proof by mathematical induction consists of:
  2. To prove \(2+4+\cdots+2n=n(n+1)\), in the base case \(n=1\) both sides equal:
  3. In the inductive step for \(P(n)\), the inductive hypothesis is:
  4. Using \(1+3+\cdots+(2n-1)=n^2\), what is the sum of the first \(12\) odd numbers?
  5. In the inductive step of \(1+2+\cdots+n=\tfrac{n(n+1)}{2}\), adding \(k+1\) to both sides of \(P(k)\) makes the right side equal to:
  6. Using \(1^2+2^2+\cdots+n^2=\tfrac{n(n+1)(2n+1)}{6}\), compute \(1^2+2^2+\cdots+6^2\).
  7. To prove that \(6\) divides \(7^n-1\), which equality lets you go from \(P(k)\) to \(P(k+1)\)?
  8. The inequality \(2^n>n^2\) fails for \(n=2,3,4\) and holds for \(n\ge5\). Which base case is suitable to prove it by induction?
  9. Let \(P(n)\): «\(n=n+1\)». It is proved that \(P(k)\Rightarrow P(k+1)\) by adding \(1\) to both sides. What follows?
  10. \(P(3)\) is checked and \(P(k)\Rightarrow P(k+1)\) is proved for all \(k\ge3\). For which \(n\) is \(P(n)\) proved?

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §5.1
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §5.2
  • László Lovász, József Pelikán, Katalin Vesztergombi, Discrete Mathematics: Elementary and Beyond, 1st edition, Springer, 2003. Cap. 1