Closed form for multiplicative recurrence relation

Question

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?

Answer 1

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).

Answer 2

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.