The principle of mathematical induction is a simple but powerful technique for proving mathematical results. In its most basic form, it says the following:

If something’s true for an integer n_0, and if it being true for the number k implies it is true for the number k+1, then it is true for all integers n \ge n_0.

This is a more-or-less “obvious” statement. It has two components: the base case and the inductive step. The base case establishes truth for one number. The inductive step does not actually establish truth of the statement for any particular value. Instead, it establishes the truth of a logical implication. In formal terms, the above box reads:

If P(n) is a proposition for the integer n, then if P(n_0) is true and P(k) \Rightarrow P(k+1), then P(n) is true for all integers n \ge n_0.

Think of induction as a string of dominos. Establishing the base case is like knocking down the first domino. Establishing the inductive step is like setting up the dominos so that if the k-th domino falls, it knocks over the (k+1)-th domino. Thinking of it this way, it should be obvious that once these two things are established, then all the dominos will fall. This is one of the concepts that is best learned through examples.

Let’s prove a basic result using induction. We will prove that 1 + 2 + 3 + \cdots + n = n(n+1)/2. We begin with the base case. Is it true for n= 1? Yes, because the left-hand side is 1 and the right-hand side is 1(1+1)/2 = 2/2 = 1. Now we establish the induction step. If it’s true for n=k, is it then true for n=k+1? Let’s see. We begin with 1 + 2 + 3 + \cdots + k + (k+1). Since we are assuming that it’s true for n = k, we can rewrite the first k terms as 1 + 2 + 3 + \cdots + k = k(k+1)/2. Then our sum becomes

\displaystyle 1 + 2 + 3 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) \\ = (k+1)\left( \frac{k}{2} + 1 \right) \\ = \frac{(k+1)(k+2)}{2}

which is the formula we wanted for k+1, so the formula is true for all positive integers n. Let’s go over why this works again. We showed the formula is correct when n = 1. We then showed that if the formula is correct when n = k, then it is also correct when n = k+1. Why does this mean the formula is correct for any n? Well, it’s correct for n = 1. By the inductive step, since it’s correct for n = 1, it’s also correct for n = 1 + 1 = 2. By the inductive step again, since it’s correct for n = 2, it’s also correct for n = 2 + 1 = 3, and so on.

Now we’ll prove a more interesting result using induction. Consider the question: how many subsets (including the empty set) of \{1, 2, 3, \ldots, n\} are there that contain no consecutive integers? For problems like these, it’s always nice to look for a pattern first, in case the formula for the answer is nice. For \{1\}, both the empty subset and the entire set work, so the answer is 2. For \{1,2\}, the subsets \varnothing, \{1\}, \{2\} all work, so the answer is 3. For \{1,2,3\}, the subsets \varnothing, \{1\}, \{2\}, \{3\}, \{1,3\} work, so the answer is 5. Continuing in this way, we’ll see that the answer for the first few values of n are 2,3,5,8,13,\ldots. These look like the Fibonacci numbers! We know that the Fibonacci numbers F_n are defined by a recurrence relation F_n = F_{n-1} + F_{n-2}, so maybe the answer we’re looking for also satisfies this recurrence. That is, we conjecture (or guess) that T_n = F_{n+2}, where T_n is the answer we’re looking for and F_1 = F_2 = 1.

To prove our conjecture, we can use induction, so we just need to show that T_1 = F_3, T_2 = F_4 , and T_n = T_{n-1} + T_{n-2}. As an exercise, convince yourself why this is enough to answer our original question. The base cases we just did: T_1 = 2 = F_3 and T_2 = 3 = F_4. Now, let’s establish the relation T_n = T_{n-1} + T_{n-2}. Let’s call a set “happy” if it contains no consecutive integers (so our original question is to find the number of happy subsets of \{1,2,3,\ldots,n\}). Suppose we have a happy subset S of \{1,2,3,\ldots,n\}. What do we know about S? Well, it either contains the number n or it doesn’t. If it doesn’t, then it’s just a happy subset of \{1,2,3,\ldots,n-1\}, and we know there are T_{n-1} of those. If S does contain n, then it can’t contain n-1 or else it wouldn’t be happy. Then, if we ignore n, then the rest of S is a happy subset of \{1,2,3,\ldots,n-2\}, of which we know there are T_{n-2}. Therefore, T_n = T_{n-1} + T_{n-2} and we are done!

To recap, you should have learned the following from this post:

  • What the principle of mathematical induction is and how it works
  • How to use induction to prove mathematical statements
Advertisements