<s>[INST] Closed form for multiplicative recurrence relation In this StackOverflow question, I found an interesting recurrence relation:
$$f(n) = \begin{cases} 1 & n \leq 2 \\ nf(n-1) + (n-1)f(n-2) & \text{otherwise.}\end{cases}$$
I plugged it into Wolfram Alpha, and it gives me the solution:
$$f(n) = \frac{2~\Gamma(n+3) - 5~!(n+2)}{n+1}$$
How would a human being go about solving something like this? Could I use generating functions in some clever way?
 [/INST] Note that $\Gamma(n+3)=(n+2)!$.
$$f(n) = \frac{2\Gamma(n+3) - 5!(n+2)}{n+1}=\frac{2(n+2)! - 5 \cdot !(n+2)}{n+1}$$
Once one has this form, it is not hard using induction:
\begin{align*} f(n+1)&=(n+1)f(n)+nf(n-1) \\ &=\frac{2(n+2)! - 5 \cdot !(n+2)}{n+1}(n-2)+\frac{2(n+1)! - 5 \cdot !(n+1)}{n}n \\ &= 2(n+2)! - 5 \cdot !(n+2) + 2(n+1)! - 5 \cdot !(n+1) \\ &= 2(n+2)(n+1)! - 5 \cdot !(n+2) + 2(n+1)! - 5 \cdot !(n+1)  \\ &= 2(n+3)(n+1)! - 5 \cdot !(n+2) - 5 \cdot !(n+1)  \\ &= 2(n+3)(n+1)! - 5 \cdot (!(n+2)+ !(n+1)) \\&= \frac{[2(n+3)(n+1)! - 5 \cdot (!(n+2)+ !(n+1))](n-2)}{n-2} \\&= \frac{2(n+3)(n-2)(n+1)! - 5(n-2) \cdot (!(n+2)+ !(n+1))}{n-2} \\&= \frac{2(n+3)! - 5 \cdot !(n+3)}{n+2}\end{align*}
The last step uses the recurrence relation given here.

To find such formula, just notice that the closed form is the sum of a lot of factorials, and you could probably find it by writing it as factorials while doing some small cases. 
</s>