Finding a closed form for recurrence relations $a_n=na_{n-1}+1$ and $a_n=na_{n-1}+n$

Question

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

Answer 1

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

Answer 2

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