Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 68 · Proof Techniques

Mathematical Induction

Learn mathematical induction with base case and inductive step, proofs of sum formulas, divisibility and inequalities, and the mistakes to avoid.

How do you prove something about all positive integers when there are infinitely many of them? You cannot check them one by one. Mathematical induction is the technique that does it with just two finite checks, and it is the proof method closest to programming: it is recursion, turned into an argument.

Think of an endless row of dominoes. If you knock over the first one, and you know that any falling domino knocks over the next, then every domino falls. That is induction. You will use it to prove closed forms for sums, divisibility facts and inequalities, and later to justify recursive algorithms.

The principle

To prove that a statement P(n) holds for every integer n ≥ n₀ (usually n₀ = 0 or 1), you do two things.

  1. Base case. Prove P(n₀).
  2. Inductive step. Prove that for every k ≥ n₀, if P(k) is true then P(k+1) is true. The assumption P(k) is called the inductive hypothesis.

Then P(n) holds for all n ≥ n₀, because P(n₀) gives P(n₀+1), which gives P(n₀+2), and so on forever.

Induction in two moves

Base case Show the first domino falls.
Inductive step If domino k falls, so does k+1.
Conclusion Every domino falls.

Skip either move and the argument collapses.

1 / 2

Check numerically before you prove

Induction proves a formula you already believe. A quick experiment tells you whether the guess is even plausible, and it protects you from wasting effort on a false claim. Remember that a test is not a proof (see How Proofs Work).

Python Test induction claims on many values

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.

The first three print None (no failure found), and the last fails at n = 1. Passing tests are encouraging, but induction is what turns them into a theorem.

Proving a sum formula

Theorem. For every integer n ≥ 1, 1 + 2 + … + n = n(n+1)/2.

Proof. Let P(n) be this statement.

Base case (n = 1). The left side is 1 and the right side is 1·2/2 = 1. So P(1) holds.

Inductive step. Let k ≥ 1 and assume P(k): 1 + 2 + … + k = k(k+1)/2. We must show P(k+1): 1 + 2 + … + k + (k+1) = (k+1)(k+2)/2. Starting from the left side and using the hypothesis,

1 + … + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2.

That is the right side of P(k+1). By induction, P(n) holds for all n ≥ 1. ∎

The pattern: write the sum up to k+1, peel off the last term, replace the rest using the hypothesis, and simplify to the target. The same plan proves the sum of the first n odd numbers is n²: the step says k² + (2k+1) = (k+1)².

Divisibility and inequalities

Induction works for any statement indexed by integers. For divisibility, the trick is to rewrite the k+1 expression so that the hypothesis term appears.

Theorem. For every n ≥ 0, 7 divides 8ⁿ − 1.

Proof. Base case: 8⁰ − 1 = 0, which 7 divides. Step: assume 8ᵏ − 1 = 7m for some integer m. Then 8ᵏ⁺¹ − 1 = 8·8ᵏ − 1 = 8(8ᵏ − 1) + 7 = 8·7m + 7 = 7(8m + 1). So 7 divides 8ᵏ⁺¹ − 1. ∎

For inequalities, you chain inequalities and keep track of what is bigger.

Theorem. For every n ≥ 5, n² < 2ⁿ.

Proof. Base case: 5² = 25 < 32 = 2⁵. Step: assume k² < 2ᵏ for some k ≥ 5. Then 2ᵏ⁺¹ = 2·2ᵏ > 2k². Also 2k² ≥ (k+1)² exactly when k² ≥ 2k + 1, which is true for every k ≥ 3. So 2ᵏ⁺¹ > 2k² ≥ (k+1)². ∎

This example shows why the starting point matters. The claim fails at n = 3 (9 against 8) and at n = 4 (16 against 16), so the base case cannot be earlier than 5, even though the step itself would work from k = 3. Let code find the true starting point.

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.

The three patterns show that the starting point differs: n² < 2ⁿ starts at 5, 2ⁿ > n³ at 10, and n! > 2ⁿ at 4. The inductive step often works cleanly only after the claim has "taken off".

Induction and recursion

Induction is the proof twin of recursion. A recursive function calls itself on a smaller input, with a base case that stops the calls. An induction proof assumes the claim for the smaller case and proves it for the larger. That is why induction is the standard way to prove that recursive code is correct. For example, this function adds the first n integers; its correctness proof is the sum-formula proof above in code form.

Python A recursive function and its inductive proof

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.

Typical mistakes

  • Forgetting the base case. "Every integer is equal to the next one" can be "proved" by a perfectly valid-looking step, but there is no base case that works. Without a first domino, nothing falls.
  • A step that quietly fails for small k. In the famous "all horses are the same color" argument, the step breaks when going from 1 horse to 2, so the induction never gets started above 1.
  • Using the conclusion. In the step, start from the k+1 expression and reach the target. Do not assume P(k+1) and rearrange it to something true: that proves nothing unless every move is reversible.
  • Wrong starting value. Pick the smallest n₀ for which the claim is true, and prove that base case honestly (see the inequality above).
  • Assuming P(k) for all k. The hypothesis is for one fixed, arbitrary k. If you assume it for every k, you have assumed the theorem.
  • Skipping the algebra justification. After "by the inductive hypothesis", show where the hypothesis was used.

An induction proof is only as strong as its weakest link. A missing base case or a step that fails for one particular k proves nothing, even if the algebra looks flawless.

Sometimes the step needs more than just P(k): for example, a number's factorization uses many smaller numbers. That version is called strong induction, and it is the subject of Strong Induction and Well-Ordering.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What are the two parts of an induction proof?

    You prove the statement for the first value (base case), then prove that if it holds for k it holds for k+1 (inductive step).
  2. 2. In the inductive step for 1 + 2 + ... + n = n(n+1)/2, which fact do you use?

    You assume the statement for an arbitrary k (the inductive hypothesis) and use it to prove the statement for k + 1. Assuming P(k+1) or P(n) for all n would be circular.
  3. 3. Why does 'n squared < 2^n' need a base case of n = 5 rather than n = 1 or n = 3?

    At n = 3 the values are 9 and 8, at n = 4 they are 16 and 16, so the claim fails there. The first value where it is true (and stays true) is n = 5, and the base case must be a value where the claim holds.
  4. 4. A student 'proves' a claim by showing P(k) implies P(k+1) for all k but never checks P(1). What is the problem?

    Without a true first statement, the implications P(1) -> P(2) -> P(3) -> ... give nothing. A valid step alone cannot prove the claim.

Summary

  • Induction proves P(n) for all n ≥ n₀ with a base case and an inductive step.
  • The inductive hypothesis is P(k) for one arbitrary k; the goal is to reach P(k+1).
  • For sums, peel off the last term and use the hypothesis; for divisibility, rewrite the k+1 expression to expose the hypothesis term.
  • Check the claim in Python first, and find the true starting point for inequalities.
  • Induction mirrors recursion and is how recursive code is proved correct.
  • Never skip the base case, assume the conclusion, or start before the claim becomes true.

Next: Strong Induction and Well-Ordering.