2
$\begingroup$

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 $

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

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.