Solve the following recurrence relation:

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)$?

• Note that you also have $f(n)=n^2(f(n-1)+n!(n-1)!)$ – abiessu Apr 22 '15 at 19:58
• @abiessu: Not quite: there are three factors of $n$ in the last term. – Brian M. Scott Apr 22 '15 at 19:59
• @BrianM.Scott: yes, caught that only a moment ago... – abiessu Apr 22 '15 at 20:00

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}.$$

• Is $n(n+1)$ not $n(n-1)$? $f(1)=1$ not $f(1)=0$ – rlartiga Apr 22 '15 at 20:03
• Uh oh! Thanks for catching the error. – Umberto P. Apr 22 '15 at 20:12
• How did you know to divide by (n!)^2 to conveniently get a nice looking recurrence relation for g(n)? – Hyune Apr 22 '15 at 20:27
• If you want $f(n) = a(n) g(n)$ to put the equation into the form $g(n) = g(n-1) + \ldots$, you need $a(n) = n^2 a(n-1)$. – Robert Israel Apr 22 '15 at 21:28

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)}$$