0

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

Katie Melosto
  • 360

2 Answers2

4

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

J.G.
  • 115,835
  • +1; this works well, and I think it's what OP was looking for – J. W. Tanner 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! – Katie Melosto Feb 16 '20 at 20:20
  • 1
    @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 – Katie Melosto Feb 16 '20 at 20:43
  • 1
    @KatieMelosto See edit. – J.G. Feb 16 '20 at 21:25
1

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

J. W. Tanner
  • 60,406