Relación de recurrencia telescópico

Question

Hola hay estoy tratando de resolver las siguientes relaciones de recurrencia usando telescópico. ¿Cómo puedo hacerlo?

$$T(n) = \frac 2n \Big(T(0) + T(1) + \ldots+ T(n-1)\Big) + 5n$$

Suponiendo que $n\ge 1$

Answer 1

Reorganizar $$T(n) = \frac 2n \Big(T(0) + T(1) + \ldots+ T(n-1)\Big) + 5n\tag{1}$$ a conseguir

$$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)\;.$$

A continuación, sustituir esto en $(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*}$$

Ahora vamos a $a=T(0)$, y calcular algunos valores de $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}$$

Esto sugiere que la $T(n)=c_na+b_n$ donde $c_n$ es, probablemente,$n+1$. De hecho, si $$T(n-1)=na+b_{n-1}\;,$$ then from $(2)$ nos encontramos con que

$$\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*}$$

confirmando que $c_n=n+1$. Por lo tanto, el problema se reduce a la solución de la recurrencia $$b_n=b_{n-1}+10+\frac1n(b_{n-1}-5)$$ with initial condition $b_0=0$.

Parece ser conveniente dejar a $u_n=b_n-5$, por lo que el $u_0=-5$, y

$$u_n=u_{n-1}+10+\frac1nu_{n-1}=\frac{n+1}nu_{n-1}+10\;.$$

$$\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*}$$

donde $H_n$ $n$- ésimo número armónico. (Propiamente hablando, este debe ahora ser demostrado por inducción en $n$.)

Finalmente, entonces, $b_n=u_n+5=10(n+1)(H_{n+1}-1)-5n$, y

$$\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*}$$