<s>[INST] 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.
 [/INST] 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$.
</s>