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

Question

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 1

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

Answer 2

From the recursion we have that $$a_n = n(n-1)a_{n-2} + (n-1)(-1)^{n-1}. $$ Hence by induction $a_n$ is divisble by $n-1$ for all $n\in\mathbb{N}$ (note this holds true for the first few cases.)