3

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.

IceCreamBoi23
  • 131

2 Answers2

5

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$.

JimmyK4542
  • 54,331
0

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.$

Alexander Kovacec
  • 43