0

My question concerns the inductive step of the proof below. I've typed out the work I've done so far. If anyone has any suggestions on how to proceed thanks in advance.

If $n\in\mathbb{N}$, then $(1-\frac{1}{2})(1-\frac{1}{4})(1-\frac{1}{8})(1-\frac{1}{16})\cdots(1-\frac{1}{2^n})\ge\frac{1}{4}+\frac{1}{2^{n+1}}$.

$Proof.$ We use mathematical induction.

Base Case. For $n=1$ we see that $1-\frac{1}{2}\ge\frac{1}{4}+\frac{1}{4}$ since $\frac{1}{2}\ge\frac{1}{2}$.

Inductive Step. Let $n>1$. Assume our statement is true for $n$. Now observe that

$\begin{align}(1-\frac{1}{2})(1-\frac{1}{4})(1-\frac{1}{8})(1-\frac{1}{16})\cdots(1-\frac{1}{2^{n+1}})&\ge\\ \left((1-\frac{1}{2})(1-\frac{1}{4})(1-\frac{1}{8})(1-\frac{1}{16})\cdots(1-\frac{1}{2^{n}})\right)(1-\frac{1}{2^{n+1}})&\ge(\frac{1}{4}+\frac{1}{2^{n+1}})(1-\frac{1}{2^{n+1}}) \end{align}$

My question is: How do we get from $\begin{align} (\frac{1}{4}+\frac{1}{2^{n+1}})(1-\frac{1}{2^{n+1}}) \end{align}$ to $\frac{1}{4}+\frac{1}{2^{(n+1)+1}}$?

Most of what I've attempted has led to tedious calculations that do not simplify to the desired result. I've also tried making the argument that $(1-\frac{1}{2^{n+1}})$ must be $\ge$ to $\frac{1}{2}$ but then I'm stuck with $\frac{1}{8}+\frac{1}{2^{(n+1)+1}}$... Is my approach incorrect here?

ClownInTheMoon
  • 1,987
  • In your inductive step, why do you have a hypothesis of equality, where inequality should be? This may also explain your main difficulty - you do not have to prove equality, only inequality. – Andris Birkmanis Sep 16 '16 at 16:04
  • @AndrisBirkmanis Sorry about that. Fixed it. – ClownInTheMoon Sep 16 '16 at 16:13
  • you are almost there. Show that $(\frac{1}{4}+\frac{1}{2^{n+1}})(1-\frac{1}{2^{n+1}}) >\frac{1}{4}+\frac{1}{2^{n+2}}$ and you are done. Multiply it out. The algebra is not so tough. – user317176 Sep 16 '16 at 16:18

2 Answers2

1

Note that you have to show that $$(\frac{1}{4}+\frac{1}{2^{n+1}})(1-\frac{1}{2^{n+1}})\geq \frac{1}{4}+\frac{1}{2^{(n+1)+1}}$$ which is $$\frac{1}{4}+\frac{1}{2^{n+1}}-\frac{1}{2^{n+3}}-\frac{1}{2^{2n+2}}\geq \frac{1}{4}+\frac{1}{2^{n+2}}$$ or $$\frac{1}{2^{n+1}}-\frac{1}{2^{n+3}}-\frac{1}{2^{2n+2}}\geq \frac{1}{2^{n+2}}.$$ Now multiply both sides by $2^{n+3}$, $$4-1-\frac{1}{2^{n+1}}\geq 2$$ or $$ 1\geq \frac{1}{2^{n+1}}$$ which holds.

Robert Z
  • 145,942
1

My question is: How do we get from $\begin{align} (\frac{1}{4}+\frac{1}{2^{n+1}})(1-\frac{1}{2^{n+1}}) \end{align}$ to $\frac{1}{4}+\frac{1}{2^{(n+1)+1}}$?

Note that we have to show that $$\left(\frac{1}{4}+\frac{1}{2^{n+1}}\right)\left(1-\frac{1}{2^{n+1}}\right)\color{red}{\ge}\frac 14+\frac{1}{2^{n+2}}$$

One has $$\begin{align}\left(\frac{1}{4}+\frac{1}{2^{n+1}}\right)\left(1-\frac{1}{2^{n+1}}\right)&= \frac 14-\frac{1}{2^{n+3}}+\frac{1}{2^{n+1}}-\frac{1}{2^{2n+2}}\\&= \frac 14+\frac{-2^{n-1}+2^{n+1}-1}{2^{2n+2}}\\&=\frac 14+\frac{3\cdot 2^{n-1}-1}{2^{2n+2}}\\&= \frac 14+\frac{2^n+(2^{n-1}-1)}{2^{2n+2}}\\&\color{red}{\ge}\frac 14+\frac{2^n+0}{2^{2n+2}}\\&=\frac 14+\frac{1}{2^{n+2}}\end{align}$$

mathlove
  • 139,939