Finding a closed form for recurrence relations $a_n=na_{n-1}+1$ and $a_n=na_{n-1}+n$ Consider the sequence defined by
$$
\begin{cases}
a_0=1\\
a_n=n\cdot a_{n-1}+1 & \text{if }n\ge 1
\end{cases}
$$
Find a closed form for $a_n$.
Second case is as follows:
$$
\begin{cases}
a_0=1\\
a_n=n\cdot a_{n-1}+n & \text{if }n\ge 1
\end{cases}
$$
Find a closed form for $a_n$.
 A: Try exponential generating functions (and another link here). For example, let's look at the first recurrence
$$f(x)=\sum\limits_{n=0}\color{red}{a_n}\frac{x^n}{n!}=
1+\sum\limits_{n=1}a_n\frac{x^n}{n!}=\\
1+\sum\limits_{n=1}(n\cdot a_{n-1} + 1)\frac{x^n}{n!}=
1+\sum\limits_{n=1}a_{n-1} \frac{x^n}{(n-1)!} + \sum\limits_{n=1}\frac{x^n}{n!}=\\
x\left(\sum\limits_{n=1}a_{n-1} \frac{x^{n-1}}{(n-1)!}\right) + \sum\limits_{n=0}\frac{x^n}{n!}=\\
x\left(\sum\limits_{n=0}a_{n} \frac{x^{n}}{n!}\right) + \sum\limits_{n=0}\frac{x^n}{n!}=\\
x\cdot f(x) + e^x$$
or (applying series multiplication, below the 2nd defition here)
$$f(x)=\frac{e^x}{1-x}=\left(\sum\limits_{n=0}\frac{x^n}{n!}\right)\left(\sum\limits_{n=0}x^n\right)=\\
\sum\limits_{n=0}\left(\sum\limits_{i=0}^n\frac{1}{i!}\cdot 1\right)x^n=
\sum\limits_{n=0}\color{red}{\left(\sum\limits_{i=0}^n\frac{n!}{i!}\right)}\frac{x^n}{n!}$$
and finally
$$a_n=\sum\limits_{i=0}^n\frac{n!}{i!}=
n!\left(\sum\limits_{i=0}^n\frac{1}{i!}\right)$$
A: Hint:
$$a_n=na_{n-1}+1$$
$$\Rightarrow a_n=n(n-1)a_{n-2}+1+n$$
$$\Rightarrow a_n=n(n-1)(n-2)a_{n-3}+1+n+n(n-2)$$
Continuing so on we get,
$$a_n=a_0n!+\sum_{k=1}^n \frac {n!}{k!}=n!\left(1+\sum_{k=1}^n \frac {1}{k!}\right)=n!\sum_{k=0}^n\frac{1}{k!}$$
Similarly you can solve for the second case to get,
$$a_n=n!\left(1+\sum_{k=0}^{n-1} \frac{1}{k!}\right)$$
