3
$\begingroup$

(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.

$\endgroup$
3
  • $\begingroup$ I did not follow the steps after "Subtracting $1/4 + 2^{-(k+1)}$ on the RHS as it's an inequality", mind clarifying? $\endgroup$
    – peterwhy
    Sep 30 '18 at 20:25
  • $\begingroup$ 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. $\endgroup$
    – tkon
    Sep 30 '18 at 20:38
  • $\begingroup$ 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. $\endgroup$
    – peterwhy
    Sep 30 '18 at 20:48
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.