Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
5  
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$ –  Adi Dani Nov 15 '12 at 22:05
22  
Really? is Chris your brother? –  Matemáticos Chibchas Jan 21 '13 at 4:56
8  
500 reputation points, I see the sharks around...wait, I am one of them! –  Matemáticos Chibchas Feb 6 '13 at 14:29
11  
@Jonas: For what it's worth, the sequence $L_n$ is called Lalescu's sequence and is known to converge to $1/e$. –  Mike Spivey Feb 6 '13 at 20:01
9  
Can you ask your teacher the solution and share it to us ? It has been quite a long time since the question was asked. –  user10676 Feb 13 '13 at 10:33

6 Answers 6

up vote 33 down vote accepted
+1000

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.

share|improve this answer
7  
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. –  Matemáticos Chibchas Feb 8 '13 at 20:32

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

share|improve this answer
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. –  Jonas Meyer Feb 5 '13 at 0:04
11  
Please consider deleting this answer. –  Sasha Feb 6 '13 at 20:43
2  
@Sasha It is better to keep a wrong answer and explain why it is so than simply deleting it. –  programaths Feb 8 '13 at 11:34
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. –  Sasha Feb 8 '13 at 13:24
5  
@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. –  András Salamon Feb 10 '13 at 13:49

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}. $$

share|improve this answer
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}$. –  1015 Feb 6 '13 at 13:45
2  
you used $a>b\implies \frac{a}{b}\gt 1$, but that is not true for $\forall a,b,\in \Bbb R$ –  Aang Feb 6 '13 at 16:13
    
whoops. sorry you are correct. –  user61213 Feb 6 '13 at 18:21
15  
@rffy Please consider deleting this answer. –  Sasha Feb 6 '13 at 20:43

I would use the Stirling's approximation, wich is very accurate when using a big value of n:

http://en.wikipedia.org/wiki/Stirling%27s_approximation

The result is pretty oubvious when you do the replacement.

share|improve this answer
14  
How do you prove that it is accurate enough to preserve monotonicity of this sequence? –  Jonas Meyer Feb 6 '13 at 22:17
7  
Besides, Stirling’s approximation is calculus ... –  Ewan Delanoy Feb 7 '13 at 5:20

Suppose for some $n$ $$L_{n}=\sqrt[n+1] {(n+1)!} - \sqrt[n] {n!}<L_{n+1}=\sqrt[n+2] {(n+2)!} - \sqrt[n+1] {(n+1)!}$$ 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.)

share|improve this answer
    
@MichaelLi Yeah, and it doesn't help disprove the previous inequality in any way, irrespective of its size. –  Mark Hurd Feb 8 '13 at 14:30

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$

share|improve this answer
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$. –  mercio Feb 8 '13 at 16:14
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$. –  A.P. Feb 8 '13 at 16:28
1  
What a pity, I saw the light at the end of the tunnel, but it is true, the last proposition is flawed :-( –  Matemáticos Chibchas Feb 8 '13 at 16:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.