Proving a bounded square root.

Question

How would I be able to prove $$\sqrt{k\sqrt{k+1{...\sqrt{n}}}}<k+1,$$ originally the problem was to prove $$\sqrt{2\sqrt{3...\sqrt{n}}}<3,$$ and it told us to prove the statement above for $2\leq k\leq n$.

Answer 1

If $\Pr(X=i)=\frac{1}{2^{i+1}}$ for $i=0,1,\ldots,$ then $\mathbb{E}(s^X)=\frac{1}{2-s}$ which implies by derivation that $\mathbb{E}(X)=1.$ Let $k>0$. Since $x\mapsto \log (k+x)$ is concave the Jensen inequality (*) says $$\log(k+1)=\log (k+\mathbb{E}(X))\stackrel{(*)}{\geq}\mathbb{E}(\log (k+X))=\sum_{i=0}^{\infty}\frac{1}{2^{i+1}}\log (k+i)\geq \sum_{i=0}^{n}\frac{1}{2^{i+1}}\log (k+i)$$ which is the desired result.