Prove that $n!e-2$ $<$ $\displaystyle \sum_{k=1}^{n}(^{n}\textrm{P}_{k})$ $\leq$ $n!e-1$

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).

-
Do you know how to approximate $\sum_{k=0}^{n-1}\frac{1}{k!}$? – Alex Oct 9 '12 at 3:19

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

-

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

-

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<n!e-1-\frac{1}{n}$$

-