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).
Prove that n!e-2< \sum_{k=1}^{n}(^{n}\textrm{P}_{k}) \leq n!e-1
-
0Do you know how to approximate $\sum_{k=0}^{n-1}\frac{1}{k!}$? – 2012-10-09
3 Answers
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