92
$\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.

  • 2
    I think your question is meaning less: I doubt you can construct (I mean really *construct*) any totally ordered nth-root-closed field without calculus (topology, analysis or whatever you call things based on Cauchy sequences).2013-02-12

2 Answers 2

41

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.

  • 1
    @0.5772156649... There were 2 bounties awarded, by different users.2015-11-11
0

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} 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, which is the same as showing that $a_{n+2}^{n+2}a_n^{n+2} 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$

  • 1
    What a pity, I saw the li$g$ht at the end of the tunnel, but it is true, the last proposition is flawed :-(2013-02-08