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

  • 1
    $\begingroup$ Did you try proving it by induction? $\endgroup$ Feb 16 '20 at 20:05
  • $\begingroup$ 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:) $\endgroup$ Feb 16 '20 at 20:08
  • $\begingroup$ If you edit in your telescoping argument, we may identify the mistake. $\endgroup$
    – J.G.
    Feb 16 '20 at 20:11
  • $\begingroup$ Hi! Thanks so much @J.G. I added my incorrect telescoping process $\endgroup$ 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.$$

  • $\begingroup$ +1; this works well, and I think it's what OP was looking for $\endgroup$ Feb 16 '20 at 20:13
  • $\begingroup$ @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! $\endgroup$ Feb 16 '20 at 20:20
  • 1
    $\begingroup$ @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. $\endgroup$
    – J.G.
    Feb 16 '20 at 20:32
  • $\begingroup$ @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 $\endgroup$ Feb 16 '20 at 20:43
  • 1
    $\begingroup$ @KatieMelosto See edit. $\endgroup$
    – 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)!$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.