2

While studying derangements, I've found on the internet the following relation : $$\lim_{n\to\infty}\frac{!n}{n!} =\frac{1}{e} \approx 0.3679\ldots.$$

This relation really intrigues me and I would like to know how to prove it.

In the detail,I came across the above limit reading this article from AOPS site . In the article it is said that the above limit can be noted given the recurrence $!n=n\cdot!(n-1)+(-1)^{n}$ .

Sadly I can't note that.

Anyway I've tried to do something.

Given the following relation $ !n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ I have that $ \cfrac{!n}{n!}=\sum_{k=0}^n \cfrac {(-1)^k}{k!} $ .

Now the right hand side of the last equality is interesting because it can be written as $$\sum_{k=0}^n \cfrac {1}{k!} \cdot (-1)^k $$ and I know that $$\sum_{k=0}^\infty \cfrac {1}{k!} =e $$ but now I am left with the trouble of the $(-1)^k$ factor which I don't know how to handle.

Mr. Y
  • 2,637

4 Answers4

3

It is well-known that $$e^x = \sum_{k = 0}^\infty \frac{x^k}{k!}$$ Now set $x = -1$, and you're done.

Arthur
  • 199,419
1

$\exp(x) = \sum_{k=0}^\infty \frac{x^k}{k!}$ for all $x \in \mathbb{R}$.

Hence, for $x=-1$, we have $\exp(-1) = \sum_{k=0}^\infty \frac{(-1)^k}{k!}= \frac1e$.

$D_n = n! \sum_{k=0}^n \frac1{k!}$ so $\lim_{n \to \infty}\frac{D_n}{n!} = \lim_{n \to \infty}\sum_{k=0}^n \frac1{k!} = \sum_{k=0}^\infty \frac{(-1)^k}{k!}= \frac1e$.

Claudeh5
  • 580
1

Maybe the hard way if you don't know the gamma function:

$$\lim_{n\to\infty}\frac{!n}{n!}=\lim_{n\to\infty}\frac{\frac{\Gamma(n+1,-1)}{e}}{\Gamma(n+1)}=\lim_{n\to\infty}\frac{\Gamma(n+1,-1)}{e\Gamma(n+1)}=\frac{1}{e}\lim_{n\to\infty}\frac{\Gamma(n+1,-1)}{\Gamma(n+1)}$$

With $\Gamma(x)$ is the gamma function and $\Gamma(s,x)$ is the incomplete gamma function

Jan Eerland
  • 28,671
  • Hmm...Can you give me some link for gamma function,so I can learn it ? Thanks for your answer,I like to have multiple approaches on one problem. – Mr. Y Nov 22 '15 at 12:25
  • @Mr.Y I learned it at university, but wikipedia gives a ery good explanation (https://en.wikipedia.org/wiki/Gamma_function) – Jan Eerland Nov 22 '15 at 12:27
1

Since, by definition, $!n = n! \sum_{k = 0}^{n} \frac {(-1)^k} {k!}$, it is easy to obtain

$$\lim_{n\to\infty}\frac{!n}{n!} = \sum_{k = 0}^{\infty} \frac {(-1)^k} {k!},$$

which is $\frac {1} {e}$.

The more intriguing is the equality in the article that you referred to

$$!n = \left \lfloor \frac {n!} {e} + \frac {1} {2} \right \rfloor,$$

and this is provable by induction on $n$ in the recurrence relation given for $!n$.