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

@abiessu: Not quite: there are three factors of $n$ in the last term. — Brian M. Scott, Apr 22 '15 at 19:59

Umberto P. · Answer 1 · 2015-04-22T20:12:18.760

8

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

edited Apr 22 '15 at 20:12

answered Apr 22 '15 at 19:59

Umberto P.

52,165

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
1

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

score 0 · Answer 2 · answered Aug 09 '15 at 23:10

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

Solve the following recurrence relation:

2 Answers2