Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 37 Ā· Proof Techniques

Mathematical Induction

Learn mathematical induction from the domino picture to complete proofs: sums, divisibility and inequalities, common pitfalls, and Python checks of the formulas.

How do you prove a statement about every natural number when there are infinitely many to check? Mathematical induction does it with two finite pieces of work. It is the most important proof technique in discrete mathematics and computer science, because it matches how programs are built: recursion and loops over ever-larger inputs.

The principle

Let P(n) be a statement about the natural number n. To prove āˆ€n ≄ nā‚€ P(n):

  1. Base case: prove P(nā‚€).
  2. Inductive step: prove that for every k ≄ nā‚€, P(k) → P(k + 1). In the proof you assume P(k) (the inductive hypothesis) and derive P(k + 1).

Then P holds for all n ≄ nā‚€. Think of dominoes: the base case knocks over the first; the step guarantees that each falling domino knocks over the next.

The domino principle

Base case The first domino falls
Inductive step If P(k) then P(k+1)
Conclusion All dominoes fall

You need both parts

1 / 2

Formally, induction is equivalent to the well-ordering principle: every nonempty set of natural numbers has a least element. If P failed somewhere, there would be a smallest failure, but the step would then push it down to a smaller failure: a contradiction.

Example 1: a sum formula

Claim. For all n ≄ 1, 1 + 2 + ⋯ + n = n(n + 1)/2.

Base case (n = 1). LHS = 1, RHS = 1Ā·2/2 = 1. āœ“

Inductive step. Assume 1 + ⋯ + k = k(k + 1)/2. Then 1 + ⋯ + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2, which is the formula for n = k + 1. āˆŽ

Notice the move at the heart of every such proof: use the inductive hypothesis at exactly the spot where the smaller instance appears.

Python Checking induction claims numerically

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Example 2: divisibility

Claim. For all n ≄ 1, 7ⁿ āˆ’ 1 is divisible by 6.

Base case. 7¹ āˆ’ 1 = 6. āœ“

Step. Assume 6 divides 7įµ āˆ’ 1, so 7įµ āˆ’ 1 = 6m. Then 7įµāŗĀ¹ āˆ’ 1 = 7Ā·7įµ āˆ’ 1 = 7(7įµ āˆ’ 1) + 6 = 7Ā·6m + 6 = 6(7m + 1). āˆŽ

The trick: rewrite the new expression so the old one appears (7Ā·7įµ āˆ’ 1 = 7(7įµ āˆ’ 1) + 6).

Example 3: an inequality

Claim. For all n ≄ 4, 2ⁿ < n!.

Notice the base case is n = 4, not 1, since 2³ = 8 > 3! = 6 fails at smaller n.

Base. 2⁓ = 16 < 24 = 4!. āœ“

Step. Assume 2įµ < k! with k ≄ 4. Then 2įµāŗĀ¹ = 2Ā·2įµ < 2Ā·k! < (k + 1)Ā·k! = (k + 1)!, since k + 1 > 2. āˆŽ

Python Find where an inequality starts to hold

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This "find the base case" exercise is what mathematicians do before choosing nā‚€.

Induction in programming

A recursive function's correctness proof is an induction. For sum_to(n), the base case is n = 0 and the inductive step trusts the call on n āˆ’ 1. Loop invariants are induction on the number of iterations: the invariant holds before the loop (base), and if it holds before an iteration it holds after (step).

Python Recursion mirrors induction

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A famous false proof

"Claim: all horses have the same color. Base: one horse: trivially same color. Step: assume any k horses are the same color; take k + 1 horses, remove one, the rest are same color; replace and remove another; overlapping horses force all the same." The flaw is in the step for k = 1: two horses have no overlap, so the step fails exactly when moving from 1 to 2. The inductive step must work for every k from the base onward, including the first one. A correct-looking step with a hidden gap breaks the whole chain.

Writing an induction proof: template

  1. State P(n) precisely, and the range of n.
  2. Base case: verify directly.
  3. Inductive hypothesis: "Assume P(k) holds for some k ≄ nā‚€."
  4. Inductive step: show P(k + 1), pointing out where you use the hypothesis.
  5. Conclusion: "By induction, P(n) holds for all n ≄ nā‚€."

Common mistakes

  • Omitting the base case (every domino could be loose).
  • Assuming P(k + 1) while proving it, instead of assuming P(k).
  • Using a different statement for the hypothesis than for the goal.
  • Wrong starting point, as with 2ⁿ < n!.
  • A step that silently fails at small k, like the horse "proof".

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. What are the two parts of a proof by induction?

    The base case starts the chain; the inductive step carries truth from k to k+1.
  2. 2. In the inductive step you assume...

    The inductive hypothesis is P(k); the goal is P(k+1).
  3. 3. Why does 2^n < n! need base case n = 4?

    At n = 1, 2, 3 the inequality is false (2 < 1 fails, 4 < 2 fails, 8 < 6 fails), so we start where it first holds.
  4. 4. Where does the 'all horses are the same color' proof break?

    With k = 1 the two subsets of size 1 do not overlap, so the argument does not link them.

Summary

  • Induction proves āˆ€n ≄ nā‚€ P(n) via a base case and a step P(k) → P(k+1).
  • It is equivalent to well-ordering of the natural numbers.
  • Typical uses: sum formulas, divisibility, inequalities, program correctness and loop invariants.
  • Choose the base case where the statement first holds; make sure the step works for every k.
  • Recursion and induction are the same idea seen from two sides.

Next: Strong and Structural Induction