Students new to induction often find it one of the most confusing topics. In this blog post I hope to make the principle of induction seem like common sense!

Before doing so, though, let’s see two fast examples in order to recall the kinds of arguments we need to understand.

Fast Example 1

Theorem: For all positive integers n,

$$ 1+2+\cdots + n = \frac{n(n+1)}{2} $$

Proof: Define the proposition $P(n)$ for each positive integer n, to be the assertion

$$ 1+2+\cdots +n = \frac{n(n+1)}{2} $$

(Base case) To prove $P(1)$ we just observe that $1 = \frac{1(1+1)}{2}$.

(Inductive case) We need to prove that if k is any positive integer for which $P(k)$ is true, then also $P(k+1)$ is true.

Assuming $P(k)$ (the inductive hypothesis), then by definition, we know

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

The proposition $P(k+1)$ is the assertion

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

We need to assume $1+2+\cdots +k=\frac{k(k+1)}{2} = \frac{k(k+1)}{2}$ and use this to prove that $1+2+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2}$. Because of the inductive hypothesis, we can make the substitution in the first equation below.

$$ \begin{aligned} 1+2+\cdots + k + (k+1) &= \frac{k(k+1)}{2}+k+1 \\ &= \frac{k(k+1)+2(k+1)}{2} \\ &= \frac{(k+1)(k+2)}{2} \end{aligned}$$

The above “chain of equations” shows that $1+2+\cdots+k+(k+1)=\frac{(k+1)(k+2)}{2}$, which is $P(k+1)$ and therefore we have proved the inductive case.

Because we have proved both the base case and inductive case, then by induction, $P(n)$ is true for all positive integers.

Fast Example 2

Theorem: Every tree (i.e. a graph which is connected and contains no cycles) has a leaf node.

Proof: Define $P(n)$ to be the proposition: “If T is a tree with n nodes, then T has a leaf node.”

(Base case) To show $P(1)$ notice that the only graph with one vertex has zero edges. It is therefore a leaf, and so T has a leaf.

(Induction case) Let k be any positive integer, and assume $P(i)$ for every $1 \le i\le k$. (This means that every tree of k vertices or less must have a leaf.) We need to prove $P(k+1)$ from the assumption.

Let T be a tree with k+1 vertices. Let v be any vertex, and consider the many different (disconnected) trees that may result from removing v from T.

Every one of these trees has at most k vertices and therefore has a leaf. (In the diagram above, the trees are made up of vertex groups {i,f,j} and {g} and {e} and {c,a,b,h}.) Take any such resulting tree, call it S. Say that u is a leaf of S. If u is not adjacent to v then u is a leaf of T and we’re done. Otherwise u is connected to v, in which case we consider two further cases: S is u (i.e. S has only one vertex, u) or not. If S is u then u is a leaf of T and we’re done. Otherwise we may remove u from S to obtain another tree S’, with leaf u’. Now u’ must be a leaf of T.

This now shows that T has a leaf, and therefore the inductive case has been proved. Because both the base case and inductive case hold, then the proof by induction is complete.

The Logic of Induction

Every proof by induction involves some kind of a “transfer principle” which takes us from case k to case k+1! If you imagine all of the cases laid out in a string:

A proof by induction is mostly about showing that this transfer principle holds! What you show in a proof by induction, is that if the property holds anywhere, then it must transfer to the next case. Of course you also have to show that the base-case holds — this is so that the transfer sequence has somewhere that it is guaranteed to start.

Can we think of a clear and easy “transfer property”? Is there some property that, if it holds at an integer k, must also hold for an integer k+1?

Sure, how about the property $P(k)$ defined by “k is greater than 5”. Notice that this is not true for k equal to 0 or 1 or 2 or 3 or 4 or 5. Therefore we will not try to prove this claim for these cases! However it starts being true at k=6. And if it is true at any integer k then it must also be true for k+1. Therefore this property does transfer, and a proof by induction will work!

The proof by induction would go: (Base case) For k=6 we obviously have 5 < k. (Inductive case) Assume 5 < k. Then 5 < k < k+1 and therefore k+1 is also greater than 5. This demonstrates the inductive case and therefore the proof by induction is complete.

Effectively the way that this proof works, is that it shows: First, in the base case, 5 < 6. But by the transfer principle, we know that if 5 < 6 then also 5 < 6+1. So 5 < 7. But also if 5 < 7 then also 5 < 7+1. So 5 < 8. And so on.

So in summary, the base case provides a starting point. The inductive case proves that the property we are discussing has the transfer property. Therefore the property transfers from the base case to the next case. Then the next case transfers to the one after it, and so on.

Looking back at the first fast example, the property in question was the property of the number n, that $1+2+\cdots+n = \frac{n(n+1)}{2}$. The inductive case for that argument, showed that this property is transferable. For the second fast example, it was a bit more complicated because this used “strong induction” rather than regular induction. Here, we could not just work from the case k to k+1. Rather we had to argue that “If the property holds for EVERYTHING up to k, then it holds for k+1”. However, the logic is not much different, except that we had to refer to all of the cases up to k, rather than k alone.

How Does Proof by Induction Make Any Sense?

Fast Example 1

Fast Example 2

The Logic of Induction