For every n ∈ N, prove that $(1 − 1/2 )(1 − 1/2^2 ). . .(1 − 1/2^n ) ≥ 1/4 + 1/2^{n+1}$ through induction.

Question

this is a homework question for my university math proofs. I've spent over an hour and cannot figure it out. For this induction proof I understand the base case but can't seem to solve the inductive step.

Base case: $n = 1$

$(1 − 1/2 )≥ 1/4 + 1/2^{1+1}.\;$ Thus, the base case is true ($1/2 = 1/2$)

Inductive case: $P(n) \Rightarrow P(n+1)$ Direct proof: Assume $P(n)$, show $P(n+1)$.

Suppose $P(n): (1 − 1/2 )(1 − 1/2^2 ). . .(1 − 1/2^n ) ≥ 1/4 + 1/2^{n+1}$.

If I multiply both sides by $(1 − 1/2^{(n+1)+1})$, the new LHS of $P(n)$ will be equal to $P(n+1)$, and I can try to show that the new RHS of $P(n)$ is equivalent to the RHS of $P(n+1)$.

New RHS of P(n): $(1/4 + 1/2^{n+1})*(1 − 1/2^{(n+1)+1})$

Now when I expand this out I can't seem to show that it is equivalent to what the RHS of $P(n+1)$ was.

Is my approach correct?

Thanks, John

Answer 1

The error in your approach is easily corrected: For the LHS to go from

$$(1-1/2)(1-1/2^2)\cdots(1-1/2^n)$$

to

$$(1-1/2)(1-1/2^2)\cdots(1-1/2^{n+1})$$

you want to multiply by $(1-1/2^{n+1})$, not $(1-1/2^{(n+1)+1})$. From there it's fairly straightforward to show that

$$\begin{align} \left({1\over4}+{1\over2^{n+1}}\right)\left(1-{1\over2^{n+1}}\right) &={1\over4}+{1\over2^{n+1}}\left(1-{1\over4}-{1\over2^{n+1}}\right)\\ &\ge{1\over4}+{1\over2^{n+1}}\cdot{1\over2}\quad\text{if }n\ge1\\ &={1\over4}+{1\over2^{(n+1)+1}} \end{align}$$

(Thanks to user StAKmod for pointing out an error in my first attempt at fair straightforwardness.)

Answer 2

your thought was right,except for trying to prove them equal,what we usually do here is to prove $\geqslant$. So $$\prod_{i=0}^n (1-{1\over 2^i})*(1-{1\over 2^{n+1}})\geqslant(1-{1\over 2^{n+1}})*({1\over 4}+{1\over 2^{n+1}})$$ simplify and get${1\over 4}+{1\over 2^{n+2}}+({1\over 2^{n+2}}-{1\over 2^{n+3}}-{1\over 2^{2n+2}})$

What is left is to prove the part in the bracket is $\geqslant0$. Which is simple,for${1\over 2^{n+2}}-{1\over 2^{n+3}}-{1\over 2^{2n+2}}={1\over 2^{n+3}}-{1\over 2^{2n+2}}$ and the fact $n\geqslant1$