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

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

• Did you try proving it by induction? Feb 16 '20 at 20:05
• I haven't.... the assignment was on telescoping so was trying to first solve it that way - but open to any info if you sense you can use induction:) Feb 16 '20 at 20:08
• If you edit in your telescoping argument, we may identify the mistake.
– J.G.
Feb 16 '20 at 20:11
• Hi! Thanks so much @J.G. I added my incorrect telescoping process Feb 16 '20 at 20:19

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

• +1; this works well, and I think it's what OP was looking for Feb 16 '20 at 20:13
• @J.G. would like to understand a bit more about your process. I'm not sure I understand $b_n := a_n/n!$ curious how you got there - thanks! Feb 16 '20 at 20:20
• @KatieMelosto I divide by something that multiplies by $n$ at each step, because you need to telescope something of the form $b_n-b_{n-1}$. Your mistake was in trying to telescope something that isn't of that form.
– J.G.
Feb 16 '20 at 20:32
• @J.G.Thanks so much! When you divide $b_n := a_n/n!$ is that: $(a_n = na_{n-1} + n!)/n!$? Trying to put the math together Feb 16 '20 at 20:43
• @KatieMelosto See edit.
– J.G.
Feb 16 '20 at 21:25

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