Integer part of n!/e

 This is a classic puzzle. I am hoping the solution is new (unlikely though). Anyway.

The problem is: 

Show that the integer part of  $\dfrac{n!}{e}$ is always an even number, for positive integer $n$.

Scroll down for a solution.

.

.

.

.

.

We will use the following two:

$\textbf{Claim 1}$: 

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

$\textbf{Proof:}$

Use

$$\frac{1}{(2n)!} - \frac{1}{(2n+1)!} = \frac{2n}{(2n+1)!}$$

and $$e^x = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots $$

(put $x = -1$ above). 

$\textbf{Claim 2}$:

$$\sum_{k = 1}^{n} \frac{a_k - 1}{a_1 a_2 \dots a_k} = 1 - \frac{1}{a_1 a_2 \dots a_n}$$

$\textbf{Proof:}$ Easy induction.

Now to the problem. 

$$\frac{N!}{e} = \sum_{n=1}^{\infty} \frac{2n N!}{(2n+1)!}$$

If $M = 2m+1$ is the largest odd integer $\leq N$ then we have

$$\frac{N!}{e} = \sum_{n=1}^{m} 2n \frac{N!}{(2n+1)!} + N! \sum_{n=m+1}^{\infty} \frac{2n}{(2n+1)!}$$ 

The first $\sum_{n=1}^{m}$ term is an even integer and the second term

$$N! \sum_{n=m+1}^{\infty} \frac{2n}{(2n+1)!} < \sum_{n=m+1}^{\infty} \frac{2n}{(2m+3)(2m+5)\dots(2n+1)} = 1$$

The equality of $1$ is because of claim 2 above (put $a_1, a_2, \dots = 2m+3, 2m+5, \dots$). 

Thus the integer part of $\frac{N!}{e}$ is an even integer. 

$\textbf{Additional Remarks:}$ Note that the above proof can be easily modified to give the following recurrence relation for $S_n = \lfloor n!/e \rfloor$.

$$\begin{aligned}&S_{2n+1} = (2n+1) S_{2n} + 2n \\ &  S_{2n} = 2n S_{2n-1}\end{aligned}$$

which yields the sequence $$0,0,2,8,44, 264, 1854, \dots$$

OEIS entry is here.