# Is there any example of a “forwards/backwards” induction?

I like to make the "dominoes" analogy when I teach my students induction.

I recently came across the following video:

In this video, a sequence of concrete block wall caps are set up like dominoes on the top of a wall. The first wall cap is knocked down, setting off the domino effect. The blocks are spaced so that they are resting on each other when they fall, but just barely. So rather than resting flat each block is supported slightly by its successor. When the last block falls, however, it falls flat (having no subsequent block to rest on). This causes the block behind it to slip off, and lay flat, which causes the brick behind it to slip off and lie flat, until all the blocks are lying flat perfectly end to end.

Is there any instance of a similar phenomena occurring in mathematics? I am thinking of a situation in which you want to prove both $$P(n)$$ and $$Q(n)$$ for $$n = 1, 2, 3, \dots, 100$$ (say). If you are able to prove:

1. $$P(1)$$
2. $$\forall k \in \{1,2,3, \dots, 99\} P(k) \implies P(k+1)$$
3. $$P(100) \implies Q(100)$$
4. $$\forall k \in \{ 100, 99, 98, \dots, 3,2\}, Q(k) \implies Q(k-1)$$

Then it will follow that both $$P(n)$$ and $$Q(n)$$ are true for $$n = 1, 2, 3, \dots, 100$$.

If an example is found, it could be a great example for teaching because it would force students to think through the logic of why induction works rather than blindly following a certain form of "an induction proof".

• brilliant.org/wiki/forward-backwards-induction – Bill Cook Nov 9 '18 at 3:35
• @BillCook That is a nice form of induction! I am actually thinking about giving students a few examples, and having them try to create their own inductive methods. – Steven Gubkin Nov 9 '18 at 10:34
• The link to the youtube video might expire. Could you provide a short summary of what it is about and how it relates to your question? – Joel Reyes Noche Nov 9 '18 at 11:50
• Maybe not quite what you're looking for, but have you heard of Cauchy induction? You prove your base case, then you prove that $P(n) \implies P(2n)$ and that $P(n) \implies P(n-1)$, which covers all cases. – Mike Pierce Nov 9 '18 at 16:12
• @MikePierce This is actually the same type of induction that Bill Cook posted above. – Steven Gubkin Nov 10 '18 at 13:06

brilliant.org/wiki/forward-backwards-induction – Bill Cook Nov 9 '18 at 3:35

Maybe not quite what you're looking for, but have you heard of Cauchy induction? You prove your base case, then you prove that $$P(n) \implies P(2n)$$ and that $$P(n) \implies P(n-1)$$, which covers all cases. – Mike Pierce Nov 9 '18 at 16:12

• The only example of this "Cauchy induction" that is paraded everywhere is the AM-GM inequality, but it is a terrible example, and in my opinion should never be taught, for two reasons: (1) Students who are unable to use induction correctly (including for predicates with nested quantifiers) would gain nothing from an attempt to teach them this kind of 'induction'. (2) There is an extremely easy proof of AM-GM that uses ordinary induction. – user21820 Nov 28 '20 at 17:08
• @user21820 I think the student has something to gain: namely, flexibility in their reasoning. I don't want them to think of "induction proofs" as being one rigid mold to follow (without understanding). The "Cauchy induction" argument forces the student to track through the sequence of implications leading to the conclusion. – Steven Gubkin Nov 28 '20 at 18:00
• Well, in my experience, it caused nothing but more confusion to students who were incapable of handling ordinary induction properly, and it didn't benefit those who were. That said, it's just my words, so I can't possibly expect you to assume what I say as true just like that. =) – user21820 Nov 28 '20 at 18:08

I am not a fan of the so-called "Cauchy induction" mentioned in the other answer, for the reasons mentioned in my comment there. So here is my own offered answer (taken from an earlier post of mine):

Given $$f:\mathbb{Z}{\to}\mathbb{R}$$ such that $$f(0) = 0$$ and $$f(1) = 1$$ and $$f(x{+}1) + 6 f(x{-}1) = 5 f(x)$$ for any $$x {\in} \mathbb{Z}$$, prove that $$f(x) = 3^x - 2^x$$ for any $$x {\in} \mathbb{Z}$$.

Any student that can give a correct proof of this statement has at least an intermediate level of understanding of induction. Actually, difficulty in understanding induction has nothing to do with "backward-forward", but simply has to do with not being taught how to do rigorous reasoning. It definitely is impossible for anyone who is familiar with an FOL deductive system to be unable to understand induction properly, as it is completely obvious what exactly induction means from the nature of formal deduction itself, as explained here. Furthermore, it is impossible for anyone who knows how to construct formal FOL proofs to use induction wrongly in any way whatsoever.

So why is it that people do not want to teach students formal FOL deduction? I have no idea. In my teaching experience, it takes much less time for students to learn to use a reasonable Fitch-style system (such as this variant) than to use a common programming language, and once they learn it they will never again be unclear about what is illogical about their arguments, because it is simply an open-and-shut case whether or not they can produce a formal proof.

In other words, the phenomenon of students not understanding induction is merely a symptom of the real problem of not understanding basic logic. Solve that true malady and all bad symptoms (including induction issues, quantifier swapping, choice confusion, and so on) disappear automatically.

• "Furthermore, it is impossible for anyone who knows how to construct formal FOL proofs to use induction wrongly in any way whatsoever" is this a tautology, or a meaningful statement? Every mathematician, no matter how great, makes mistakes occasionally. I do not doubt that even the greatest have occasionally has a logical misstep in a particularly delicate induction argument. – Steven Gubkin Nov 28 '20 at 18:03
• @StevenGubkin: It was not supposed to be a formal statement. Of course, I am excluding careless errors. The main point was simply that everyone who has a proper grasp of basic FOL deduction will never make a conceptual error regarding induction. If they make a careless error and it is pointed out to them, they will be able to see 100% clearly that they are unable to construct a formal proof unlike what they originally thought, and hence know 100% certainly that they were wrong. – user21820 Nov 28 '20 at 18:05
• I feel that I would be more receptive to your ideas if they were presented with less force and certainty. I very much doubt that training students in formal logic (in the manner you describe) will so clearly resolve student difficulties. A piece of anecdotal evidence: my uncle was a very fine philosopher, who worked (among many other things) on understanding and correcting Frege's work. He taught courses on symbolic logic. He was a brilliant man with wide ranging interests. Despite all this, he had some deficits in his mathematical reasoning skills. – Steven Gubkin Nov 28 '20 at 18:11
• In my experience, he relied quite heavily on the formal manipulations of the logical symbols to make up for some blind spots. I think he would have taken quite some time to fully digest the proof of theorem you give here, and he may have had difficulty proving the theorem himself. – Steven Gubkin Nov 28 '20 at 18:14
• @StevenGubkin: I really don't expect to convince you just by what I say here. What I say is merely based on what I observed in my actual teaching. I can't evaluate your anecdotal evidence properly as there is too little information. For one, I am specifically advocating for Fitch-style natural deduction and no other. Indeed, I don't even claim (or believe) that knowing other deductive systems will help much in eliminating logical errors, because they are unusable except for really tiny toy examples, and hence they don't get used in practice. – user21820 Nov 28 '20 at 18:23