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

  • 6
    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$2012-11-15
  • 6
    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$.2012-11-16
  • 0
    Would it help to look at the second derivative of [$\Gamma(n+1)^{1/n}$](http://tinyurl.com/b4o8hmt)? It's negative and goes to $0$ in the limit... (your site-self-promotion is working ;-)2013-01-14
  • 0
    @draks... yeah, I'm a creative person as regards your last remark :-). However, for the problem I need an approach without calculus.2013-01-14
  • 0
    sorry, I just starred at the equation without reading the prerequisites...2013-01-14
  • 4
    $\sqrt[n] {n!}$ is the geometric mean of 1..n.2013-01-23
  • 1
    @Mark Hurd AM-GM inequality would be too strong to estimate $\sqrt[n]{n!}$. As well I tried HM, you'll have to deal with the harmonic series, which is rather complicated.2013-01-26
  • 4
    @Jonas: Perhaps it would be beneficial to firm up what is meant by "without calculus" in the question statement.2013-02-03
  • 0
    @cardinal: I do not have any suggestions in that regard.2013-02-04
  • 0
    @Jonas: Ok, fair enough. One thing that (immediately) comes to mind: Are we admitting any use at all of the exponential function?2013-02-04
  • 2
    @cardinal: As far as I am concerned, yes.2013-02-04
  • 1
    Can we use the fact that $\sqrt[n] {n!}$ is a stictly increasing function?2013-02-06
  • 15
    @Jonas: For what it's worth, the sequence $L_n$ is called [Lalescu's sequence](http://en.wikipedia.org/wiki/Traian_Lalescu) and is known to converge to $1/e$.2013-02-06
  • 4
    @Mike: Thanks, it is interesting at least to learn that it has a name! Here's a related question I just remembered: http://math.stackexchange.com/q/161682/2013-02-06
  • 0
    One of the things Google finds for Lalescu's sequence is [this answer](http://math.stackexchange.com/a/178798/) by Chris's sister.2013-02-06
  • 0
    It's also interesting that I see answers from new (or less used) MSE accounts.2013-02-06
  • 1
    I couldn't get it to work, but this seems like a good candidate for induction.2013-02-07
  • 0
    Even though it didn't work for me, maybe this could help: $$e\left(\frac ne\right)^n \leq n! \leq e\left(\frac{n+1}e\right)^{n+1}$$2013-02-08
  • 0
    @macydanim: can this inequality be proved without calculus?2013-02-08
  • 0
    Hmm the only proof i found does use integration. http://en.wikipedia.org/wiki/Factorial#Rate_of_growth_and_approximations_for_large_n2013-02-08
  • 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

5 Answers 5

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.

  • 12
    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.2013-02-08
  • 4
    I have never seen a bounty that large!2015-11-11
  • 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}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$$\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$

  • 4
    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$.2013-02-08
  • 1
    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$.2013-02-08
  • 1
    What a pity, I saw the light at the end of the tunnel, but it is true, the last proposition is flawed :-(2013-02-08
-3

Suppose for some $n$ $$L_{n}=\sqrt[n+1] {(n+1)!} - \sqrt[n] {n!} i.e. $$\sqrt[n+1] {(n+1)!} <{\sqrt[n+2] {(n+2)!} + \sqrt[n] {n!} \over 2}$$

Now by the AM-GM Inequality:

$$\sqrt {\sqrt[n+2] {(n+2)!} \sqrt[n] {n!}} <{\sqrt[n+2] {(n+2)!} + \sqrt[n] {n!} \over 2},\space \dots \space \sqrt[n+2] {(n+2)!} \neq\sqrt[n] {n!}$$

I'm not getting anywhere, but it might spark someone else ...

. . .

Just expanding on my comment: Can someone approach this in a less hand-wavy way?

$\sqrt[n] {n!}$ is the Geometric Mean of $ 1 .. n $

As such, $\sqrt[n+1] {(n+1)!}$ (the Geometric Mean of $ 1 .. (n+1) $) will always be greater, but by a lesser amount for each increasing $n$. (Yeah, this is effectively assuming what we're trying to prove.)

  • 0
    @MichaelLi Yeah, and it doesn't help disprove the previous inequality in any way, irrespective of its size.2013-02-08
-7

$\sqrt[n+1]{(n+1)n!}-\sqrt[n]{n!}$

$\sqrt[n+1]{n!}*\color{red}{\sqrt[n+1]{n+1}}-\sqrt[n]{n!}$

The red one gets smaller and smaller very quickly. In fact, it has 1 as limit because for $\sqrt[n]{n}=b$, $b \geq 1$ is required since multiplying something less than 1 multiple time by itself make it smaller.

($n^n<(n+1)^{(n+1)} \forall n \in [0,1[$)

So for huge n, red part can be replaced by 1.(That is not the same "magnitude")

$\sqrt[n+1]{n!}*\color{red}{1}-\sqrt[n]{n!}$ Or $\sqrt[n+1]{n!}-\sqrt[n]{n!}$

And we see something hapenning here : $\sqrt[n+1]{n!}$ is obviously smaller than $\sqrt[n]{n!}$ and that will stay. So higher is $n$ lower is the whole expression.

Explanations

$n+1$ is a linear function. When number become huge, $n+1$ can be confused with $n$ (like in 100000+1) $\sqrt[2]{x}$ is quadratic and greater is $x$ more it is "relatively" reduced. Like $\sqrt[2]{100}$ is reduced by 10 times while $\sqrt[2]{10000}$ is reduced by 100 times. $\sqrt[x]{x}$ reduces his argument even more. Looking at "rate", $\sqrt[x]{x}$ reduce his argument way faster than $\sqrt[x]{x!}$, as much that it become insignificant. That's why I extracted it from $\sqrt[n+1]{(n+1)!}$. I agree that limits are somewhat used here but it does only involve basic logic skills, I mean nothing that is advanced.

  • 1
    You talk about limits in your proof, but as I mentioned above, the proof won't use calculus.2013-02-04
  • 1
    I'm not sure I understand your way at all. I checked again and again the answer but I don't see the way this is related to the fact that the sequence is decreasing. Anyway, thank you for your work! Please provide with more details if possible.2013-02-04
  • 0
    Can calculations and inference be used ? (but I guess it will lead to limits ...)2013-02-04
  • 4
    I don't think this answer answers the question. I don't see how the fact that $\sqrt[n+1]{n!}<\sqrt[n]{n!}$ helps. Note that $\sqrt[n+1]{(n+1)!}-\sqrt[n]{n!}$ is positive; I think it decreases to $\frac{1}{e}$ as $n\to \infty$. If you are going to use an approximation $\sqrt[n+1]{n+1}\approx 1$, I think it will have to be done more carefully.2013-02-05
  • 12
    Please consider deleting this answer.2013-02-06
  • 4
    @Sasha It is better to keep a wrong answer and explain why it is so than simply deleting it.2013-02-08
  • 9
    @programaths But following this logic each question may contain dozens of incorrect answers. There many downsides to keeping wrong answers not least of which is cluttering the page.2013-02-08
  • 7
    @Sasha: isn't the whole point of SE that downvoted answers become less visible (grayed out, sink to the bottom)? This site is not a maths textbook. "Bad" answers that are clearly marked as such can give new users a lot of information, by showing the kinds of arguments that are not acceptable. If these were to be deleted as a general rule, then that information would be lost.2013-02-10
  • 0
    Some bad answers contain good ideas. However personally I delete my own bad answers.2013-02-13
-7

Take $\ell_n = \sqrt[n]{n!}$. You should be able to see that $\ell_n$ is increasing: $$ \ell_{n+1} > \ell_{n} >0, \quad \mbox{ for all } n, $$ so $$ L_n = \ell_{n+1}-\ell_{n} > 0, \quad \mbox{ for all } n, $$ and $$ \frac{\ell_{n+1}}{\ell_n}-1 > 0, \quad \mbox{ and } \quad \frac{\ell_{n}}{\ell_{n+1}}-1<0, \quad \mbox{ for all } n. $$ Fix $n$. In particular, $$ \frac{\ell_{n+1}}{\ell_n}-1>0>\frac{\ell_{n-1}}{\ell_n}-1. $$ Dividing by the right hand side gives $$ \frac{ \frac{\ell_{n+1}}{\ell_n}-1 }{ \frac{\ell_{n-1}}{\ell_n}-1 } > 1. $$ Now the left hand side of this is equal to $$ \frac{\ell_{n+1}-\ell_{n}}{\ell_{n-1}-\ell_n}=\frac{L_n}{-L_{n-1}}. $$ We multiply by $-L_{n-1}$, which is negative, to get $$ L_n < L_{n-1}. $$

  • 3
    Regarding the inequality $>1$, dividing the inequality by a negative number should change the direction of the inequality. Regarding the last inequality, you get $-L_{n-1}$ on the RHS, not $L_{n-1}$.2013-02-06
  • 2
    you used $a>b\implies \frac{a}{b}\gt 1$, but that is not true for $\forall a,b,\in \Bbb R$2013-02-06
  • 0
    whoops. sorry you are correct.2013-02-06
  • 15
    @rffy Please consider deleting this answer.2013-02-06