SICP - Tangent on Mathematical Induction

A tangent on mathematical induction which is related to my efforts at solving SICP Exercise 1.13

Table of Contents

Mathematical induction is a way of trying to mathematically prove stuff that involves a few different steps. A video I found uses the example of trying to prove that $3^n - 1$ is even for all values where $n ≥ 1$, and I'll talk about this example briefly here. This example is easier than the one I needed to figure out in order to solve SICP Exercise 1.13, because 1) there is only one base case to consider, and 2) the actual thing you're trying to prove is more straighforward, and thus, is something many people intuitively sense is true without needing to prove it using advanced math techniques. This example is a bit of a tangent, but was helpful for me to figure out SICP Exercise 1.13. It's useful to consider this example before considering the more complicated case in that Exercise, especially if, like me, you're coming into that Exercise asking "so, uhhh, what's a mathematical induction? 🤔"

So you have something you want to prove - some general mathematical statement - that's amenable to the mathematical induction technique. So then you come up with a base case. The base case is a concrete case of the overall pattern we are trying to prove. Since the $3^n - 1$ example involves proving a truth about when $n ≥ 1$, 1 is the natural base case to select - it's literally the first n we can choose in the range of values we're trying to say something about. So the base case is $3^1 - 1 = 2$. 2 is an even number. So we've proved that $3^n - 1$ is true when $n = 1$. But there are lots of n's and we don't want to do this for every case.

So then we come to what some people describe as the inductive hypothesis. We basically come up with a generalization related to the thing we just demonstrated in the base case. For our example problem the inductive hypothesis might be "Suppose that $3^n - 1$ is even for some $n ≥ 1 $". We just saw an example of that hypothesis being true for an $n$ in the described range - namely $n = 1$. We don't know it's true for any given $n$ in that range, but we know that it's true for a particular $n$ where $n ≥ 1$ (namely, when $n = 1$). So I think the inductive hypothesis basically involves assuming that the statement of the hypothesis is true for any particular $n$ and using that assumption to prove that it's also true for when $n = n + 1$. And then, when we prove the truth of the statement for $n+1$, that proof lets us generalize about a whole range of $n's$. But we do need the assumption at the beginning. And proving the base case helps keep the inductive hypothesis somewhat grounded in reality, since we can't just fly off and make assumptions that aren't true for any $n$'s if we have to prove that they are true for at least 1 $n$.

We need to state the inductive hypothesis in terms of some $n$ because that's what we need for the purposes of the "inductive step". If we tried to just start from the case we proved, where $n = 1$, then we'd have to proceed step by step (from $n = 1$ to $n = 2$ and so on) if we wanted to make some claim about, say, when $n = 42,000$. Lots of work. But with the inductive hypothesis, we can pick any number in the number line and start from there and say, "ok, let's assume it's true that this $3^n - 1$ is even for this particular $n$" and then use that fact to make claims about $n + 1$, and, by extension, the whole set of values to the right of that $n$ on the number line.

So we have our base case and inductive hypothesis. So now we try to take the "inductive step". We want to say, okay, assuming this inductive hypothesis that we've just demonstrated is true for some specific, concrete n (in the base case) is in fact true for any given n (as claimed by our inductive hypothesis), let's prove that it's true for when $n = n + 1$. Or, to use concretes, we've seen that $3^n - 1$ is true when $n = 1$. That's consistent with our inductive hypothesis, which says that for any particular $n$ where $n ≥ 1 $, $3^n - 1$ is even. Let's stipulate that the hypothesis is true. If we do that, then starting from any given $n$ where $n ≥ 1 $, we cab be assured that the statement will still be true. E.g. if we know that $3^1 - 1$ is true, which we saw already, and we can also prove that "$3^n - 1$ is even for some $n ≥ 1 $" is also true where $n = n+1$, then we'll know that $3^2 - 1$ is even, since 2 is just our original $n + 1$. And if we can know that, we can know that $3^3 - 1$ is even, and that $3^4 - 1$ is even, and so on, through infinity. Or we can start from n = 42,000, and we assume that's true per the inductive hypothesis, and then, if we've proved that $3^n - 1$ is even when $n = n + 1$, we can know all the values of n to the right of 42,000 on the number line are also even when evaluating $3^n - 1$.

Okay so how do we prove anything about $3^{n+1} - 1$ being even?

Here's an approach (based on this video):

$3^{n+1} - 1$

$= 3^{n}3^1 - 1$

$= 3^1(3^n) - 1$

$= (2 + 1)(3^n) - 1$

$= 2(3^n) + 3^n - 1$

So our inductive hypothesis is that $3^n - 1$ is even. We see that on the right.

And to that presumably even number, we are adding $2(3^n)$. So we're adding a number that has 2 as a factor, so that's going to be even. So we're adding two even numbers. So we proved $3^{n+1} - 1$ is even. Hurrah!

Update: removed an erroneous line pointed out by Max.