Is there any example of a "forwards/backwards" induction?

Question

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

I recently came across the following video:

https://www.youtube.com/watch?v=-BTWiZ7CYoI

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".

Answer 1

Answered in comments:

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

Answer 2

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.