1
$\begingroup$

Prove that $n!e-2 < \sum_{k=1}^{n}(^{n}\textrm{P}_{k}) \leq n!e-1$ where $^{n}\textrm{P}_k = n(n-1)\cdots(n-k+1)$ is the number of permutations of $k$ distinct objects from $n$ distinct objects and $e$ is the exponential constant (Euler's number).

  • 0
    Do you know how to approximate $\sum_{k=0}^{n-1}\frac{1}{k!}$?2012-10-09

3 Answers 3

2

Since ${}^n P_k / n! = 1/(n-k)!$, we have to prove the following:

$\displaystyle e - \frac{1}{n!} < \sum_{k=0}^n \frac{1}{k!} < e$

which follows obviously from the expansion $e = \sum_{k=0}^\infty \frac{1}{k!}$ and the estimate

$\displaystyle \sum_{k \ge n+1} \frac{1}{k!} \le \sum_{\ell=0}^\infty \frac{1}{(n+1)^\ell} \frac{1}{(n+1)!} = \frac{1}{n \cdot n!}$

1

The identity is equivalent to

$e-\frac{2}{n!} < \sum_{k=1}^{n}\frac{^{n}\textrm{P}_{k}}{n!} < e-\frac{1}{n!}$

Since

$\frac{^{n}\textrm{P}_{k}}{n!}=\frac{1}{(n-k)!}$, the inequality becomes

$e-\frac{2}{n!} < \sum_{k=1}^{n}\frac{1}{(n-k)!} < e-\frac{1}{n!}$

or

$e-\frac{1}{n!} < \sum_{k=0}^{n}\frac{1}{(n-k)!} < e$

Using $e=\sum_{k=0}^{\infty}\frac{1}{k!}$, the RHS inequality is trivial, while the LHS reduces to

$ \sum_{k=n+1}^{\infty}\frac{1}{k!} < \frac{1}{n!}$

This is easy to prove. Indeed

$ \sum_{k=n+1}^{\infty}\frac{1}{k!} =\frac{1}{(n+1)!}+ \sum_{k=n+2}^{\infty}\frac{1}{k!} \leq \frac{1}{(n+1)!}+ \sum_{k=n+2}^{\infty}\frac{1}{n!(k-1)k}$ $= \frac{1}{(n+1)!}+\frac{1}{n!}\sum_{k=n+2}^{\infty}\frac{1}{(k-1)k} =\frac{1}{(n+1)!}+\frac{1}{n!}\frac{1}{n+1}$

with the last equality following from the calculation of the telescopic sum

$\sum_{k=n+2}^{\infty}\frac{1}{(k-1)k}=\frac{1}{(n+2)-1}$

Thus we proved that

$ \sum_{k=n+1}^{\infty}\frac{1}{k!} \leq \frac{2}{(n+1)!} < \frac{1}{n!}$

0

Denote the expression in question by $S$ $ \sum_{k=0}^{n-1}\frac{1}{k!}=e-\sum_{k=n}^{\infty}\frac{1}{k!}=e-\frac{1}{n!}\bigg(1+\frac{1}{n+1}+\frac{1}{(n+1)(n+2)} + \cdots \bigg)\\ \leq e-\frac{1}{n!} \bigg(1+\frac{1}{n+1} + \frac{1}{(n+1)^2} +\cdots \bigg)\\ =e-\frac{1}{n!} \sum_{k=0}^{\infty} \bigg(\frac{1}{n+1} \bigg)^k=e-\frac{1}{n!}\bigg(1+\frac{1}{n}\bigg) $ Pre-multiplying this by $n!$ the upper bounds comes out easily: $ S