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 Apr 22 '15 at 19:58
  • $\begingroup$ @abiessu: Not quite: there are three factors of $n$ in the last term. $\endgroup$ – Brian M. Scott Apr 22 '15 at 19:59
  • $\begingroup$ @BrianM.Scott: yes, caught that only a moment ago... $\endgroup$ – abiessu Apr 22 '15 at 20:00
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 Apr 22 '15 at 20:03
  • $\begingroup$ Uh oh! Thanks for catching the error. $\endgroup$ – Umberto P. Apr 22 '15 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 Apr 22 '15 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$ – Robert Israel Apr 22 '15 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.