Forward-Backward Induction

Forward-Backward Induction is a variant of mathematical induction. It has a very distinctive inductive step, and though it is rarely used, it is a perfect illustration of how flexible induction can be. It is also known as Cauchy Induction, which is a reference to Augustin Louis Cauchy who used it prove the arithmetic-mean-geometric-mean inequality.

Without further ado, we present to you forward-backward induction!

Forward-backward induction

• Step \(1\): [The base case] We start by showing that our statement is true for an integer \(n_0\). This isn't any different from standard induction.

• Step \(2\): [The inductive step] This is made out of two parts.

  • \(P(k)\Rightarrow P(2k)\): This is our "forward" part. This is where you show that if the statement is true for some integer \(k\), it is also true for \(2k.\)

  • \(P(k)\Rightarrow P(k-1)\): This is our "backward" part. Here you show that if the statement is true for some integer \(k\), then it is also true for \(k-1.\)

Completing steps \(1\) and \(2\) proves that the statement is true for all positive integers \(n\).

Take some time to think about why this argument works. The first part of the inductive step shows that the statement is true for larger and larger values of \(n\). But that leaves a lot of gaps in between. The second part ensures that all the gaps are taken care of.

Another way of viewing it is through the domino analogy. (Dominoes are a great way to think about induction!). Say, you have infinitely many dominoes arranged in a line. You have proved a very interesting property about these dominoes. If you knock over the \(k\)-th domino, for some strange reason, all the \(2^n\cdot k^{\text{th}}\) dominoes get knocked over. After you observe the dominoes for a little while longer, you prove that the dominoes are arranged in such a way that if one of them falls down, the one preceding it falls down as well. Now if you were to knock down the first domino, all of the dominoes (despite all their weirdness!) would eventually fall.

Convince yourself that the method of forward-backward induction does indeed work. Then continue reading.

We're going to see forward-backward induction in action through Cauchy's proof of the AM-GM inequality. AM-GM inequality states that the arithmetic mean of a bunch of non-negative reals cannot be less than their geometric mean.

In other words, for \(a_i \in \mathbb{R}_{+}\)

\[ \frac{\displaystyle\sum_{i=1}^n a_i}{n}\geq \sqrt[n]{\displaystyle\prod_{i=1}^n a_i}.\]

Let's begin!

The AM-GM Inequality:

Our base case is \(n=2\) (since \(n=1\) is trivial).

We have to show that for non-negative reals \(a_1\) and \(a_2\), \(\frac{a_1+a_2}{2}\geq \sqrt{a_1a_2}\). This is not hard to do. Start from \((\sqrt{a_1}-\sqrt{a_2})^2\geq 0\). The result immediately follows.

For our induction hypothesis, we assume that the inequality holds for some integer \(k\). In other words, we have

\[\frac{\displaystyle\sum_{i=1}^k a_i}{k}\geq \sqrt[k]{\displaystyle\prod_{i=1}^k a_i}.\]

Now we show that the inequality holds for \(2k\):

\[\begin{align} \dfrac{a_1+a_2+\cdots+a_{2k}}{2k} &=\dfrac{\dfrac{a_1+a_2+\cdots+a_k}{k}+\dfrac{a_{k+1}+a_{k+2}+\cdots+a_{2k}}{k}}{2}\\ &\geq \dfrac{\sqrt[k]{a_1a_2\cdots a_k}+\sqrt[k]{a_{k+1}a_{k+2}\cdots a_{2k}}}{2}\\ &\geq\sqrt{\sqrt[k]{a_1a_2\cdots a_k}\sqrt[k]{a_{k+1}a_{k+2}\cdots a_{2k}}}\\ &=\sqrt[2k]{a_1a_2\cdots a_{2k}}. \end{align}\]

The first inequality follows from \(k\)-variable AM-GM, which is true because of our inductive hypothesis, and the second inequality follows from the \(2\)-variable AM-GM, which we just proved above.

The first part is done. Now we show that the inequality holds for \(k-1\) variables.

Since the AM-GM inequality is true for any \(k\) positive reals, it is specifically true when \(a_k=\dfrac{a_1+a_2+\cdots+a_{k-1}}{k-1}\).

We have

\[\begin{align} \frac{a_1+a_2+\cdots+a_k}{k} &\geq\sqrt[k]{a_1a_2\cdots a_k}\\ \frac{a_1+a_2+\cdots+a_{k-1}+\frac{a_1+a_2+\cdots+a_{k-1}}{k-1}}{k} &\geq \sqrt[k]{a_1a_2\cdots a_{k-1}\cdot \frac{a_1+a_2+\cdots+a_{k-1}}{k-1}}\\ \frac{a_1+a_2+\cdots+a_{k-1}}{k-1} &\geq\sqrt[k]{a_1a_2\cdots a_{k-1}\cdot \frac{a_1+a_2+\cdots+a_{k-1}}{k-1}}\\ \left(\frac{a_1+a_2+\cdots+a_{k-1}}{k-1}\right)^k &\geq a_1a_2\cdots a_{k-1}\cdot \frac{a_1+a_2+\cdots+a_{k-1}}{k-1}\\ \left(\frac{a_1+a_2+\cdots+a_{k-1}}{k-1}\right)^{k-1} &\ge a_1a_2\cdots a_{k-1}\\ \frac{a_1+a_2+\cdots+a_{k-1}}{k-1} &\ge\sqrt[k-1]{a_1a_2\cdots a_{k-1}}. \end{align}\]

This proves that the AM-GM inequality for \(k-1\) variables.

We've shown the base case and the inductive hypothesis. So, by the forward-backward induction, the AM-GM inequality is true for any variable. \(_\square\)