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

• I have edited Just tell if the T(n-1) is in numerator or denominator – SMath Feb 22 '14 at 7:39
• If you write the first terms, you should notice that, for any $n$, $T(n)$ is proportional to $c$. – Claude Leibovici Feb 22 '14 at 8:28
• Have a look at my answer to math.stackexchange.com/questions/684946/…, this is more-or-less the same problem. – Jack D'Aurizio Feb 22 '14 at 10:03

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

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

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