Solving the recurrence relation $T(n) = (n+1)/n*T(n-1) + c(2n-1)/n, T(1) = 0$ I tried a lot of different methods. Not able to make out the series. Could anyone help me i this regard?
$ T(n) = \frac{(n+1)}{n}T(n-1) + c\frac{(2n-1)}{n} , T(1) = 0 $
 A: $$\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$$
A: Not enough reputation for comments. Following hints from @Did,
$$
\frac{T_n}{n+1}-\frac{T_{n-1}}{n}=c \left(\frac{3}{n+1}-\frac{1}{n}\right),
$$
and hence
$$
\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}
$$
Summing them up, we have
$$
\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}
$$
where the $n^\text{th}$ harmonic number $\mathcal{H}_n=1+\frac{1}{2}+\cdots +\frac{1}{n}=\Theta(\log_e n)$. Consequently, $T_n=\Theta(n\log _e n)$.
A: As
$$
\frac{1}{n+1}T(n)-\frac 1n T(n-1)+c\left(\frac{3}{n+1}-\frac 1n\right)
$$
or
$$
\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
$$
and now calling
$$
\mathbb{T}(n) = \frac {1}{2c}\left(\frac{1}{n+1}T(n)-c\frac{3}{n+1}\right)
$$
we have the recurrence
$$
\mathbb{T}(n)-\mathbb{T}(n-1) = \frac 1n
$$
with solution
$$
\mathbb{T}(n) = \sum_{k=2}^n\frac 1k = \mathcal{H}_n -1
$$
