# 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