How to convert the recursive function $f(n)=n\cdot f(n-1)+1$ to an explicit function $f(0)=1$
$f(n)=n\cdot f(n-1)+1$
How can an explicit function be derived from this?
 A: 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!}$$
A: 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.
A: 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$.
