Today, we will discuss a fundamental proof technique that can be used to prove properties of natural numbers (or any other mathematical structures that have minimal elements; we will get back to this a bit later).

Most of you have probably already run into the concept of mathematical induction, which states that if you want to prove that a property holds for every positive natural number N, then it is sufficient to do the following:

(1) Show that the property holds for N = 1.

(2) Show that if the property holds for a positive natural number N, then it must also hold for the number N + 1.

This is essentially it! Step (1) is usually called the base case, while step (2) is called the inductive step. We will now make things a bit more precise, and we will also discuss some examples.

Suppose that you have a statement that is parameterized by a natural number N; let’s denote this as P(N). For example, such a statement could be the following:

• P(N) : “The number N is divisible by 2.”
• P(N) : “(N + 1)² ≥ 0.”

Clearly, the first statement is not true for every natural number N, as it only holds for even numbers, while the second statement is true for every natural number N. When you are dealing with such statements, one way to prove that they hold for every natural number N (if they actually hold) is by using the strategy described above.

A few more details

Let’s see now why this strategy, given that it succeeds, indeed shows that the statement holds for every natural number N.

As stated above, we have to have a starting point. The starting point might be N = 1, but of course it can be any other natural number as well (including 0). Depending on what is the starting point (base case), the statement we prove is valid for all natural numbers that are at least as large as our starting point.

So the first step is to prove our base case. Let’s assume that we manage to prove that our statement indeed holds for a natural number Nₒ .Thus, we can now write that P(Nₒ) is true.

Once we have that, then the second part (inductive step), is to show that if the statement holds for any given number N ≥ Nₒ , then it also holds for the number N+1. This can be thought of as a scheme for generating a proof that the statement P(N) is true for every number N ≥ Nₒ as follows. Given a number N ≥ Nₒ and our base case, we can show that P(N) is true by the following procedure:

• First, we can apply our scheme to show that P(Nₒ + 1) is true.
• Once we have that, we can again apply our scheme to show that P(Nₒ + 2) is true.
• Again, we can apply our scheme to show that P(Nₒ + 3) is true.
• …. (you see where we are going with this)

By applying our scheme sufficiently many times, we will eventually reach the number N-1, and the last application of our scheme will show that P(N) is true.

This is the essence of mathematical induction. I hope, by now, that it is clear that this strategy will never fail, as long as we have ensured that the base case and the inductive step are both true. The domino effect is really a great analog of the above process. The inductive step ensures that “dominoes are placed closed to one another, such as if one falls, then the next one will fall as well”. The base case ensures that “the first domino is indeed pushed”.

Some variants

Induction is primarily used to prove statements for the natural numbers, but in fact, it is more diverse than that. First, it can be used to prove statements for a finite set of natural numbers. For example, if you need to prove that a statement holds for every natural number between 1 and M (where M ≥ 1 is some natural number), then you can still apply the above strategy.

Moreover, a variant known as strong induction (which is equivalent to the original version of induction), is sometimes very useful. The only difference is that we replace the inductive step by the following variant:

(2') Show that if the property holds for every positive natural number smaller or equal to N, then it must also hold for the number N+1.

A typical example of a set where induction cannot be applied, at least as is, is the set of real numbers. Observe that there is no clear starting point to use as base case (e.g., think of the set of positive real numbers), and no obvious way to define the “next” real number in the inductive step, and so the above strategy will not work. Nevertheless, there are much more advanced forms of induction that allow you to work with uncountable sets (see, e.g., transfinite induction and well-founded structures), but these are out of scope for this article (and definitely, I am ignorant enough about these so I should not write about them!).

Two examples

We will now look at two examples, to digest what we just discussed.

Example #1

Show that the following statement is true for every natural number N > 0:

In the above, we use the notation:

To prove the above statement, we apply the standard mathematical induction.

Base case: For N = 1, it is easy to see that the left-hand side of the statement is equal to 1, while the right-hand side is equal to 2/2 = 1. Thus, the base case holds.

Inductive step: Suppose that the statement is true for some number N ≥ 1. We will show that the statement is then true for the number N + 1. We again analyze both sides of the statement, but first, let’s write down what the inductive hypothesis guarantees. It tells us that the following holds:

Let’s now look at the left-hand side of the statement we want to prove. We have

Note here that the “magic” happened at the 3rd line of the above derivation, where we used exactly what the induction hypothesis implied. Looking at the final term, we conclude that this matches the right-hand side of the statement P(N+1). Thus, the statement holds for the number N+1, and the inductive step is complete. We are done!

Example #2

Our 2nd example, although not directly a statement about natural numbers, can be formulated in such a way such that it is parameterized by natural numbers, and thus, we can apply induction to it. First, we need the definition of a rooted binary tree. Roughly speaking, a rooted binary tree has a root (one vertex/point), and at most 2 children (vertices/points it connects to). Each child is itself a rooted binary tree. You can check the Wikipedia entry for a formal definition, but the crucial property to keep in mind is that every vertex has distinct children; in other words, no two vertices connect to the same child. Thus, there are no cycles in the final graph. Here is a visualization of a binary tree:

In the above picture we have the following:

• Vertex A is the root and its children are the vertices B and C.
• The only child of vertex B is D.
• Vertex C has two children, E and F.
• Vertex E has one child, G.
• Vertex F has two children, H and I.
• The vertices D, G, H and I have no children. Such vertices are called leaves.

A key quantity associated with binary trees (and in fact, all rooted trees) is the height of the tree. The height is a natural number that measures how many “levels/layers” the tree has. In the example above, we have:

• The root (vertex A) is at level 0.
• The vertices B and C are at level 1.
• The vertices D, E and F are at level 2.
• The vertices G, H and I are at level 3.

Thus, the height of the above tree is equal to 3.

Finally, we define the size of the tree to be equal to the number of vertices it contains. In our example, the size is equal to 9.

We are now interested in proving the following statement for rooted binary trees.

Show that following statement is true for every N≥ 0:

Before proving the above statement, let’s do a sanity check by using the example in the picture above. As stated, the tree in the picture has height 3 and size 9. We have 2⁴-1 = 16–1 = 15 > 9. So, the statement holds for our example. Let’s now prove it for all rooted binary trees.

To prove such a statement, we will use strong induction. As a comment, trees are in general great for using induction, due to their recursive structure; this will hopefully become clear in the proof.

Base case: For N = 0, a rooted binary tree of height 0 consists of only one vertex, the root, and so it has size 1 = 2¹-1. Thus, the base case holds.

Inductive step: Suppose that the statement is true for all rooted binary trees of height at most N ≥ 0; this is our inductive hypothesis. We will now show that the statement also holds for rooted binary trees of height N + 1. Let T be any rooted binary tree whose height is N + 1. The tree T has a unique root which belongs to level 0; let’s denote it as vertex A. Note that since the tree has height strictly larger than 0, then it means that vertex A has at least one child (and at most two children). We now do some case analysis:

Case 1: Vertex A has exactly one child, which we denote as vertex B. In this case, we remove vertex A from the tree, and we end up with a rooted binary tree rooted at vertex B; let’s call this tree Tₒ. It is easy to see that the height of Tₒ is equal to N. We now use the inductive hypothesis on the tree Tₒ, which states that its size is at most

Thus, we have that

We note that in the inequality in the 5th line above, we used the fact that for every N ≥ 0, we have that

We conclude that the statement holds in this case.

Case 2: Vertex A has two children, vertices B and C (as in the example in the picture above). We again remove vertex A, and we end up with two rooted binary trees, one rooted at vertex B and one rooted at vertex C. Let T₁ denote the binary tree rooted at vertex B and let T₂ denote the tree rooted at vertex C. It is easy to see that both T₁ and T₂ have height at most N. Thus, we can use the inductive hypothesis on both of the trees, which gives that

We now have that

We conclude again that the statement holds in this case.

To finish the proof, we note that we did not make any assumption about the tree T, and so the above statement holds for any tree of height N + 1. We are done!