Solving the recurrence relation $T(n) = \frac{1}{n}(T(0) + T(1) + ... + T(n-1)) + 5n$ I have been trying to solve the following recurrence relation
$T(n) = \frac{1}{n}(T(0) + T(1) + ... + T(n-1)) + 5n$
$T(0) = 0$
I've tried to use substitution which wasn't very useful as I couldn't figure out a way to simplify the resultant equation.
My next approach was to just plug in numbers as follows
$T(1) = 5 * 1$
$T(2) = \frac{1}{2}(5 * 1) + 5 * 2 = \frac{5 * 1}{2} + 5 * 2$
$T(3) = \frac{1}{3}(\frac{5 * 1}{2} + 5 * 2) + 5 * 3 = \frac{5 * 1}{6} + \frac{5 * 2}{3} +  5 * 3$
$T(4) = \frac{1}{4}(\frac{5 * 1}{6} + \frac{5 * 2}{3} +  5 * 3) + 5 * 4 = \frac{5 * 1}{24} + \frac{5 * 2}{12} + \frac{5 * 3}{4} +  5 * 4$
I can sort of see a pattern emerge here like $\sum_{i=1}^{n} \frac{5*i}{previousDenominator/ i}$ however I couldn't really see a way to get that bottom part into an actual equation.
 A: Multiply the recurrence relation by $n$ to get $$nT_n = T_0+T_1+\cdots+T_{n-1}+5n^2.$$ Replacing $n$ with $n+1$ gives $$(n+1)T_{n+1} = T_0+T_1+\cdots+T_{n-1}+T_n+5(n+1)^2.$$ Subtracting the first equation from the second gives $$(n+1)T_{n+1}-nT_n = T_n+5(n+1)^2-5n^2,$$ which can be simplified to $$T_{n+1}-T_n = 10-\dfrac{5}{n+1}.$$ Now you have a closed form for the difference between consecutive values of $T_n$. So just use the equation $$T_n = T_0 + \sum_{k = 0}^{n-1}(T_{k+1}-T_k)$$ and simplify the result to get a formula for $T_n$.
A: The calculation should be continued: We get
$ \begin{array}{rcl}
T_n&=&T_0+10n- 5\sum\limits_{k=0}^{n-1}\frac{1}{k+1} \\
      &=&T_0+10n- 5 H_n
 \end{array}     $
Here the $H_n=1+\frac{1}{2}+\cdots +\frac{1}{n}$ are the so called  harmonic numbers.    It is known that
$H_n= \ln n+\gamma + \varepsilon_n$ where $(\varepsilon_n)_{n\geq 1}$ is a sequence monotonically
decreasing to 0 and $\gamma\approx 0.57721. . .$ is the Euler Mascheroni constant.
Actually therefore one knows there is not what would be called a    `closed form solution'  for the recurrence; but very good approximations:
$T_n=T_0+10n -5\ln n-5\gamma -5\varepsilon_n.$
