prove by induction $\sqrt{1 \sqrt{2 \sqrt{3.....\sqrt n }}} < 2$

Question

My attempt:

let $$p(n-1) = \sqrt{1 \sqrt{2 \sqrt{3.....\sqrt{n-1} }}}$$

now let us assume that $p(n-1)$ is less than 2

for $n = 1$(base case) $ \sqrt 1 = 1 < 2$

now $$\frac{p(n)}{p(n-1)} = \frac{\sqrt{1 \sqrt{2 \sqrt{3.....\sqrt{n}}}}}{ \sqrt{1 \sqrt{2 \sqrt{3.....\sqrt{n-1} }}})} = n^{(1/2^n)}$$

now

$$\sqrt{1 \sqrt{2 \sqrt{3.....\sqrt n }}} < \sqrt{1 \sqrt{2 \sqrt{3.....\sqrt{n-1} }}} \cdot n^{(1/2^n)} $$

as $p(n-1)$ is less than 2 so we can write

$$\sqrt{1 \sqrt{2 \sqrt{3.....\sqrt n }}} < 2n^{(1/2^n)} $$

as n tends to infinity $2n^{(1/2^n)}$ converges to 2 so by taking limits on both sides we have

$$\lim_{{n \to \infty}} \sqrt{1 \sqrt{2 \sqrt{3.....\sqrt n }}} < 2$$

now $\frac{p(n)}{p(n-1)}$ equals $n^{(1/2^n)}$ which is always greater than 1 this means that $p(n)$ is strictly increasing. So if p(n) is increasing and $\lim_{{n \to \infty}} p(n) $ < 2 then this means that p(n) is always lesser than 2 for all n.

This was my argument, but I wasn't given credit for this solution. So is there anything wrong with my solution.

Answer 1

Your mistake is in going from

$$ p(n) = \sqrt{1 \sqrt{2 \sqrt{3.....\sqrt n }}} < 2n^{(1/2^n)} $$

to

$$ \lim_{n \to \infty} p(n) = \lim_{n \to \infty} \sqrt{1 \sqrt{2 \sqrt{3.....\sqrt n }}} < \lim_{n \to \infty} 2n^{(1/2^n)} $$

Remember the context: you were assuming for now that $p(n-1) < 2$. So you have correctly proved that

$$ p(n-1) < 2 \implies p(n) < 2n^{(1/2^n)} $$

But this doesn't tell us for example that $p(n+1) < 2(n+1)^{(1/2^{n+1})}$. Assuming that $p(n-1)<2$ can only tell us that $p(n+1) < 2n^{(1/2^n)}(n+1)^{(1/2^{n+1})}$.

To make the limit comparison valid, you would need to know that $p(n) < 2n^{(1/2^n)}$ for every $n$ (or for every $n>N$).

This proof approach is not easy to fix. Maybe it would work to inductively show $p(n) < q(n)$ for some formula $q$ where it's more obvious $q(n)<2$ for every $n$.

Answer 2

In the induction step you show $p(n) < 2*2^{1 \over 2^n}$. Then you insert $p(n) < 2$ into the next step when you are have that $p(n+1) < 2*2^{1 \over 2^{n+1}}$. This is not a valid argument since you are inserting a better statement than what you have shown.

Answer 3

Passing to log we have to show that $$ S=\sum_{n=2}^{\infty}\frac{\log n}{2^{n}}<\log 2. \ \ $$ The trick is to use the majorization for $n\geq 2$ $$\log n\leq \frac{n}{2}+\log 2 -1$$ leading to $S<\frac{1}{4}+\frac{1}{2}\log 2.$ You have to use $\sum_{n=0}^{\infty}z^n=\frac{1}{1-z}$ and $\sum_{n=1}^{\infty}nz^{n-1}=\frac{1}{(1-z)^2}$ applied to $z=1/2.$

Answer 4

First Version: You said you need to use induction. So assume that $$S_n=\sum_{k=2}^n \frac{\log k}{2^k} < \log 2 - \frac cn$$ for some $n$ and $c$. Going to $n+1$ $$S_{n+1} < \log 2 - \frac cn + \frac{\log(n+1)}{2^{n+1}} \stackrel{!}{\leq} \log 2 - \frac{c}{n+1}$$ and so $c$ must satisfy $$f(n)=\frac{n(n+1)\log(n+1)}{2^{n+1}} \leq c \, .$$ We have $f(3)=\frac{3\log 2}{2}>f(4)=\frac{5\log5}{8}$ and $$f'(n)=\frac{\left(-(n^2+n)\log2+2n+1\right)\log(n+1)+n}{2^{n+1}} \\ \leq -\frac{\log(n+1)}{2^{n+1}} \, \left[(n^2+n)\log2-3n-1\right] \\ =-\frac{\log(n+1)\log2}{2^{n+1}}\left[\left(n-\frac{3/\log2-1}{2}\right)^2-\left(\frac{3/\log2-1}{2}\right)^2-\frac{1}{\log2}\right] \, .$$ Now if $n\geq \frac{3/\log2-1}{2}$, the square bracket is an increasing function in $n$ and for $n=4>\frac{3/\log2-1}{2}$ we have $$f'(4)=-\frac{\log5}{32}\left[20\log2-13\right]<0 \, ,$$ thus $f'(n)<0$ for all $n\geq 4$, which in turn implies $f(3)>f(4)>f(5)>...$.

We can therefore choose $c=f(3)=\frac{3\log2}{2}$ and our induction step is fulfilled for every $n\geq 3$. It remains to check the induction start, that is $n=3$, $$\frac{\log2}{4}+\frac{\log3}{8} < \frac{\log2}{4} + \frac{\log4}{8} = \frac{\log2}{2} = \log 2 - \frac{\frac{3\log2}{2}}{3} \, .$$

The case $n=2$ can be checked separately i.e. $\log2/4 < \log2$, which is clearly true.

---

Second Version: I just realized it is probably much easier to make the ansatz $$S_n < \log2 - \frac{cn}{2^n}$$ which gives rise to the induction step $$S_{n+1} = S_n + \frac{\log(n+1)}{2^{n+1}} < \log 2 - \frac{cn}{2^n} + \frac{\log(n+1)}{2^{n+1}} \stackrel{!}{\leq} \log 2 - \frac{c(n+1)}{2^{n+1}}$$ i.e. the condition $$c \geq \frac{\log(n+1)}{n-1}=f(n)$$ which is true for every $n\geq 3$, since $$f'(n)=\frac{-(n+1)\log(n+1)+n-1}{(n+1)(n-1)^2} < \frac{-(n+1)\log(e)+n-1}{(n+1)(n-1)^2} = -\frac{2}{(n+1)(n-1)^2} < 0$$ for every $n\geq 2$ and if $c=f(3)=\log 2$ (which is the maximal value for all $n\geq 3$, while the induction start for $n=2$ wouldn't work). The induction start is then again $n=3$ i.e. $$\log 2 - \frac{3\log 2}{8} > \log 2 - \frac{4\log 2}{8} = \frac{\log 2}{2} = \frac{\log 2}{4} + \frac{\log 4}{8} > \frac{\log 2}{4} + \frac{\log 3}{8} = S_3 \, .$$