1
$\begingroup$

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

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

2 Answers 2

8
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Is $n(n+1)$ not $n(n-1)$? $f(1)=1$ not $f(1)=0$ $\endgroup$
    – rlartiga
    Commented Apr 22, 2015 at 20:03
  • $\begingroup$ Uh oh! Thanks for catching the error. $\endgroup$
    – Umberto P.
    Commented Apr 22, 2015 at 20:12
  • $\begingroup$ How did you know to divide by (n!)^2 to conveniently get a nice looking recurrence relation for g(n)? $\endgroup$
    – Hyune
    Commented Apr 22, 2015 at 20:27
  • 1
    $\begingroup$ 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)$. $\endgroup$ Commented Apr 22, 2015 at 21:28
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .