Hi there I am trying to solve the following recurrence relation using telescoping. How would I go about doing it?
$T(n) = \frac 2n \Big(T(0) + T(1) + \ldots+ T(n-1)\Big) + 5n$
Assuming $n\ge 1$
Hi there I am trying to solve the following recurrence relation using telescoping. How would I go about doing it?
$T(n) = \frac 2n \Big(T(0) + T(1) + \ldots+ T(n-1)\Big) + 5n$
Assuming $n\ge 1$
Rearrange $T(n) = \frac 2n \Big(T(0) + T(1) + \ldots+ T(n-1)\Big) + 5n\tag{1}$ to get
$T(0)+T(1)+\ldots+T(n-1)=\frac12\Big(nT(n)-5n^2\Big)\;,$ and hence $T(0)+T(1)+\ldots+T(n-2)=\frac12\Big((n-1)T(n-1)-5(n-1)^2\Big)\;.$
Then substitute this into $(1)$:
$\begin{align*} T(n)&=\frac2n\left(\frac12\left((n-1)T(n-1)-5(n-1)^2\right)+T(n-1)\right)+5n\\ &=\frac{n-1}nT(n-1)-\frac{5(n-1)^2}n+\frac2nT(n-1)+5n\\ &=\frac{n+1}nT(n-1)-\frac5n(n^2-2n+1)+5n\\ &=\frac{n+1}nT(n-1)+10-\frac5n\;.\tag{2} \end{align*}$
Now let $a=T(0)$, and calculate a few values of $T$:
$\begin{array}{c|l} n&T(n)\\ \hline 0&a\\ 1&2a+5\\ 2&3a+15\\ 3&4a+\frac{85}3\\ 4&5a+\frac{265}6\\ 5&6a+62 \end{array}$
This suggests that $T(n)=c_na+b_n$, where $c_n$ is probably $n+1$. Indeed, if $T(n-1)=na+b_{n-1}\;,$ then from $(2)$ we find that
$\begin{align*} T(n)&=(n+1)a+\left(1+\frac1n\right)b_{n-1}+10-\frac5n\\ &=(n+1)a+b_{n-1}+10+\frac1n(b_{n-1}-5)\;, \end{align*}$
confirming that $c_n=n+1$. Thus, the problem reduces to solving the recurrence $b_n=b_{n-1}+10+\frac1n(b_{n-1}-5)$ with initial condition $b_0=0$.
It appears to be convenient to let $u_n=b_n-5$, so that $u_0=-5$, and
$u_n=u_{n-1}+10+\frac1nu_{n-1}=\frac{n+1}nu_{n-1}+10\;.$ Then
$\begin{align*} u_n&=\frac{n+1}nu_{n-1}+10\\ &=\frac{n+1}n\left(\frac{n}{n-1}u_{n-2}+10\right)+10\\ &=\frac{n+1}{n-1}u_{n-2}+10\left(1+\frac{n+1}n\right)\\ &=\frac{n+1}{n-1}\left(\frac{n-1}{n-2}u_{n-3}+10\right)+10\left(1+\frac{n+1}n\right)\\ &=\frac{n+1}{n-2}u_{n-3}+10\left(1+\frac{n+1}n+\frac{n+1}{n-1}\right)\\ &\qquad\qquad\qquad\vdots\\ &=(n+1)u_0+10\left(\frac{n+1}{n+1}+\frac{n+1}n+\frac{n+1}{n-1}+\ldots+\frac{n+1}2\right)\\ &=-5(n+1)+10(n+1)(H_{n+1}-1)\\ &=-5-5n+10(n+1)(H_{n+1}-1)\;, \end{align*}$
where $H_n$ is the $n$-th harmonic number. (Properly speaking, this should now be proved by induction on $n$.)
Finally, then, $b_n=u_n+5=10(n+1)(H_{n+1}-1)-5n$, and
$\begin{align*} T(n)&=(n+1)\Big(T(0)+10(H_{n+1}-1)\Big)-5n\\ &=(n+1)\Big(T(0)+10H_{n+1}\Big)-10(n+1)-5n\\ &=(n+1)\Big(T(0)+10H_{n+1}\Big)-15n-10\;. \end{align*}$