4
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your response! That makes a lot of sense. If I'm honest, I'm having trouble even coming up with an example of an induction proof where the steps are not reversible. Do you know of an example off the top of your head? $\endgroup$ – Brain Gainz Apr 2 at 4:30
  • $\begingroup$ @BrainGainz You're welcome. What I've found to be the most common type of non-reversible step is squaring since, apart from $0$, there are $2$ possibilities for the original values. I can't think of any induction proof which could involve this off the top of my head, but I'll think about it & get back to you if I come up with anything. $\endgroup$ – John Omielan Apr 2 at 4:34
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ These same students who get into a pattern of proving $P(n + 1) \implies P(n)$ tend to really struggle to parse induction proofs where $P(n)$ has a $\forall$ quantifier. For example, "Every tree on $n$ vertices has $n - 1$ edges". They get that there must be vertex of degree $1$, and that removing that vertex and connecting edge must leave a tree of one fewer vertices, but they don't tend to get how to connect this to the induction hypothesis. $\endgroup$ – user764828 Apr 2 at 4:15
  • $\begingroup$ Thanks for your response. My follow up question is, how would you handle a proof involving divisibility? I ask this because I realized I contradicted my own beliefs when approached with a divisibility proof. For example, prove $7^n - 4^n$ is a multiple of 3 for each $n\in\mathbb{N}$. I completed the basis step, assumed $7^k - 4^k$ was divisible by 3, then jumped to $7^{k+1}-4^{k+1}$ and started manipulating it to try to show it was equal to 3 times some integer. I realized I was using the exact approach I had a problem with, but for some reason in this context it felt OK. Any thoughts? $\endgroup$ – Brain Gainz Apr 2 at 4:29
  • $\begingroup$ @BrainGainz Nothing wrong with that. You can assume $7^n - 4^n = 3k$ for some $k$, and see that$$7^{n+1} - 4^{n+1} = 7(7^n - 4^n) + 3 \dot 4^n = 7(3k) + 3 \cdot 4^n = 3(7k + 4^n),$$ which is divisible by $3$. This is an algebraic manipulation of one single expression, and each step is a number equal to the previous number. At the end, we conclude, as we should, that the number can be written in the form $3k'$. We're not assuming the conclusion is true by considering the number $7^{n+1} - 4^{n+1}$, and none of our steps rely on it being divisible by $3$. $\endgroup$ – user764828 Apr 2 at 8:47
  • $\begingroup$ Wow, that makes so much more sense. Thank you. I'm wondering (if you have time) what you think of this proof: youtu.be/dMn5w4_ztSw - He assumes the induction hypothesis, writes out what he's trying to show, does a substitution, then manipulates both sides of the equation until he gets to a true statement. I assume that if you are starting with what you want to show, you want to conclude with what you assumed and then use backwards arrows to indicate the proof is "backwards". Is it legitimate to end at a random true statement like he did in the video? Thanks so much for your time btw. $\endgroup$ – Brain Gainz Apr 2 at 14:01
  • 2
    $\begingroup$ @BrainGainz This is what I was talking about in my answer. He starts manipulating the equation he wants to prove, and reduces to an obviously true statement. (He also does this a bit in the base case.) To his credit, if you listen to what he says (instead of just reading what he wrote), he does say some of the right things to indicate he understands which way the logic is flowing (e.g. "So, if we can just prove this, we'll be done.", instead of saying "Therefore we have..."), but ultimately his write-up doesn't reflect this. The written proof looks like he is assuming what he needs to prove. $\endgroup$ – user764828 Apr 2 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.