Proof by Induction

The word induction refers to any thought pattern which moves from specific examples to more general principles. The best known example of induction is probably the scientific method – we collect data by repeating the same specific experiments multiple times, find regularities and make guesses about a potential overarching framework into which the data might fit. This is what experimental scientists do, broadly speaking. While there is an analogy between this kind of inductive reasoning and the mathematical tool known commonly as mathematical induction, these are actually quite different. To explain the concept behind the mathematician’s version of induction, it will be helpful to think of dominoes.

Imagine you have a line of dominoes, as long as you’d like it to be, and that you are standing next to the first domino. Imagine you have lined up the dominoes so that each domino is very close to the one in front of it, so that one domino falling forwards will cause the other to as well. Now, via our common sense, we can see that if we knock over the first domino, then every domino will fall. It’s a cascading effect.

This is the idea behind the proof technique called mathematical induction. We’ll take a little time to flesh it out in detail before we put it to use, but when the math starts to show up, the analogy of the line of dominoes is quite helpful for conceptual clarity. In the domino situation, the two conditions that we needed to know about could be phrased as follows:

(1) Domino 1 fell over.

(2) If Domino n falls over, then so will Domino n+1 (since Domino n knocks it over).

Our conclusion from these points is that every domino will fall. 1 will knock over 2, which will knock over 3, which will knock over 4, and so on. So, every domino will fall. Using the same concept in a broader setting, suppose that we have some kind of statement which depends on some number n. For example, we could use P(n) as a shortcut for writing “n is even” or “n is a prime number” or “2n+7=17.” We can use this shorthand to ask which values of n cause P(n) to be true, and which do not. In the domino example, our statement P(n) would be “Domino n will fall over.” Using P(n) as a placeholder for the statements about dominoes, we can rewrite (1) and (2) in the following way.

(1) P(1) is true.

(2) If P(n) is true, then P(n+1) is also true.

Our conclusion is that P(n) is true for every positive whole number n. This even works if we have an infinite line of dominoes, because any particular domino you might choose will eventually be knocked over.

To give another analogy, imagine a tower with a ground floor labeled floor 1. Consider what would happen to (1) and (2) if you were to define P(n) to mean that “floor n is supported by the floors beneath it.” This provides yet another analogy for how the proof method I am describing works – the lower floors support the higher floors. I won’t write out this analogy in as much detail, but pausing to process this second analogy might be helpful in understanding the discussion to come.

The two steps we keep mentioning make up the technique of mathematical induction (which I will now just call induction for simplicity). There are no additional bells or whistles to it – all we need to know (once we know what P(n) is, of course) is whether (1) and (2) are true or not. Usually (1) is called the base case, since we can think of (1) as the foundation or base from which we build upwards (think of the building analogy), and (2) is called the inductive step.

To show how this kind of proof actually works, I will walk through the most common first example used in math classrooms when induction is taught – a shortcut for calculating 1 + 2 + 3 + \dots + (n-1) + n.

Theorem: For every positive whole number n, the formula

1 + 2 + 3 + \dots + (n-1) + n = \dfrac{n(n+1)}{2}

is true.

Before I move on to the proof, I want to put the question into the same language as I have been using, with P(n) and all that. We can define the claim P(n) to be the claim that 1 + 2 + 3 + \dots + (n-1) + n = \dfrac{n(n+1)}{2}. Thus, to prove this claim, we have two steps we must accomplish. The base case is to show that P(1) is true, and the inductive step is to show that we can use the truth of P(n) to prove the truth of P(n+1). Now, I won’t be writing P(n) in the actual proof, I will leave that as a mental exercise for you all. This paragraph should provide enough clarity to aid in understanding how the proof I’m about to write relates to the analogies of the dominoes and the building.

Proof: For the value n = 1, we have \dfrac{n(n+1)}{2} = \dfrac{1(1+1)}{2} = \dfrac{2}{2} = 1, and the sum of all numbers up to 1 is just 1. Therefore, the base case is true.

Suppose now that the theorem is true for a particular value of n, so that the equation

1 + 2 + \dots + n = \dfrac{n(n+1)}{2}.

is known to be true. We would like to show that the theorem is true for the value n+1, that is, that the equation

1 + 2 + \dots + n + (n+1) = \dfrac{(n+1)((n+1)+1)}{2}

is true (think about what P(n+1) is to understand the above formula). To see that this is true, we can see using our previous assumption of the truth of the equation for n that

1 + 2 + \dots + n + (n+1) = \big( 1 + 2 + \dots + n \big) + (n+1) = \dfrac{n(n+1)}{2} + (n+1).

The right-most part of the equation we have just derived can be rewritten using a ‘common denominator’ (since 2/2 = 1):

\dfrac{n(n+1)}{2} + (n+1) = \dfrac{n(n+1)}{2} + \dfrac{2(n+1)}{2} = \dfrac{n(n+1) + 2(n+1)}{2} = \dfrac{(n^2+n) + (2n+2)}{2} = \dfrac{n^2 + 3n + 2}{2}.

We can also observe by using the “foiling method” that (n+1)(n+2) = n^2 + 2n + 1n + 2 = n^2 + 3n + 2, and therefore we can see that

\dfrac{n^2 + 3n + 2}{2} = \dfrac{(n+1)(n+2)}{2}.

Following all of the equalities shows that the equation 1 + 2 + \dots + n + (n+1) = \dfrac{(n+1)(n+2)}{2} is true.

We have proven both steps, and therefore the original claim is itself always true. So, we are done with the proof.

The reason induction is worth learning is precisely for problems like this – where there is a kind of one-after-the-other connection between certain parts of the problem. When things are built out of smaller parts that look a lot like the bigger part, the technique of induction is often quite useful. It does take some time to build up intuition for this one though. And you do have the be extremely careful how you use it (look up the “all horses are the same color paradox” to see a misuse of induction if you are curious).

One thought on “Proof by Induction

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: