Resolver la relación de recurrencia $T(n) = (n+1)/n*T(n-1) + c(2n-1)/n, T(1) = 0$

Question

He probado muchos métodos diferentes. No se puede distinguir la serie. ¿Podría alguien ayudarme en este sentido?

$ T(n) = \frac{(n+1)}{n}T(n-1) + c\frac{(2n-1)}{n} , T(1) = 0 $

Answer 1

$$\frac{T(n)}{n+1}=\frac{T(n-1)}{n}+c\frac{2n-1}{n(n+1)}=\frac{T(n-1)}{n}+\frac{3c}{n+1}-\frac{c}n$$

Answer 2

No hay suficiente reputación para los comentarios. Siguiendo las indicaciones de @Did,

$$ \frac{T_n}{n+1}-\frac{T_{n-1}}{n}=c \left(\frac{3}{n+1}-\frac{1}{n}\right), $$

y por lo tanto

$$ \begin{align} \frac{T_{n-1}}{n}-\frac{T_{n-2}}{n-1}&=c \left(\frac{3}{n}-\frac{1}{n-1}\right),\\ &\vdots\\ \frac{T_3}{4}-\frac{T_2}{3}&=c \left(\frac{3}{4}-\frac{1}{3}\right),\\ \frac{T_2}{3}-\frac{T_1}{2}&=c \left(\frac{3}{3}-\frac{1}{2}\right). \end{align} $$

Resumiendo, tenemos

$$ \begin{align} &\frac{T_n}{n+1}-\frac{T_1}{2}&=&c \left(3 \sum _{k=3}^{n+1} \frac{1}{k}-\sum _{k=2}^n \frac{1}{k}\right)\\ \Rightarrow &\frac{T_n}{n+1}&=&c \left(3 \left(\mathcal{H}_{n+1}-\frac{1}{2}-1\right)-\left(\mathcal{H}_n-1\right)\right)\\ &&=&c \left(2 \mathcal{H}_n+\frac{3}{n+1}-\frac{7}{2}\right)\\ \Rightarrow &T_n&=&c \left(2 (n+1) \mathcal{H}_n-\frac{7}{2} n-\frac{1}{2}\right),\\ \end{align} $$

donde el $n^\text{th}$ número armónico $\mathcal{H}_n=1+\frac{1}{2}+\cdots +\frac{1}{n}=\Theta(\log_e n)$ . En consecuencia, $T_n=\Theta(n\log _e n)$ .

Answer 3

Como

$$ \frac{1}{n+1}T(n)-\frac 1n T(n-1)+c\left(\frac{3}{n+1}-\frac 1n\right) $$

o

$$ \frac {1}{2c}\left(\frac{1}{n+1}T(n)-c\frac{3}{n+1}\right)-\frac {1}{2c}\left(\frac 1n T(n-1)-c\frac 3n\right)=\frac 1n $$

y ahora llamando a

$$ \mathbb{T}(n) = \frac {1}{2c}\left(\frac{1}{n+1}T(n)-c\frac{3}{n+1}\right) $$

tenemos la recurrencia

$$ \mathbb{T}(n)-\mathbb{T}(n-1) = \frac 1n $$

con solución

$$ \mathbb{T}(n) = \sum_{k=2}^n\frac 1k = \mathcal{H}_n -1 $$