Forward-backward induction

Question

I've seen the famous proof presented by Cauchy for the AM-GM inequality but what other neat proofs use forward-backward induction? Is it fundamentally inextricable from ordinary induction (are there no problems where only forward-backward induction will do the trick and not ordinary induction)? Are there other even more variants of induction like this that have their own uses? Any material one could refer to that deals with more useful examples of FB induction?

Answer 1

Here's an example of one I ended up using the other day. I was trying to determine all functions $f$ which are analytic on their domain (some disk about $0$ in the complex plane), and such that there is a complex number $c$ such that $$f(z)=c+zf\bigl(z^2\bigr)$$ for all $z$ in the domain of $f.$

I began by using analyticity in a disk about $0$ to conclude that $$f(z)=\sum_{n=0}^\infty a_n z^n,$$ so that $$zf\left(z^2\right)=z\sum_{n=0}^\infty a_n \left(z^2\right)^n=\sum_{n=0}^\infty a_n z^{2n+1}.$$ Noting that we can rewrite $$f(z)=\sum_{n=0}^\infty a_{2n} z^{2n}+\sum_{n=0}^\infty a_{2n+1} z^{2n+1},$$ we find that $$f(z)-zf\left(z^2\right)=\sum_{n=0}^\infty a_{2n}z^{2n}+\sum_{n=0}^\infty (a_{2n+1}-a_n)z^{2n+1}.$$ Since we need this to be equal to $c,$ then we must have $a_0=c,$ $a_{2n}=0$ for all positive $n,$ and $a_{2n+1}=a_n$ for all $n.$

After playing around with the recurrence a bit, I came to the conclusion that $a_n=c$ if $n=2^j-1$ for some nonnegative integer $j,$ and that for all other $n,$ $a_n=0.$ Standard induction made it easy to prove the former, but not the latter. For that, I used forward-backward induction.

Since $a_{2n}=0$ for all positive $n,$ then readily, $a_n=0$ whenever $n$ is a positive even integer, and in particular when $n=2^j$ for some positive integer $j.$ To prove it for the rest, I proceeded as follows.

Given a positive integer $k$ such that, for all integers $m$ with $2^k\le m\le 2^{k+1}-2,$ we have $a_m=0.$ (This clearly holds for $k=1.$) Take any odd integer $m$ such that $2^{k+1}\le m\le 2^{k+2}-2.$ Since $m$ is odd, then in fact, $2^{k+1}+1\le m\le 2^{k+2}-3,$ and letting $m=2j+1,$ we have $$2^{k+1}+1\le 2j+1\le 2^{k+2}-3$$ $$2^{k+1}\le 2j\le 2^{k+2}-4$$ $$2^k\le j\le 2^{k+1}-2$$ Thus, $a_j=0$ by inductive hypothesis, so $a_m=a_{2j+1}=a_j=0.$

Consequently, I concluded that $$f(z)=c\sum_{j=0}^\infty z^{2^j-1}.$$