Solve the following recurrence relation:

Question

Solve the following recurrence relation: $f(1) = 1$ and for $n \ge 2$,

$$f(n) = n^2f(n − 1) + n(n!)^2$$

How would I go about solving this?

• Would I need to find a substitution $f(n) =\text{ insert here }g(n)$ in aim of getting rid of the $n^2$ that is multiplied onto $f(n-1)$

• Then use the method of differences/ladder method to simplify down $g(n)$

• Then substitute back into $f(n)$?

Answer 1

Divide everything by $(n!)^2$: $$\frac{f(n)}{(n!)^2} = \frac{n^2 f(n-1)}{(n!)^2} + n = \frac{f(n-1)}{((n-1)!)^2} + n.$$ If you write $g(n) = \frac{f(n)}{(n!)^2}$ you get $$g(n) = g(n-1) + n.$$ Since $g(1) = 1$, this becomes $g(n) = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ so that $$f(n) = (n!)^2 \frac{n(n+1)}{2}.$$

Answer 2

If you have a linear recurrence of the first order:

$$ f(n + 1) = g(n) f(n) + h(n) $$

if you divide by the summing factor $s(n) = \prod_{0 \le k \le n} g(n)$ you are left with:

$$ \frac{f(n + 1)}{s(n)} - \frac{f(n)}{s(n - 1)} = \frac{h(n)}{s(n)} $$

Adding this for $k$ from $0$ to $n$ telescopes nicely:

$$ \frac{f(n + 1)}{s(n)} = f(0) + \sum_{0 \le k \le n} \frac{h(k)}{s(k)} $$