Question about rigor when it comes to proof by induction

Question

I have a general question concerning "rigor" when it comes to proof by induction. I make instructional videos about math, and I was in the process of planning a video on this topic. So I did what I always do before I make a video, which is check out other videos on the topic to see how other people are teaching / explaining it. What I found is that a lot of people are teaching the proof by induction method in a way that is (in my opinion) a lot less rigorous than the way I was taught. It just doesn't seem right.

So I figured I'd ask for a second opinion, since I'm sure some of y'all have a lot more experience with this than I do.

The way I was taught was: first show the basis step (show the statement is true when $n=1$). Then assume the statement is true when $n=k$, and USE THIS ASSUMPTION to show the statement is true when $n=k+1$.

This is where I see people going two different directions. Some people are doing it the way I was taught, which is that you have to work with the induction hypothesis to conclude the statement is true when $n=k+1$. Others however, are assuming the induction hypothesis, then writing something like "this is what we want to show:", then modifying what they want to show (the statement that $n=k+1$) until they arrive at something that is true (typically the induction hypothesis). Technically, I don't think they are making any extra assumptions, but for some reason it feels like they are working backwards and seems kind of sloppy. Am I right about this, or am I being too critical? I'm very interested to hear y'alls opinions. Thanks!

Answer 1

I usually handle it the way you were taught, i.e., use the induction hypothesis to prove it's true for $n = k + 1$. You can work backwards, i.e., go from the $n = k + 1$ step back to $n = k$, as some people do, but I believe it's generally not a good idea to do it this way. This is because this method only works properly if all of the steps are reversible, i.e., you can take the steps that were used and also do them backwards, i.e., effectively do the procedure the way you initially described.

One main issue I have with teaching students to do it the second way is you need to emphasize the reversibility aspect, so it unnecessarily complicates the procedure. Also, students may forget to check for this, thus possibly ending up with an incorrect proof. I don't really see any particular advantage to it, and several disadvantages, so I would not recommend it.

Answer 2

What you're observing is a common fallacy that's far wider than just induction. It's something that I think most students stumble over at some point in their mathematics studies: the temptation to start with what you want to prove, and reduce it to something true. The problem is that $P \implies Q$, where $Q$ is true, does not imply $P$ is true. In this way, it's a variation on Affirming the Consequent.

As a non-induction example, consider the identity $$\frac{\cos(x)}{1 + \sin(x)} = \frac{1 - \sin(x)}{\cos(x)},$$ where $\cos(x) \neq 0$. Most students will proceed something like this: \begin{align*} \frac{\cos(x)}{1 + \sin(x)} &= \frac{1 - \sin(x)}{\cos(x)} \\ \cos^2(x) &= (1 - \sin(x))(1 + \sin(x)) \\ \cos^2(x) &= 1 - \sin^2(x), \end{align*} therefore it's true.

Reading a list of statements like this, the most common way to interpret this as a logical argument is to insert the logical connector $\implies$ between each pair of equalities. However, what students don't seem to grasp is that it's actually the $\impliedby$ direction that's important! From the true fact that $\cos^2(x) = 1 - \sin^2(x)$ (and the assumption $\cos(x) \neq 0$), we can derive the equality that we want, simply by following the steps backwards.

Of course, one can make this argument valid, simply by explicitly including the $\impliedby$ between each step, but it's important that students check that every step can be done backwards.

So, in short, yes, I think you should teach it the way you were taught. It is indeed more rigorous. While showing that $P(n+1) \implies P(n)$ is all well and good if you can safely reverse the steps, it is absolutely better if the students prove the more relevant implication, $P(n) \implies P(n+1)$, and know that this is what they're supposed to be proving.