Forwards-Backwards Proof By Induction

 

You are first introduced to proof by induction in the first year of A-level further mathematics.

A statement such as: “\displaystyle 2^{n} +3 is a prime number, where \displaystyle n is a natural number” may be true for some values of \displaystyle n and false for others.

You can prove a statement \displaystyle S( n) is true for all natural numbers \displaystyle n, by showing \displaystyle S( n) satisfies two conditions:

  • \displaystyle S( n) is true when \displaystyle n=1
  • Under the assumption \displaystyle S( n) is true when \displaystyle n=k, it follows that \displaystyle S( n)} is true when \displaystyle n=k+1.

 

From these two conditions it follows that \displaystyle S( n) is true for all \displaystyle n:n\in \mathbb{N}.

Most problems encountered at A-level can be dealt with relatively easily.  However, proof by induction problems do exist where the above two conditions are quite difficult to prove and require a lot of work, unless you’ve encountered the problem before.

You’ll now learn a variant of proof by induction which can simplify the work considerably.

We will prove a statement \displaystyle S( n) is true for all natural numbers \displaystyle n, by showing \displaystyle S( n) satisfies three conditions:

  • \displaystyle S( n) is true when \displaystyle n=1
  • Under the assumption \displaystyle S( n) is true when \displaystyle n=k, it follows that \displaystyle S( n)} is true when \displaystyle n=2k.
  • Under the assumption \displaystyle S( n) is true when \displaystyle n=k, it follows that \displaystyle S( n)} is true when \displaystyle n=k-1.

 

This is sometimes called forwards-backwards induction.  Think carefully why these three conditions prove \displaystyle S( n) for all natural numbers.  The second condition proves it for larger and larger ‘doubled values’, and the third condition ‘fills in’ all the gaps we left behind, thus hitting all the numbers.

 

Consider the well know arithmetic-geometric mean inequality:

(1)   \begin{equation*} {\displaystyle \frac{{\textstyle \sum\limits _{{\textstyle i=1}}^{n} a}{\displaystyle _{i}}}{n} \ \geq }{\textstyle \ \sqrt[n]{\prod\limits _{i=1}^{n}} a_{i}} \end{equation*}

where \displaystyle a_{i} \in \mathbb{R}_{+}

 

We want to show that this is true for all \displaystyle n:n\in \mathbb{N}.

For \displaystyle n=1, we have \displaystyle a_{i} \geq a_{i}.  So the first condition is met.

Next, assume true for \displaystyle n=k,

    \begin{equation*} {\displaystyle \frac{{\textstyle \sum\limits _{{\textstyle i=1}}^{k} a}{\displaystyle _{i}}}{k} \ \geq }{\textstyle \ \sqrt[k]{\prod\limits _{i=1}^{k}} a_{i}} \end{equation*}

    \begin{equation*} \end{equation*}

Under this assumption, show that it is true for \displaystyle n=2k,

    \begin{align*} \frac{a_{1} +a_{2} +...+a_{2k}}{2k} & =\frac{\frac{a_{1} +a_{2} +...+a_{k}}{k} +\frac{a_{k+1} +a_{k+2} +...+a_{2k}}{k}}{2}\\ & \\ & \geq \frac{\sqrt[k]{a_{1} a_{2} ...a_{k}} \ +\ \sqrt[k]{a_{k+1} a_{k+2} ...a_{2k}}}{2}\\ & \\ & \geq \sqrt{\sqrt[k]{a_{1} a_{2} ...a_{k}} \ \sqrt[k]{a_{k+1} a_{k+2} ...a_{2k}}}\\ & \\ & =\sqrt[2k]{a_{1} a_{2} ...a_{2k}} \end{align*}

Hence, if true for \displaystyle n=k, it follows that it is true for \displaystyle n=2k.

Now under the same assumption, show it is true for \displaystyle n=k-1,

For \displaystyle n=k,

(2)   \begin{equation*} \frac{a_{1} +a_{2} +...+a_{k}}{k} \ \geq \ ( a_{1} a_{2} ...a_{k})^{\tfrac{1}{k}} \end{equation*}

We are also free to choose any \displaystyle a_{k} we wish,

Choose \displaystyle a_{k} = \displaystyle \frac{a_{1} +a_{2} +...+a_{k-1}}{k-1}

Substituting into \displaystyle ( 2),

    \begin{align*} \frac{a_{1} +a_{2} +...+\frac{a_{1} +a_{2} +...+a_{k-1}}{k-1}}{k} & \ \geq \ \left( a_{1} a_{2} ...a_{k-1}\frac{a_{1} +a_{2} +...+a_{k-1}}{k-1}\right)^{\cfrac{1}{k}}\\ & \\ \Longrightarrow \ \ \ \ \ \ \ \ \ \ \ \frac{a_{1} +a_{2} +...+a_{k-1}}{k-1} & \ \geq \ \left( a_{1} a_{2} ...a_{k-1}\frac{a_{1} +a_{2} +...+a_{k-1}}{k-1}\right)^{\cfrac{1}{k}}\\ & \\ \Longrightarrow \ \ \ \ \ \ \left(\frac{a_{1} +a_{2} +...+a_{k-1}}{k-1}\right)^{k} & \ \geq \ a_{1} a_{2} ...a_{k-1}\frac{a_{1} +a_{2} +...+a_{k-1}}{k-1}\\ & \\ \Longrightarrow \ \ \ \left(\frac{a_{1} +a_{2} +...+a_{k-1}}{k-1}\right)^{k-1} & \ \geq \ a_{1} a_{2} ...a_{k-1}\\ & \\ \Longrightarrow \ \ \ \ \ \ \ \ \ \ \ \frac{a_{1} +a_{2} +...+a_{k-1}}{k-1} & \ \geq \ \sqrt[k-1]{a_{1} a_{2} ...a_{k-1}}\\ & \end{align*}

Hence, if true for \displaystyle n=k, it is also true for \displaystyle n=k-1.

Since we have proved all three conditions, it follows that the statement is true for all \displaystyle n:n\in \mathbb{N}. \displaystyle \qed

Note: If you are worried about the step where we choose a particular value of \displaystyle a_{k}, that loss of generality doesn’t matter, since we have effectively ‘thrown away’ \displaystyle a_{k} in the final statement.

If you are feeling brave, try and redo this proof using standard induction.