Intereting Posts

How often is a sum of $k$ consecutive primes also prime?
What's the best way to measure mathematical ability?
If 4n+1 and 3n+1 are both perfect sqares, then 56|n. How can I prove this?
Inversion of Trigonometric Equations
Lebesgue inner measure formula
Fourier transform for dummies
Why does taking completions make number fields simpler?
Evaluation of the integral $\int_0^1 \log{\Gamma(x+1)}\mathrm dx$
Solvability of a group with order $p^n$
$I-AB$ be invertible $\Leftrightarrow$ $I-BA$ is invertible
Show that $2 < e^{1/(n+1)} + e^{-1/n}$
Why does $\sum_{n = 0}^\infty \frac{n}{2^n}$ converge to 2?
Probability of getting two pair in poker
Ring Inside an Algebraic Field Extension
$ax+by+cz=d$ is the equation of a plane in space. Show that $d'$ is the distance from the plane to the origin.

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.

- the concept of Mathematical Induction
- The asymptotic behaviour of $\sum_{k=1}^{n} k \log k$.
- Well-Ordering and Mathematical Induction
- Need a counter example for cycle in a graph
- Good examples of double induction
- Mathematical explanation for the Repertoire Method
- Prove that there exists bipartite graph with this degree sequence: $(3,3,3,3,3,5,6,6,6,6,6,6,6,6)$
- $k$-element subsets of $$ that do not contain $2$ consecutive integers
- What is the next prime number?
- Equivalence Relations On a Set of All Functions From $\mathbb{Z} to $\mathbb{Z}$

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.

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.

- $A,B,C \in M_{n} (\mathbb C)$ and $g(X)\in \mathbb C$ such that $AC=CB$- prove that $A^jC=CB^j$ and $g(A)C=Cg(B)$
- Calculating the Zeroes of the Riemann-Zeta function
- Geometric interpretation of the determinant of a complex matrix
- Any $p + 1$ consecutive integers contain at least two invertible elements modulo $p!!$ if $p$ is odd
- Clarkson's Proof of the Divergence of Reciprocal of Primes
- How do you prove that $n^n$ is $O(n!^2)$?
- Show that the set of zeros of $f$ is discrete
- Evalute $ \lim_{n\rightarrow \infty}\sum^{n}_{k=0}\frac{\binom{n}{k}}{n^k(k+3)} $
- Some exact sequence of ideals and quotients
- How to start a math blog?
- Finding Inverse Laplace Transform
- Topology – Quotient Space and Homeomorphism
- Eigenvalues of product of two hermitian matrices
- For $f$ continuous, show $\lim_{n\to\infty} n\int_0^1 f(x)x^n\,dx = f(1).$
- Is a matrix $A$ with an eigenvalue of $0$ invertible?