95
$\begingroup$

Prove without calculus that the sequence $$L_{n}=\sqrt[n+1] {(n+1)!} - \sqrt[n] {n!}, \space n\in \mathbb N$$ is strictly decreasing.

$\endgroup$
21
  • 6
    $\begingroup$ In other words one needs to prove that $L_n-L_{n-1}=\sqrt[n+1] {(n+1)!} - \sqrt[n] {n!}-(\sqrt[n] {(n!} - \sqrt[n-1] {(n-1)!})=\sqrt[n+1] {(n+1)!}-2\sqrt[n] {n!}+\sqrt[n-1] {(n-1)!}<0$ $\endgroup$
    – Adi Dani
    Commented Nov 15, 2012 at 22:05
  • 7
    $\begingroup$ Or you could try to prove that $\left(\sqrt[n+1] {(n+1)!} - \sqrt[n] {n!}\right) \big/ \left(\sqrt[n] {n!} - \sqrt[n-1] {(n-1)!}\right) < 1$ for all $n$. $\endgroup$ Commented Nov 16, 2012 at 1:33
  • 5
    $\begingroup$ $\sqrt[n] {n!}$ is the geometric mean of 1..n. $\endgroup$
    – Mark Hurd
    Commented Jan 23, 2013 at 16:05
  • 4
    $\begingroup$ @Jonas: Perhaps it would be beneficial to firm up what is meant by "without calculus" in the question statement. $\endgroup$
    – cardinal
    Commented Feb 3, 2013 at 20:54
  • 16
    $\begingroup$ @Jonas: For what it's worth, the sequence $L_n$ is called Lalescu's sequence and is known to converge to $1/e$. $\endgroup$ Commented Feb 6, 2013 at 20:01

2 Answers 2

43
+1000
$\begingroup$

Let $\ell_n = \left(n!\right)^{1/n}$. Clearly for all $n \in \mathbb{N}$, $\ell_n > 0$. The question is equivalent to showing that $$\frac{\ell_{n+2}}{\ell_{n+1}} + \frac{\ell_n}{\ell_{n+1}} < 2 \tag{1}$$ Let $$ x_n = \log \frac{\ell_{n+1}}{\ell_n} = \frac{1}{n+1} \left( \log(n+1) - \frac{1}{n} \sum_{k=1}^n \log(k) \right) $$ The inequality $(1)$ now reads: $$ 2 > \exp(x_{n+1}) + \exp(-x_n) = 2 \exp\left(\frac{x_{n+1}-x_n}{2}\right) \cosh \left(\frac{x_{n+1}+x_n}{2}\right) \tag{2} $$ We can rewrite $x_n$ a little: $$ x_n = \frac{1}{n+1} \left( \log\left(\frac{n+1}{n}\right) - \underbrace{\frac{1}{n} \sum_{k=1}^n \log\left(\frac{k}{n}\right)}_{\text{denote this as } s_n} \right) $$

Note that, with some straightforward algebra $$ \frac{x_{n+1}-x_n}{2} = \frac{1}{2(n+2)} \log\left(1+\frac{1}{n+1}\right) - \frac{1}{(n+1)(n+2)} \left( \log\left(1+\frac{1}{n} \right) - s_n \right) \tag{3} $$ $$ \frac{x_{n+1}+x_n}{2} = \frac{1}{2(n+2)} \log\left(1+\frac{2}{n}\right)+ \frac{1}{2(n+2)} \log\left(1+\frac{1}{n}\right) - \frac{1}{n+2} s_n \tag{4} $$

Bounding $s_n$

Using summation by parts: $$ \sum_{k=1}^n \left(a_{k+1}-a_k\right) b_k = a_{n+1} b_n - a_1 b_1 -\sum_{k=1}^{n-1} a_{k+1} \left(b_{k+1} - b_k \right) $$ with $a_k = \frac{k}{n}$ and $b_k = \log \frac{k}{n}$, we find $$ \begin{eqnarray} s_n &=& 0 - \frac{\log n^{-1}}{n} - \sum_{k=1}^{n-1} \frac{k+1}{n} \log\left(1+\frac{1}{k}\right) \\ &=& -\frac{n-1}{n} + \frac{1}{2} \frac{\log(n)}{n} - \frac{1}{n} \sum_{k=1}^{n-1} \left( \left(k + \frac{1}{2} \right) \log\left(1+\frac{1}{k}\right) - 1 \right) \end{eqnarray} $$ Using elementary integral $\int_0^1 \frac{\mathrm{d}x}{k+x} = \log\left(1+\frac{1}{k}\right)$ we find $$ \left(k + \frac{1}{2} \right) \log\left(1+\frac{1}{k}\right) - 1 = \int_0^1 \left(\frac{k+\frac{1}{2}}{k+x}-1\right) \mathrm{d}x = \int_0^1 \frac{1-2x}{2(k+x)} \mathrm{d}x $$ changing variables $x \to 1-x$ and averaging with the original: $$\begin{eqnarray} \left(k + \frac{1}{2} \right) \log\left(1+\frac{1}{k}\right) - 1 &=& \int_0^1 \frac{ \left(x-\frac{1}{2}\right)^2}{(k+x)(k+1-x)} \mathrm{d}x \\ &=& \int_{-\frac{1}{2}}^{\frac{1}{2}} \frac{ u^2}{\left(k+\frac{1}{2}\right)^2 - u^2 } \mathrm{d} u \end{eqnarray} $$ Since $$ \int_{-\frac{1}{2}}^{\frac{1}{2}} \frac{ u^2}{\left(k+\frac{1}{2}\right)^2 } \mathrm{d} u < \int_{-\frac{1}{2}}^{\frac{1}{2}} \frac{ u^2}{\left(k+\frac{1}{2}\right)^2 - u^2 } \mathrm{d} u < \int_{-\frac{1}{2}}^{\frac{1}{2}} \frac{ u^2}{\left(k+\frac{1}{2}\right)^2 - \frac{1}{4} } \mathrm{d} u $$ We have $$ \frac{1}{12} \frac{1}{\left(k+\frac{1}{2}\right)^2} < \left(k + \frac{1}{2} \right) \log\left(1+\frac{1}{k}\right) - 1 < \frac{1}{12 k(k+1)} = \frac{1}{12 k} - \frac{1}{12 (k+1)} $$ Since $$\frac{1}{12} \frac{1}{\left(k+\frac{1}{2}\right)^2} > \frac{1}{12} \frac{1}{\left(k+\frac{1}{2}\right) \left(k+\frac{3}{2}\right)} = \frac{1}{12} \frac{1}{k+\frac{1}{2}} - \frac{1}{12} \frac{1}{k+\frac{3}{2}} $$

We thus establish that $$ \sum_{k=1}^{n-1} \left( \left(k + \frac{1}{2} \right) \log\left(1+\frac{1}{k}\right) - 1 \right) < \sum_{k=1}^{n-1} \left( \frac{1}{12 k} - \frac{1}{12 (k+1)} \right) = \frac{1}{12} - \frac{1}{12 n} < \frac{1}{12} $$ and $$ \sum_{k=1}^{n-1} \left( \left(k + \frac{1}{2} \right) \log\left(1+\frac{1}{k}\right) - 1 \right) > \sum_{k=1}^{n-1} \left( \frac{1}{12 \left(k+\frac{1}{2}\right)} -\frac{1}{12 \left(k+\frac{3}{2}\right)} \right) = \frac{1}{18} - \frac{1}{6 (2n+1)} = \frac{1}{9} \frac{n-1}{2n+1} $$ The argument above suggests that $ \sum_{k=1}^{n-1} \left( \left(k + \frac{1}{2} \right) \log\left(1+\frac{1}{k}\right) - 1 \right)$ converges to a number $c$ such that $\frac{1}{18} < c < \frac{1}{12}$. Thus $$ -\frac{n-1}{n} + \frac{\log(n)}{2n} - \frac{1}{12 n} < s_n < -\frac{n-1}{n} + \frac{\log(n)}{2n} - \frac{1}{9} \frac{n-1}{n (2n+1)} \tag{5} $$ Implying that $s_n$ converges to $-1$ and that, for large $n$ $$ s_n = -1 + \frac{\log(n)}{2n} + \mathcal{O}\left(n^{-1}\right) $$

Using these bounds

We therefore conclude that $\frac{x_{n+1}-x_n}{2} = \mathcal{O}\left(n^{-2}\right)$ and $\frac{x_{n+1}+x_n}{2} = \mathcal{O}\left(n^{-1}\right)$. Since both the mean and difference are arbitrarily small for large enough $n$: $$ \begin{eqnarray} 2 \exp\left(\frac{x_{n+1}-x_n}{2}\right) \cosh \left(\frac{x_{n+1}+x_n}{2}\right) &<& 2 \frac{1}{1-\frac{x_{n+1}-x_n}{2}} \frac{1}{1-\frac{1}{2} \left(\frac{x_{n+1}+x_n}{2}\right)^2} \\ &=& 2 + 2\left(\frac{x_{n+1}-x_n}{2}\right) + \left(\frac{x_{n+1}+x_n}{2}\right)^2 + \mathcal{o}\left(n^{-3}\right) \\ &=& 2 - \frac{1}{2 n^3} + \mathcal{o}\left(n^{-3}\right) \end{eqnarray} $$

Thus, at least for $n$ large enough the sequence $L_n$ is decreasing.

This painstaking exercise just makes one appreciate the power of calculus.

$\endgroup$
5
  • 12
    $\begingroup$ At first I thought: "man, this proof is invalid because you are using integral" but later I recalled that the most natural definition for logarithm is that using integral. Fortunately the bounty comes from Jonas and not from Chris's sister, otherwise he would reject your worthy proof. Congratulations. $\endgroup$ Commented Feb 8, 2013 at 20:32
  • 5
    $\begingroup$ I have never seen a bounty that large! $\endgroup$
    – user285523
    Commented Nov 11, 2015 at 5:16
  • 1
    $\begingroup$ @0.5772156649... There were 2 bounties awarded, by different users. $\endgroup$
    – Sasha
    Commented Nov 11, 2015 at 13:36
  • $\begingroup$ It also seems that this is the answer with (currently) the largest cumulative bounty earned in this site. $\endgroup$ Commented Nov 27, 2021 at 12:25
  • $\begingroup$ Can you pls add details to the final part? As it is, it does not work or, at least, it is not justified. Thx. $\endgroup$ Commented Apr 12 at 17:36
0
$\begingroup$

My proof attempt contained a fatal mistake. It seems to me that correcting it would be as hard as proving the statement from scratch, so I've decided to give up. The following two lemmas remain valid, and although strictly weaker than the desired result, they might still be useful to someone, so I've decided to leave them here. (Thanks to mercio for pointing out the mistake and apologies to everyone for the inconvenience.)

It is convenient to define $a_n=\sqrt[n]{n!}$ for $n\in\mathbb N$. Then, $L_n=a_{n+1}-a_n$ holds for $n\in\mathbb N$. We define a new sequence by $K_n=\frac{L_n}{a_n}$. Note that $K_n=\frac{a_{n+1}}{a_n}-1$.

Lemma 1. The sequence $(a_n)_{n=1}^\infty$ is strictly increasing.

Proof. Note that $a_{n+1}^{n+1}=(n+1)a_n^n$ holds for all $n\in\mathbb N$ by definition of $(a_n)_{n=1}^\infty$. This implies that $(\frac{a_{n+1}}{a_n})^n=\frac{n+1}{a_{n+1}}$ holds for all $n\in\mathbb N$. But $a_{n+1}^{n+1}=(n+1)!<(n+1)^{n+1}$, therefore we have $a_{n+1}<n+1$ or equivalently $\frac{n+1}{a_{n+1}}>1$, proving the claim. $\square$

Lemma 2. The sequence $(K_n)_{n=1}^\infty$ is strictly decreasing.

Proof. Clearly, it suffices to prove that $(K_n+1)_{n=1}^\infty$ is strictly decreasing. By definition of $K_n$, this means that we have to show that $\frac{a_{n+2}}{a_{n+1}}<\frac{a_{n+1}}{a_n}$ holds for all $n\in\mathbb N$. This is clearly equivalent to showing $a_{n+2}a_n<a_{n+1}^2$, which is the same as showing that $a_{n+2}^{n+2}a_n^{n+2}<a_{n+1}^{2n+4}$ holds for all $n$. By definition of $(a_n)_{n=1}^\infty$ this is equivalent to $(n+2)!n!a_n^2<((n+1)!)^2a_{n+1}^2$, so we only have to show that $$\frac{a_n^2}{a_{n+1}^2}<\frac{n+1}{n+2}$$ is true for all $n$. We can easily establish this fact by induction. Clearly, it holds for $n=1$. Suppose now, it holds for some $n\in\mathbb N$. We will show that it must also hold for $n+1$. To do this, note that $$\begin{align}\Biggl(\frac{a_{n+1}^2}{a_{n+2}^2}\Biggr)^{n+2}&=\frac{((n+1)!)^2a_{n+1}^2}{((n+2)!)^2}\\ &=\frac{(n!)^2(n+1)^2a_{n+1}^2}{((n+1)!)^2(n+2)^2}\\ &=\frac{a_n^{2n}(n+1)^2a_{n+1}^2}{(a_{n+1})^{2n+2}(n+2)^2}\\ &=\Biggl(\frac{a_n^2}{a_{n+1}^2}\Biggr)^n\frac{(n+1)^2}{(n+2)^2}\overset{\text{I.H.}}{<}\Biggl(\frac{n+1}{n+2}\Biggr)^{n+2}<\Biggl(\frac{n+2}{n+3}\Biggr)^{n+2}.\end{align}$$ Here "I.H." denotes the place where we used the inductive hypothesis. Taking $(n+2)$-nd roots completes the induction. $\square$

$\endgroup$
3
  • 4
    $\begingroup$ But, don't you have $L_n = K_n a_n$ from the definition of $K_n$ ? at the end this get switched to $L_n = K_n / a_n$. $\endgroup$
    – mercio
    Commented Feb 8, 2013 at 16:14
  • 1
    $\begingroup$ Good observation mercio, it becomes $L_{n+1}\over L_n$$=$${K_{n+1}a_{n+1}}\over K_na_n$ and $K_{n+1}\over K_n$$<1$ but $a_{n+1}\over a_n$$>1$ so nothing from this could be said about the monotonicity of the $L_n$. $\endgroup$
    – A.P.
    Commented Feb 8, 2013 at 16:28
  • 1
    $\begingroup$ What a pity, I saw the light at the end of the tunnel, but it is true, the last proposition is flawed :-( $\endgroup$ Commented Feb 8, 2013 at 16:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .