How to convert the recursive function $f(n)=n\cdot f(n-1)+1$ to an explicit function

Question

$f(0)=1$

$f(n)=n\cdot f(n-1)+1$

How can an explicit function be derived from this?

Answer 1

The general strategy here is to make a "guess" and prove it: $$ f(0)=1$$ $$ f(1)=1\cdot f(0)+1=2$$ $$ f(2)=2\cdot f(1)+1=5$$ $$ f(3)=3\cdot f(2)+1=16$$ $$ f(4)=4\cdot f(3)+1=65$$ $$ f(5)=5\cdot f(4)+1=326$$ We can write out the computations to get an idea of what's going on: $$ f(2)=2\cdot 2+1=2\cdot 2!+1$$ $$ f(3)=3\cdot f(2)+1=3(2\cdot 2+1)+1=2\cdot 3!+3+1$$ $$ f(4)=4(3(2\cdot 2+1)+1)+1=2\cdot 4!+4\cdot 3+4+1=2\cdot 4!+\frac{4!}{2!}+\frac{4!}{3!}+\frac{4!}{4!}.$$ Now, this predicts a general trend that for $n\ge 2$, $$ f(n)=2n!+\sum_{k=2}^n \frac{n!}{k!}.$$ Indeed, this is true for $f(2)=2\cdot 2!+1=5$. Suppose the formula holds for $n$, then $$ f(n+1)=(n+1)\bigg(2n!+\sum_{k=2}^n \frac{n!}{k!}\bigg)+1=2(n+1)!+\sum_{k=2}^n\frac{(n+1)!}{k!}+1=2(n+1)!+\sum_{k=2}^{n+1}\frac{(n+1)!}{k!}.$$ This completes the proof. This rule does not apply (in its current form) to the cases $n=0,1$, but we get $$ f(n)= \begin{cases} 1&n=0\\ 2&n=1\\ 2n!+\sum_{k=2}^n \frac{n!}{k!}&n\ge 2. \end{cases}$$ Edit: Now that I've seen the other answer here, it is clear that mine can be improved. Indeed, we have that $2n!=\frac{n!}{1!}+\frac{n!}{0!}$. So, the final result is that $$ f(n)=\sum_{k=0}^n \frac{n!}{k!}$$ and this formula holds for all $n$.

Answer 2

In your equation, expand $f(n-1)$ and simplify. Then expand the $f(n-2)$ and simplify. After a few iterations you should see a pattern emerging.

If you are unfamiliar with the falling factorial and Pochhammer Symbol, you may wish to read up on those.

Answer 3

You can denote $u_{n}=\frac{f(n)}{n!}$ and then the recursive formula can be expressed :

$$n!u_{n}=n(n-1)!u_{n-1}+1$$

Now you can easily get a telescoping sum : $$u_{n}-u_{n-1}=\frac{1}{n!}$$

So

$$\sum_{k=1}^{n}\left( u_{k}-u_{k-1} \right)=\sum_{k=1}^{n}\frac{1}{k!}\Rightarrow u_{n}-u_{0}=\sum_{k=1}^{n}\frac{1}{k!} $$

Which implies

$$f(n)=n!u_{n}=n!\left( \frac{f(0)}{0!}+\sum_{k=1}^{n}\frac{1}{k!} \right)$$

$$f(n)=\sum_{k=0}^{n}\frac{n!}{k!}$$