Is it possible to find a closed form for this recursive sequence?

Question

Is it possible to find a closed form for the sequence defined by

$$\begin{align*} a_0&=3\\ na_n&=(n-1)a_{n-1}+1\quad\text{for }n\ge 1\;. \end{align*}$$

Answer 1

It’s always a good idea to calculate a few values. Here we have $1\cdot a_1=(1-1)a_0+1=1$, so $a_1=1$. Then $2a_2=(2-1)a_1+1=2$, so $a_2=1$. Similarly, $3a_3=(3-1)a_2+1=3$, so $a_3=1$. At this point you might begin to suspect that $a_n=1$ for all $n\ge 1$, and the calculations up to this point suggest how to prove this by induction on $n$: if $a_n=1$, then

$$(n+1)a_{n+1}=na_n+1=n+1$$

and the induction step works just fine.

That’s the simple, easy approach. There is another fairly nice way to deal with this one, though. You might notice that the $na_n$ and $(n-1)a_{n-1}$ on the two sides of the recurrence are examples of ths same function, once for $n$ and once for $n-1$. Since this combination appears consistently, let’s give it a name: let $b_n=na_n$ for each $n$. Then the recurrence becomes $b_n=b_{n-1}+1$, where $b_0=0$. It’s now trivial to see that $b_n=n$ for $n\ge 1$ and hence that $a_n=\frac{b_n}n=1$ for $n\ge 1$.