Prove by induction that, for all positive integers n, the following inequality holds:

Question

(1-2^-1)(1-2^-2)...(1-2^-n) ≥ 1/4 + 2^-(n+1)

My solution so far:

After verifying the base case for n = 1, I began the inductive step:

(1-2^-1)(1-2^-2)...(1-2^-(k+1)) ≥ 1/4 + 2^-(k+2)

Subtracting 1/4 + 2^-(k+1) on the RHS as it's an inequality:

(1-2^-1)(1-2^-2)...(1-2^-(k+1)) ≥ 1/4 + 2^-(k+2) - (1/4 + 2^-(k+1))

1 - 2^-(k+1) ≥ 2^-(k+2) - 2^-(k+1)

Taking common denominator on RHS (skipped a few algebraic steps):

(2^k+1 - 1)/2^k+1 ≥ 1/(2^k+2) - 1/(2^k+1)

Taking common denominator on LHS resulting in:

(2^k+1 - 1)/2^k+1 ≥ - 1/(2^-(k+1))

It's my first time learning about induction so I'm wondering if the last step is sufficient for proving the proposition since the numerator on the LHS is greater than the numerator on the RHS, and they have the exact same denominator, or is this just the completely wrong approach? Any hints and/or tips would be helpful. Thanks.

Answer 1

Assume the inequality holds for some $n = k$, $k \ge 1$,

$$\left(1-2^{-1}\right)\left(1-2^{-2}\right)\cdots\left(1-2^{-k}\right) \ge \frac14 + 2^{-(k+1)}$$

For $n = k+1$,

$$\begin{align*} LHS &= \left(1-2^{-1}\right)\left(1-2^{-2}\right)\cdots\left(1-2^{-k}\right)\left(1-2^{-(k+1)}\right)\\ &\ge \left(\frac14 + 2^{-(k+1)}\right)\left(1-2^{-(k+1)}\right)\\ &= \frac14 - \frac14\cdot 2^{-(k+1)} + 2^{-(k+1)}-2^{-2(k+1)}\\ &= \frac14 + 2^{-(k+2)}\left[-\frac14\cdot2 + 2-2^{-k}\right]\\ &= \frac14 + 2^{-(k+2)}\left[\frac32-2^{-k}\right]\\ &\ge \frac14 + 2^{-(k+2)}\left[\frac32-2^{-1}\right]\\ &= \frac14 + 2^{-(k+2)}\cdot 1\\ &= RHS \end{align*}$$

Answer 2

I'd avoid starting the induction step from what you need to prove; rather $$ \left(1-\frac{1}{2}\right)\left(1-\frac{1}{2^2}\right)\dots \left(1-\frac{1}{2^k}\right)\left(1-\frac{1}{2^{k+1}}\right)\ge \left(\frac{1}{4}+\frac{1}{2^{k+1}}\right)\left(1-\frac{1}{2^{k+1}}\right) $$ by the induction hypothesis.

The right hand side can be rewritten $$ \left(\frac{1}{4}+\frac{1}{2^{k+1}}\right)\left(1-\frac{1}{2^{k+1}}\right)= \frac{1}{4}+\frac{1}{2^{k+1}}-\frac{1}{2^{k+3}}-\frac{1}{2^{2k+2}} $$ and now we can try to see whether $$ \frac{1}{4}+\frac{1}{2^{k+1}}-\frac{1}{2^{k+3}}-\frac{1}{2^{2k+2}} \ge \frac{1}{4}+\frac{1}{2^{k+2}} $$ that is, $$ \frac{1}{2^{k+1}}\ge\frac{1}{2^{k+2}}+\frac{1}{2^{k+3}}+\frac{1}{2^{2k+2}} $$ If we multiply both sides by $2^{k+1}$ we obtain the equivalent $$ 1\ge\frac{1}{2}+\frac{1}{4}+\frac{1}{2^{k+1}} $$ that is, $$ \frac{1}{4}\ge\frac{1}{2^{k+1}} $$ or $2^{k+1}\ge 4$ that's true as soon as $k\ge1$. Therefore $$ \left(1-\frac{1}{2}\right)\left(1-\frac{1}{2^2}\right)\dots \left(1-\frac{1}{2^k}\right)\left(1-\frac{1}{2^{k+1}}\right)\ge \left(\frac{1}{4}+\frac{1}{2^{k+1}}\right)\left(1-\frac{1}{2^{k+1}}\right) \ge \frac{1}{4}+\frac{1}{2^{k+2}} $$