# "Stronger" Induction

## Prove that for all positive integer $n$ $$

$\left(1+\frac{1}{2}\right)\left(1+\frac{1}{2^2}\right) \cdots \left(1+\frac{1}{2^n}\right) < \frac{5}{2}.$

Notice that the LHS of the above inequality increases as $n$ increases but the RHS remains constant. So induction doesn't immediately work here. To prove this inequality, we make a minor change on the expression as follows:

$\left(1+\frac{1}{2}\right)\left(1+\frac{1}{2^2}\right) \cdots \left(1+\frac{1}{2^n}\right) < \frac{5}{2}- \frac{m}{2^n}.$

The goal is to determine a positive constant $m$ that will allow us to prove the inequality by induction. If this inequality is true, we can conclude that the original inequality is also true!

First, let's determine what $m$ should be. The induction step is:

$\left(1+\frac{1}{2}\right)\left(1+\frac{1}{2^2}\right) \cdots \left(1+\frac{1}{2^{k+1} }\right) < \frac{ 5}{2} - \frac{ m}{ 2^{k+1} }.$

Applying the induction hypothesis, we obtain

$\left(1+\frac{1}{2}\right)\left(1+\frac{1}{2^2}\right) \cdots \left(1+\frac{1}{2^{k+1} }\right) < \left ( \frac{ 5}{2} - \frac{ m}{ 2^{k} } \right) \times \left( 1 + \frac{1}{ 2^{k+1 } } \right) < \frac{ 5}{2} - \frac{ m}{ 2^{k+1} }.$

Expanding and simplifying, we need that

$\frac{ 5 }{ 2^{k+2 } } < \frac{ 2m } { 2^{k+2} } + \frac{m} {2^{2k+1 } }.$

Now, this is clearly satisfied for $m = 3$.

It now remains to find a base case to make the strengthened statement true. For $n = 3$, we obtain

$\left(1+\frac{1}{2}\right)\left(1+\frac{1}{2^2}\right)\left(1+\frac{1}{2^3}\right) = \frac{135}{64} < \frac{136}{64} = \frac{5}{2} - \frac{3} { 2^3 }.$

Thus, we will begin our induction on the strengthened statement and a base case of $n = 3$. We will deal with $n = 1, 2$ separately, since they do not satisfy the strengthened statement.

Comments:

We didn't need to focus on a constant $m$. We could make it a function $m(n)$ and attempted to find a better shape. Of course, this additional specification leads to more complication, and it could no longer be so easy to find a suitable function.

In such problems where we "over-compensate," the strengthened induction hypothesis might not be true for some initial cases. We simply treat them as part of our base cases.

**Cite as:**"Stronger" Induction.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/stronger-induction/