How can I solve this recurrence relation?

Question

Suppose $A_n = n + nA_{n-1}$,

How can I figure out an equation for $A_n$ in terms of $n$?

Let the base case $A_0 = 0$.

Answer 1

To solve this, I would substitute $A_n=nB_n$, which gives $$ nB_n=n+n(n-1)B_{n-1}\implies B_n=1+(n-1)B_{n-1}\tag{1} $$ Writing out a few terms, we can deduce the formula $$ B_n=\sum_{k=0}^{n-2}\frac{(n-1)!}{(n-k-1)!}+(n-1)!B_1\tag{2} $$ This gives $$ \begin{align} A_n &=\sum_{k=0}^{n-2}\frac{n!}{(n-k-1)!}+n!A_1\\ &=\sum_{k=1}^{n-1}\frac{n!}{(n-k)!}+n!A_1\\ &=\sum_{k=1}^n\frac{n!}{(n-k)!}+n!A_0\\ \end{align} $$ Note that for $n\gt0$, $$ \begin{align} \sum_{k=1}^n\frac{n!}{(n-k)!} &=\sum_{k=0}^{n-1}\frac{n!}{k!}\\ &=n!\sum_{k=0}^n\frac1{n!}-1\\[6pt] &=\left\lfloor n!e\right\rfloor-1 \end{align} $$ Therefore, $$ A_n=\left\lfloor n!e\right\rfloor-1+n!A_0 $$

Answer 2

I found $A_n = n! (\sum_{k=0}^{n-1} \frac{1}{k!} +A_0) $ for $n\geq1$

You can check $$A_{n+1}=(n+1)(A_n+1) = (n+1)\left(n! (\sum_{k=0}^{n-1} \frac{1}{k!}+A_0)+1\right) \\=(n+1)! (\sum_{k=0}^{n-1} \frac{1}{k!}+A_0) + \frac{(n+1)!}{n!} \\ = (n+1)!(\sum_{k=0}^{n} \frac{1}{k!}+A_0) $$