Summation in recurrence: $T(n) = cn + \frac{4}{n^2}\sum\limits_{k=0}^{n-1}T(k)$

Question

I search the entire forum and couldn't find a solution to this. Can you please help me solve this recurrence equation? $$ T(n) = cn + \frac{4}{n^2}\sum_{k=0}^{n-1}T(k) $$

Answer 1

Write your recurrence as: $$ n^2 T(n) = c n^3 + 4 \sum_{0 \le k \le n - 1} T(n) $$ If you substract this from the next step you get: $$ (n + 1)^2 T(n + 1) - (n^2 + 4) T(n) = c (n + 1)^3 - c n^3 $$ This is a linear recurrence of order 1, so solvable. Write it as: $$ T(n + 1) - u_n T(n) = f_n $$ dividing by $s_n = \prod_{0 \le k \le n} u_k$ gives the difference between $T(n + 1)/s_n$ and $T(n) /s_{n - 1}$, and all you need is to sum up $f_n / s_n$. The result is probably a hairy summation, unlikely to have a simple form. In any case, it should have hypergeometric terms, perhaps Gosper-Zeilberger (see e.g. A = B by Petkovsek, Wilf and Zeilberger, or look for Gosper or Zeilberger in your tame CAS) is able to simplify it (or show it is hopeless).