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?
 A: This is slightly reverse-engineered; I don't know whether I would have come up with it without knowing the answer – but it's certainly something that someone with much experience with such things could come up with.
First, note that both values of $f$ are being multiplied by one more than their argument, so the right-hand side suggests considering $g(n)=(n+1)f(n)$. That yields
$$
\frac{g(n)}{n+1} = \begin{cases} 1 & n \leq 2 \\ g(n-1) + g(n-2) & \text{otherwise.}\end{cases}
$$
Multiply through by $n+1$:
$$
g(n) = \begin{cases} n+1 & n \leq 2 \\ (n+1) (g(n-1) + g(n-2)) & \text{otherwise.}\end{cases}
$$
Now both the factorial $n!$ and the subfactorial $!n$ satisfy the recurrence
$$f(n+2)=(n+1)(f(n+1)+f(n))\;.$$
(This is an elementary arithmetic fact for the factorial, and a combinatorial identity about derangements for the subfactorial.)
This is almost what we have; we just need to shift the argument by $2$. So replace $g(n)$ by $h(n+2)$:
$$
h(n+2)=\begin{cases} n+1 & n \leq 2 \\ (n+1) (h(n+1) + h(n)) & \text{otherwise.}\end{cases}
$$
This is the recurrence for $n!$ and $!n$, so we know two linearly independent solutions and can superimpose them with coefficients to be determined to satisfy the initial conditions:
$$
h(n)=an!+b!n\;,\\
h(3)=6a+2b=2\;,\\
h(4)=24a+9b=3\;.
$$
Thus $a=2$ and $b=-5$, and substituting back we get
$$
f(n)=\frac{g(n)}{n+1}=\frac{h(n+2)}{n+1}=\frac{2(n+2)!-5!n}{n+1}\;,
$$
which is Wolfram|Alpha's result (up to their tendency to express factorials in terms of the gamma function).
A: 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. 
