Mathematical Induction

Main idea

To prove something for every n ≥ 1, you don't check infinitely many cases. You show it's true for n = 1, and that being true for any n = k forces it to be true for n = k + 1. Like dominoes: the first one falls, and each one knocks over the next, so they all go down.

Sum of the first n integers

1 + 2 + \cdots + {\htmlData{sym=0}{n}} = \frac{{\htmlData{sym=0}{n}}({\htmlData{sym=0}{n}}+1)}{2}

What the symbols mean

$n$
Last term
How many integers are added.

Explanation

Mathematical induction is simply a way to prove that something is true for every whole number $1, 2, 3, \dots$ by showing just two things: it's true for the first one, and each one passes the truth along to the next. The name borrows from everyday "inductive reasoning," going from particular cases to a general rule, but don't let that fool you: guessing a rule from a pattern isn't a proof, and mathematical induction is a full, airtight proof. It's how you nail down formulas for sums, the running time of algorithms and anything else built up one step at a time. The formula above looks like a lot, but it's just $1 + 2 + \cdots + n$ (add up the whole numbers from 1 to $n$ ) on one side and $\frac{n(n+1)}{2}$ (a shortcut that gives the same answer) on the other. Induction is how we'll show the shortcut never fails.

Direct proof and contradiction handle one statement at a time. But " $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ " is really infinitely many statements, one for each $n$ , and you can't check them all. Here's the way around it.

Structure of an induction proof of " $S(n)$ is true for all $n \ge 1$ ":

Base case: check $S(1)$ .
Inductive hypothesis: assume $S(k)$ for an arbitrary $k \ge 1$ .
Inductive step: use that assumption to prove $S(k + 1)$ .

Example: $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ . For $n = 1$ both sides are 1. Assume $1 + \cdots + k = \frac{k(k+1)}{2}$ . The sum up to $k + 1$ is the sum up to $k$ with one more term on the end, so the assumption does most of the work:

1 + \cdots + k + (k + 1) = \frac{k(k+1)}{2} + (k + 1) = \frac{(k+1)(k+2)}{2},

which is the formula with $n = k + 1$ . Done.

A common mistake. It's tempting to think the inductive step is cheating, because you assume the very formula you're trying to prove. It isn't. You never assume $S(n)$ for all $n$ ; you prove an implication, $S(k) \to S(k+1)$ , the "if ... then" from the logic unit. On its own that proves nothing, like a row of dominoes nobody has pushed. Together with the base case, though, the chain $S(1) \to S(2) \to S(3) \to \cdots$ reaches every $n$ .

Two other ways induction goes wrong: skipping the base case (the dominoes never start), or an inductive step that secretly fails for small $k$ . The famous "all horses are the same color" fake proof breaks exactly that way, going from 1 to 2.

See it

n

6.00

Here's why the formula should be true before we prove it. Columns of height 1, 2, …, n make a staircase, and a second copy of the same staircase, flipped, fills out an n by (n + 1) rectangle. With n = 6 the rectangle holds 42 squares, so one staircase holds 21. Induction turns this picture into a proof for every n.

Worked examples

Example 1

Prove by induction that $1 + 3 + 5 + \cdots + (2n - 1) = n^2$ .

1
Base case: $n = 1$ gives $1 = 1^2$ , so the first domino falls.

Practice

Type your answer and check it. Solve them all to complete the lesson.

Problem 1+5 XP

Use the formula: $1 + 2 + \cdots + 100 =$ ?

Problem 2+5 XP

In the inductive step for $1 + \cdots + n = \frac{n(n+1)}{2}$ , which term do you add to both sides?

Problem 3+5 XP

$1 + 3 + 5 + \cdots + 19 =$ ?

Problem 4+5 XP

Prove by induction that $2^n > n$ for all $n \ge 1$ .

Problem 5+5 XP

A game gives you 1 coin on day 1, 3 on day 2, 5 on day 3, and so on through the odd numbers. Induction proves the total after $n$ days is $n^2$ . On which day does the total first pass 1000 coins?

Problem 6+5 XP

Induction also proves $1^2 + 2^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$ . Use it to find $1^2 + 2^2 + \cdots + 20^2$ .

Challenge problem+25 XP

The hardest one here. Get it, and you've got this lesson.

To prove by induction that 3 divides $n^3 + 2n$ for every $n \ge 1$ , the inductive step looks at the difference $\big[(k + 1)^3 + 2(k + 1)\big] - \big[k^3 + 2k\big]$ . Simplify it, as an expression in $k$ .

Where it's used

Programmers prove loops correct with induction: the loop invariant is the inductive hypothesis, and each pass through the loop is an inductive step.

The Tower of Hanoi: Recursion and 2ⁿ − 1Discrete · Game Development

Proof by Contradiction Strong Induction and Well-Ordering