Hello math help community!

I am a grad student who is attempting to switch to algorithms area and so far it has been tough.

This is a tough question about recurrence relation that contains sum inside the recursion.I am totally stuck and feeling depressed about it. Can anyone help ?

The problem asks to solve and prove correctness for the following recursion$\displaystyle T(n)=\frac{1}{n} (\sum_{i=1}^{n-1}(T(i)+T(n-i))+cn)$. The problem also warns that unwrapping is going to be the wrong approach and the right strategy would be to guess the solution and prove it by induction. As the first step it suggests to start with $\displaystyle nT(n) -(n - 1)T(n -1)$.

Seems like the problem is for experienced people who have seen a lot of recurrences.

I deeply appreciate in advance.