# When does $n$ divide $u_n$ if $u_1=1$, $u_n=(n-1)u_{n-1}+1$? [duplicate]

I'm working through the Background section to 'The Mathematical Olympiad Handbook' by A. Gardiner, OUP, 1997, and this appears on page 17:

(***) Let $$u_1=1$$, $$u_n=(n-1)u_{n-1}+1$$. For which values of $$n$$ is $$u_n$$ divisible by $$n$$?
When you think you know, try to give a proper proof that your answer is correct.

I've not been able to come up with an answer - can anyone help?

For info, the first few values of $$u_n$$ are $$1$$, $$2$$, $$5$$, $$16$$, $$65$$, $$326$$, $$1957$$, $$13700$$, $$109601$$, $$986410$$, $$9864101$$, $$108505112$$, $$1302061345$$, $$16926797486$$,$$\ldots$$ and so the first few values of $$n$$ for which $$n$$ divides $$u_n$$ are $$1$$, $$2$$, $$4$$, $$5$$, $$10$$, $$13$$, $$\ldots$$.

Is there an obvious pattern to this?

• Wolfram Alpha gives no nice general value of $u(n)$ , only $u(n)=e\gamma(n,1)$ where $\gamma(n,1)$ is the incomplete gamme function. Inspecting further solutions , I cannot spot any pattern. Commented Jul 8 at 14:33
• Solutions below $10^5$ : $$1,2,4,5,10,13,20,26,37,52,65,74,130,148,185,260,370,463,481,740,926,962,1852,1924,2315,2405,4630,4810,6019,9260,9620,12038,17131,24076,30095,34262,60190,68524,85655$$ Commented Jul 8 at 14:35
• Seems to be "|Unsolved Problem In Number Theory|" level , while the $n$ are factors of $4*5*13*37*463\cdots$ which are somehow connected to $e$ , naturally !!
– Prem
Commented Jul 8 at 15:39
• He doesn't mention $(***)$ per se, but does say 'make sure that you tackle all the exercises marked with a single asterisk $(*)$. (Harder exercises, which you may well find too difficult on a first reading, are marked with a double asterisk $(**)$.)' Examples of $(**)$ problems are 'Prove that a real number written as a decimal is equal to a rational number if and only if the decimal eventually recurs' and 'Complete the factorisation $x^3+y^3+z^3-3xyz=(x+y+z)(...)$'. This is the only $(***)$ problem. Commented Jul 8 at 15:40
• This question is similar to: Recurrence relations and divisibility. If you believe it’s different, please edit the question, make it clear how it’s different and/or how the answers on that question are not helpful for your problem. Found using an Approach0 search. Note that there are quite a few other duplicates on this site, e.g., ... Commented Jul 8 at 16:59

$$n\mathrel{|}u_n \iff n\mathrel{|}\sum_{k=0}^{n-1}(-1)^kk!$$
We have $$u_n=(n-1)u_{n-1}+1$$, therefore \begin{align*} u_n&\equiv 1-u_{n-1} \pmod{n} \\ u_{n-1}&= (n-2)u_{n-2}+1\equiv1-2u_{n-2}\pmod{n} \\ \vdots \\ u_{n-k}&\equiv 1-(k+1)u_{n-(k+1)}\pmod{n} \end{align*}
So now, substituting, \begin{align*} u_n& \equiv_n1-u_{n-1} \\ & \equiv_n 1-(1-2u_{n-2}) \\ & \equiv_n 1-(1-2(1-3u_{n-3})) \\ & \equiv_n 1-(1-2(1-3(\dots(1-(n-1)u_1)\dots) \\ & \equiv_n 1-(1-2(1-3(\dots(1-(n-1))\dots) \\ & =0!-1!+2!-3!+\dots+(-1)^{n-1}(n-1)! \\ \end{align*}