An alternative approach to proof by induction

Question

In my experience, the 'standard' method for proof by induction can often cause confusion. In this post, I propose a slightly different way of conceptualising proof by induction that does not involve making an 'assumption'. (Of course, it turns out that this assumption is entirely justified, but my hope is that my method is less likely to cause confusion.) To begin with, here is the way is the way that proof by induction is laid out in many textbooks:

• Prove a statement is true for the 'base case'—usually, $n=0$ or $n=1$
• Assume the statement is true for $n=k$
• Show that if the statement is true for $n=k$, then it is true for $n=k+1$
• Thus, the statement is true for all $n \in \Bbb{Z}^{\geq0}$ or $n \in\Bbb{Z}^+$ (depending on the base case)

My alternative method goes like this:

• Show that if the statement is true for $n=k$, then it is true for $n=k+1$
• Show that the statement is true for the base case (e.g. $n=1$)
• Thus, the statement is true for $n=2$, $n=3$, $n=4$, $\dots$ . In other words, the statement is true for all $n \in \Bbb{Z}^+$

Though the 'standard' method might be more practical, I hope that my alternative method helps foster a more intuitive understanding of what proof by induction does, and explains why the 'assumption' made in the standard method isn't really an assumption.

I will use the statement 'the sum of the first $n$ odd numbers is always equal to $n^2$' as an example.

Answer 1

Here is the standard way to approach this problem. Let $S_n$ denote the sum of the first $n$ odd integers:

• When $n=1$, we have one odd number: $\{1\}$. The 'sum' is therefore also equal to $1$
• When $n=k$, we have $k$ odd numbers: $\{1,3,5,\dots,2k-1\}$. We assume that $S_k=1+3+5+\dots+(2k-1)=k^2$
• When $n=k+1$, we have $S_{k+1}=1+3+5+\dots+(2k-1)+(2k+1)$. We know that $1+3+5+\dots+(2k-1)=k^2$, and $S_{k+1}=k^2+(2k+1)=(k+1)^2$.
• Thus, the statement is true for all $n \in \Bbb{Z}^+$

However, there are several questions that a student might have:

1. Why did we show that the statement was true for $n=1$ if it used nowhere else in the proof?
2. Why can we assume that the statement is true for $n=k$ without showing it? The fact that $1+3+5+\dots+(2k-1)=k^2$ is not a trivial result, and yet we seem to take it for granted.

My hope is that my method can answer these questions with clarity:

• First, we must show that if $S_k=k^2$, then $S_{k+1}=(k+1)^2$: $$S_{k+1}=S_{k+1}=1+3+5+\dots+(2k-1)+(2k+1)=k^2+(2k+1)=(k+1)^2$$

In this step, we are not really making an 'assumption'. We are saying that if $S_k=k^2$, then $S_{k+1}$ must equal $(k+1)^2$. It's like saying 'if John jumps into the pool, then he will get wet'. This is a conditional statement that explains what will happen if something else happens. In the same sense, we are looking at the result of $S_k$ equalling $k^2$. We are not saying that this is true; we are not saying that this is false. We are merely looking at what we can conclude if $S_k$ does indeed equal $k^2$.

That being said, the fact that 'if John jumps in the pool, then he will get wet' isn't particularly helpful if John doesn't jump in the pool. Similarly, the fact that if $S_k=k^2$, then $S_{k+1}=(k+1)^2$, isn't very helpful if $S_k$ doesn't equal $k^2$. This is where the base case comes in:

• $S_1=1=1^2$

Here, we have shown that for $k=1$, the statement holds. Then, we can conlude it is true for $k+1=2$. Then, we can set $k=2$, and show that the statement is true for $k=3$, and so on. Thus, we have shown that the statement is true for all $n \in \Bbb{Z}^+$.

The base case is important because it shows that the statement holds for at least one value of $k$ (in this case, $k=1$). If we can't show that the statement is true for a specific value, then induction doesn't help us. However, once we have a starting point—the base case—we can on from there, and prove a statement for all positive integers. This is why proof by induction is often said to be like a domino trail:

Do you see that first domino there? That's the base case—the starting point in the chain reaction that is proof by induction. Thank you for reading.

Answer 2

I think that, more important than the question if you call "the statement is true for n" an assumption or an conditional, you should show the students what can go wrong if you miss the base case. Thus, besides cases where induction works, you should always also discuss cases where it doesn't. A possibility is: "show, by induction, that n=n+1" (obviously wrong). So we first do the inductive step: assume that n-1=n. Then, n=(n-1)+1=(n)+1=n+1. Then write down "q.e.d." or something. And now, let the students explain what went wrong.

Answer 3

In fact the importance of the base case can be illustrated with the notorious "prove all things have a common property".

Let's take for instance red cars, but you can do as well with Scottish ghosts if you prefer.

$$P(n)=\text{"If a set contains }n\text{ cars, they are all the same color}"$$

The base case $P(1)$ is trivially true since there is one car, it is of its own color.

Now let's examine $P(n+1)$ we have $n+1$ cars, pick one and set it aside.

Remains a set of $n$ cars, so they are all of the same color.

So pick any of them and swap it with the removed one. We again have a set of $n$ cars so they all are the same color too. Since the swapped one was already of this color, then $P(n+1)$ is verified and all cars in the world are of the color.

Since mine is red, then all cars are red.

The issue with this is the comparison to a same third party, i.e. we need $P(2)$ true which is not the case in general.

The base case is not necessarily $0$ or $1$, it is what we need to enforce the induction. Whether we do it before or after the $P(n)\implies P(n+1)$ is not so important. In our case despite verifying $P(1)$ as a starting point, we saw during the proof that we needed $P(2)$ too so it becomes a new base case to verify a posteriori.

---

I commented on an induction proof that went wrong some time ago.

https://math.stackexchange.com/a/2062423/399263

I showed why we are forced to adjust the base case and verify up to $P(5)$ for the proof to work.

I agree with you that sometimes it makes sense to verify the base case a posteriori, but not exactly for the same reasons you invoke, more because the proof $P(n)\implies P(n+1)$ required some $P(n_0)$ to be true during the process for some specific $n_0$.