summation - Prove that $n-1$ divides $n!left(1+sumlimits_{k=2}^{n}frac{(-1)^k}{k!}right)$

Prove that $n-1$ divides $n!\left(1+\sum\limits_{k=2}^{n}\frac{(-1)^k}{k!}\right)$.

There is a sequence: $a_1=1$, $a_{n}=n\cdot a_{n-1}+(-1)^n$. The question is to prove that $n-1$ divides $a_n$.

My approach was to notice the general formula for $a_n$, namely:

$$ a_n=n!\left(1+\sum_{k=2}^{n}\frac{(-1)^k}{k!}\right) $$

(this is trivial to verify just by plugging into the recursive relation). Now, how should I show that $n-1$ divides $$n!\left(1+\sum_{k=2}^{n}\frac{(-1)^k}{k!}\right)\ ?$$

At first, I thought it was trivial, then I noticed that the term in the parentheses is not an integer. My question is then:

• how to prove the claim that $n-1$ divides $a_n$ using the general formula,

and then:

• maybe it can be done only using the recurrence relation?

Answer

Use the formulas for derangement:

$$!n = (n - 1) \left[!(n-1) + !(n-2)\right]$$

and

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

We have:

$$\begin{align}n!\left(1+\sum\limits_{k=2}^{n}\frac{(-1)^k}{k!}\right) &= n!\left(1+\sum\limits_{k=\color{red}{0}}^{n}\frac{(-1)^k}{k!}\right)\\
&= n!+!n\\
&= n(n-1)(n-2)!+(n - 1) \left[!(n-1) + !(n-2)\right]\\

&= \color{blue}{(n-1)}\left[n(n-2)!+!(n-1) + !(n-2)\right]\end{align}$$