17
$\begingroup$

Problem: prove $\sqrt{2\sqrt{3\sqrt{\cdots\sqrt{n}}}}<3$ by induction. I tried some, but stopped in $\sqrt[2^n]{n+1}$. Also tried with $2\sqrt{3\cdots}<3^2$ and so on.

$\endgroup$
  • 2
    $\begingroup$ Is this a homework problem? $\endgroup$ – user84413 Aug 21 '13 at 18:04
  • $\begingroup$ No, is not homework. Im writing notes and can't solve this one. $\endgroup$ – Norza Aug 21 '13 at 18:10
18
$\begingroup$

This is actually a 'standard' induction question, whose goal is to make you think about the induction hypothesis.

This is tricky because the induction is not obvious. You likely have tried applying it directly, but since

$$ \sqrt{ 2 \sqrt{3 \sqrt{\ldots \sqrt{n} } } } < \sqrt{ 2 \sqrt{3 \sqrt{\ldots \sqrt{n \sqrt{n+1}} } } }, $$

the proof fails (as seen by all the other deleted solutions).

However, this is the statement that you should induct on:

Fix $n\geq 2$. For all values of $2\leq k \leq n$, $\sqrt{ k \sqrt{(k+1) \sqrt{\ldots \sqrt{n} } } } < k+1 $

Perform the 'induction' on k, going from $k$ to $k-1$ (as opposed to the typical induction on $n$ going from $n$ to $n+1$).

Specifically, the base case is when $k=n$. This is immediately obvious.

For the induction step, assume it is true for some $k$. Consider $k-1$. This induction is then immediately obvious since $(k-1)(k+1) < k^2$.

Of course, we now get a lot of other similar, interesting inequalities for free.

Moral: Choosing the correct induction hypothesis is extremely important.


Note: I personally call this method Stronger Induction (not a standard term in the literature). It cleverly choses the induction hypothesis based on observations, and includes strengthing (and modifying) the induction hypothesis like what Andre did. You can click on the link for a writeup that I did.

$\endgroup$
  • $\begingroup$ Very interesting answer. Will be very useful. $\endgroup$ – Norza Aug 22 '13 at 19:04
15
$\begingroup$

We want control over the size of $$a_n=2^{1/2}3^{1/4}4^{1/8}\cdots n^{1/2^{n-1}}.$$ It is convenient to take the logarithm, and show that $\log a_n\lt \log 3$. But one could also work directly with the product.

As is essentially necessary with induction proofs of inequalities, we prove the stronger result $$\log a_n=\frac{1}{2}\log 2+\frac{1}{4}\log 3 +\frac{1}{8}\log 4+\cdots +\frac{1}{2^{n-1}}\log n \lt \log 3 -\frac{1}{2^{n-2}}\log n.\tag{1}$$

The case $n=2$ is no problem, it comes down to the fact that $\frac{3}{2}\log 2\lt \log 3$. The inequality does hold, though not by much.

For the induction step, suppose we know that (1) holds for a particular $n$. It will then be enough to show that $$\log 3 -\frac{1}{2^{n-2}}\log n+\frac{1}{2^n}\log(n+1)\lt \log 3 -\frac{1}{2^{n-1}}\log (n+1).$$ Some manipulation makes this inequality obvious.

$\endgroup$
  • $\begingroup$ What it the $\frac{1}{5} \log(5) $ term doing in there? Otherwise nice solution, thank you! $\endgroup$ – Brusko651 Aug 21 '13 at 18:09
  • $\begingroup$ Thanks for spotting the typo. Thought this was short enough to be possibly typo-free. $\endgroup$ – André Nicolas Aug 21 '13 at 18:13
  • 3
    $\begingroup$ How did you choose which stronger inequality to prove? $\endgroup$ – Potato Aug 21 '13 at 19:17
  • 2
    $\begingroup$ Confession time, I first tried $\lt \log 3- \frac{1}{2^{n-1}}\log n$, it didn't quite work, needed to go a bit below. Thought, OK, let's go a lot below, the only trouble would be that the induction doesn't start. But it did, barely. $\endgroup$ – André Nicolas Aug 21 '13 at 19:26

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.