Choosing What to Induct On

In one sentence

When a statement has two (or more) variables $m, n$ , lay out all the cases $P (m, n)$ as a grid. To prove one cell, the inductive step uses some other cells — whatever it uses, the induction hypothesis must cover. The possible things to induct on:

induct on $m$ (any $n$ ): assume every cell with $m^{'} < m$ , which covers whole columns to the left;
induct on $n$ (any $m$ ): covers whole rows below;
induct on $m + n$ : covers the triangle down and to the left;
double induction ( $m$ first, then $n$ ): the whole columns to the left, plus the cells below in the same column.

What you induct on need not be one of the letters in the problem either: the number of variables, the sum of two numbers, an area… Induct on whatever really gets smaller at every step.

One grid, four inductions

Step 1 / 7

What the step needs
Walking from $(0, 0)$ to $(2, 3)$ , the last step is either right or up, so the number of paths $=$ paths to $(1, 3)$ $+$ paths to $(2, 2)$ . You need to know both circled cells first.

$C_{5}^{2} = C_{4}^{1} + C_{4}^{2}$
Induct on m: not enough
Induct on n: not enough either
Induct on m+n: enough
Double induction: enough too
A different statement
Induct on m

Predict first

The “binomial sum” statement: $C_{m}^{m} + C_{m + 1}^{m} + \dots + C_{m + n}^{m} = C_{m + n + 1}^{m + 1}$ . Its inductive step is “add one more term on the left”. What is it most natural to induct on?

Induct on

m

Induct on

n

You must induct on

m + n

Choose an answer first; then you can see the result.

Stop 1 · Counting: lattice paths

$C_{m + n}^{m}$ above is itself a good example: induct on $m + n$ . The base cases are the edges $m = 0$ or $n = 0$ (only one path, $C_{n}^{0} = C_{m}^{m} = 1$ ); the inductive step is the Pascal's triangle recurrence $C_{k}^{m} = C_{k - 1}^{m - 1} + C_{k - 1}^{m}$ . Here “ $m + n$ ” is exactly the total number of steps walked — what you induct on is often a meaningful quantity in the problem.

Stop 2 · Inequalities: induct on the number of variables

Example Let $x_{1}, \dots, x_{n} \in (0, 1)$ . Prove that $(1 - x_{1}) (1 - x_{2}) \dots (1 - x_{n}) \geq 1 - (x_{1} + x_{2} + \dots + x_{n})$ .

There is no second letter here, but two things vary: the number of variables $n$ and their values. The values vary continuously, so you cannot induct on them; on the number you can.

Induction on the number of variables

Step 1 / 4

Base case
For $n = 1$ the two sides are equal.

$1 - x_{1} = 1 - x_{1}$
What to assume
Take one variable out
Expand

Stop 3 · Number theory: induct on the sum of two numbers

Example The greatest common divisor $d$ of positive integers $m, n$ can be written as $d = m x + n y$ with integers $x, y$ .

One problem, several solutions

Prove that for any positive integers $m, n$ there are integers $x, y$ with $m x + n y = g cd (m, n)$ .

Induct on m+n

If $m + n = 2$ , then $m = n = 1$ ; take $x = 1, y = 0$ . Assume the statement for all pairs with a sum less than $m + n$ . If $m = n$ , take $x = 1, y = 0$ . If $m > n$ , then $g cd (m - n, n) = g cd (m, n) = d$ and $(m - n) + n < m + n$ , so by the hypothesis $(m - n) x^{'} + n y^{'} = d$ , that is $m x^{'} + n (y^{'} - x^{'}) = d$ . The case $m < n$ is the same.

CostNatural: one subtraction step of the Euclidean algorithm makes the sum smaller.

Induct on min(m, n)

We may assume $m \geq n$ . If $n ∣ m$ , then $d = n = m \cdot 0 + n \cdot 1$ . Otherwise $m = q n + r$ with $0 < r < n$ , $g cd (n, r) = d$ , and $min (n, r) = r < n$ . By the hypothesis $n x^{'} + r y^{'} = d$ ; substituting $r = m - q n$ gives $m y^{'} + n (x^{'} - q y^{'}) = d$ .

CostFaster: one division with remainder makes the smaller number smaller, but it needs strong induction.

Both choices are right: each step makes $m + n$ smaller, or makes the smaller of the two numbers smaller. Any quantity that strictly decreases at every step can be what you induct on.

Practice

Exercise 1Basic

Starting at $(0, 0)$ and moving one unit right or up at each step, in how many ways can you reach $(3, 4)$ ?

Exercise 2Basic

Compute $1 + 3 + 6 + 10 + 15 + 21$ .

Exercise 3Advanced

The inductive step for a statement $P (m, n)$ ( $m, n \geq 0$ ) uses only $P (m + 1, n - 1)$ , and every case with $n = 0$ has been checked directly. Which of $m$ , $n$ , $m + n$ should you induct on? (Type m, n or m+n.)

Exercise 4Challenge

An $m \times n$ chocolate bar is made of $mn$ small squares. Each move, you pick up one piece and break it into two along a grid line. Prove that, however you break it, it takes exactly $mn - 1$ breaks to get $mn$ small squares.

In one sentence

One grid, four inductions

Stop 1 · Counting: lattice paths

Stop 2 · Inequalities: induct on the number of variables

Induction on the number of variables

Stop 3 · Number theory: induct on the sum of two numbers

Induct on m+n

Induct on min(m, n)

Practice

Mistake Museum · Exhibits from this stop

Inducting on m, but “freezing” n as well

Inducting on m+n when the step does not make the sum smaller