2

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 $

Rusty
  • 2,868
aditya
  • 21
  • I have edited Just tell if the T(n-1) is in numerator or denominator – Rusty Feb 22 '14 at 07: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 08:28
  • Have a look at my answer to http://math.stackexchange.com/questions/684946/how-to-find-the-limit-of-this-recurrence-relation/685000#685000, this is more-or-less the same problem. – Jack D'Aurizio Feb 22 '14 at 10:03

3 Answers3

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

Did
  • 279,727
0

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

SnzFor16Min
  • 195
0

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

Cesareo
  • 33,252