Solve the recurrence $a_n=na_{n−1}+n!$

Question

I'm working on a practice set:

Solve the recurrence $a_n=na_{n−1}+n!$ for $n>0$ with $a_0=1$ Give a simple expression for $a_n$

For this problem I know the answer is $(n+1)!$ But I'm not sure how to get there....

Here is what I did so far:

I divided the equation by n so: $\frac{a_n}{n} = a_{n-1} + (n-1)!$

Then I used telescoping, so: $\frac{a_n}{n} = a_{n-1} + (n-1)!$

$\frac{a_{n-1}}{n-1} = a_{n-2} + (n-2)!$

$\frac{a_{n-2}}{n-2} = a_{n-3} + (n-3)!$

$...$

So I cancel terms across the equal sign and I get:

$a_n = a_0 + (n-1)!$

But this is not correct.

Thanks for help

Answer 1

Telescope $b_n:=a_n/n!$, which satisfies $b_n-b_{n-1}=1$ because$$b_n=\frac{na_{n-1}+n!}{n!}=\frac{a_{n-1}}{(n-1)!}+1=b_{n-1}+1.$$

Answer 2

Induction works:

base case: $n=0$

induction step: $a_{n+1}=(n+1)a_n+(n+1)!=(n+1)(n+1)!+(n+1)!=(n+2)!$