# Forward-backward induction

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?

• This question has been posted on Math Overflow. Cauchy induction is another name for FB induction. – coDE_RP Jan 20 at 16:57
• @coDE_RP Wow, well some of those answers are quite interesting! Thank you – Cardioid_Ass_22 Jan 20 at 17:31

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}.$$