The following problem is taken from an algorithms textbook(specifically, in the context of complexity analysis of recursive algorithms.)
Starting from the equation:
$$nf(n) = n(n-1) + 2 \sum_{k=1}^{n}f(k-1)$$ Prove that:
$$f(n)\approx 1.44n \log(n)$$
How would you go about this problem?
I tried to approach this problem by proving it with induction, but I couldn't make it hold for the inductive step(due to them being approximately equal). I also tried expanding the function recursively, but I couldn't find any recurring patterns to generalize. I must be missing something.