Recurrence relations and divisibility

Question

A sequence is defined as follows:

$$u_1 = 1$$

$$u_n = (n-1) u_{n-1} + 1$$

How do I even approach the following question :

For which values of n is $u_n$ divisible by $n$. Include a proper proof

Answer 1

By actual calculation the first $6$ values of $n$ such that $n\mid u_n$ are $1,2,4,5,10$, and $13$. Submitting this sequence to OEIS brings five returns, one of which is the desired sequence: this is OEIS A064383. (The sequence $\langle u_n:n\in\Bbb Z^+\rangle$ is OEIS A000522 with the index offset by $1$.)

It’s not hard to show by induction that

$$\sum_{k=0}^{n-1}\frac1{k!}=\frac{u_n}{(n-1)!}\;.\tag{1}$$

Then

$$u_n=\sum_{k=0}^{n-1}\frac{(n-1)!}{k!}=\sum_{k=0}^{n-1}\frac{(n-1)!}{(n-1-k)!}=\sum_{k=0}^{n-1}\prod_{\ell=1}^k(n-\ell)\equiv\sum_{k=0}^{n-1}(-1)^kk!\pmod{n}\;,$$

where $\prod_{\ell=1}^0(n-\ell)=1$, so the indices $n$ such that $n\mid u_n$ are the positive integers $n$ such that $n$ divides

$$\sum_{k=0}^{n-1}(-1)^kk!\;.$$

There’s a little more information in the OEIS entry and the references there.

Added: One might discover $(1)$ by ‘unwinding’ the recurrence for the $u_n$:

$$\begin{align*} u_n&=(n-1)u_{n-1}+1\\ &=(n-1)(n-2)u_{n-2}+(n-1)+1\\ &=(n-1)(n-2)(n-3)u_{n-3}+(n-1)(n-2)+(n-1)+1\\ &\;\;\vdots\\ &=(n-1)^{\underline k}u_{n-k}+\sum_{\ell=0}^{k-1}(n-1)^{\underline\ell}\\ &\;\;\vdots\\ &=(n-1)!u_1+\sum_{\ell=0}^{n-2}(n-1)^{\underline\ell}\\ &=\sum_{\ell=0}^{n-1}(n-1)^{\underline\ell}\\ &=\sum_{\ell=0}^{n-1}\frac{(n-1)!}{(n-1-\ell)!}\\ &=\sum_{\ell=0}^{n-1}\frac{(n-1)!}{\ell!} \end{align*}$$