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

(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):

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

Taking common denominator on LHS resulting in:

(2k+1 - 1)/2k+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.

• I did not follow the steps after "Subtracting $1/4 + 2^{-(k+1)}$ on the RHS as it's an inequality", mind clarifying? Sep 30 '18 at 20:25
• Sorry, hopefully it's not an error but I reasoned as follows: since RHS is ≥ LHS, subtracting from the LHS doesn't violate the equality being true. For eg, if x <= y and b is a positive integer, then x <= y + b is still true.
– tkon
Sep 30 '18 at 20:38
• Then the next step the LHS somehow becomes $1 - 2^{-(k+1)}$, is that a typo? Also on that line the LHS is positive and the RHS is negative, which is not wrong but is not very useful. Sep 30 '18 at 20:48

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