Recurrence relation $f(n)=2f(n-1)+n\log(n)$

Question

How to solve the following recurrence relation: $f(n)=2f(n-1)+n\log(n)$ ? I tried to write $f(n-1)=2f(n-2)+(n-1)\log(n-1)$, so

$f(n)=4f(n-2)+2(n-1)\log(n-1)+n\log(n)$

and then the general relation at the $k$'s iteration level is complicated, is there another method to solve this?

$2^{-n}f(n)=f(0)+\sum_{k=1}^{n} 2^{-k}k\log k$ – Oolong Milktea May 08 '22 at 08:29 — Oolong Milktea, May 08 '22 at 08:29

score 1 · Answer 1 · edited May 08 '22 at 08:44

1

If you continue to write it l, you get that

$f(n)=4f(n-2)+\log(n^n(n-1)^{2(n-1)})$

This suggest you that the general formula is

$f(n)=2^nf(0)+\log(\prod_{k=1}^n k^{2^{n-k}k})$

Check it using induction to be sure.

edited May 08 '22 at 08:44

Gary

answered May 08 '22 at 08:31

Federico Fallucca

score 0 · Answer 2 · answered May 08 '22 at 08:33

0

Multiply the equation by $2^{-n}$, and you will get $$ 2^{-n}f(n) = 2^{-(n-1)}f(n-1) + 2^{-n}n\log n. $$ Then you can sum over this equation.

answered May 08 '22 at 08:33

Kervyn

2 Answers2