0
$\begingroup$

I am facing difficulty in solving this recurrence relation having non constant coefficients. Kindly help

$nT(n) = (2n - 2)T(n - 1) + \log_2 (n/(n-1)^2) , \space\space T(1) = 2$.

EDIT: $(n^2) T(n) = (n - 1)(n - 2)T(n-1) + 3, T(1) = 0$. I was having difficulty solving this recurrence, could you please guide me on how to solve this. Help will be much appreciated

$\endgroup$
  • $\begingroup$ Let $S(n) = nT(n) - \log_2 n$ $\endgroup$ – peterwhy Dec 8 '19 at 13:30
  • $\begingroup$ Great.Thanks :) $\endgroup$ – Vaibhav Agarwal Dec 8 '19 at 13:35
1
$\begingroup$

Let $S(n) = n T(n) - \log_2 n$, then

$$\begin{align*} S(n) &= nT(n) - \log_2 n\\ &= (2n-2)T(n-1)+\log_2\frac{n}{(n-1)^2} - \log_2n\\ &= 2(n-1)T(n-1) -2\log_2(n-1)\\ &= 2S(n-1)\\ &= 2^2S(n-2)\\ &= \vdots\\ &= 2^{n-1}S(1)\\ &= 2^{n-1}\left[1T(1) - \log_2 1\right]\\ &= 2^n\\ T(n) &= \frac{S(n) +\log_2 n}n\\ &= \frac{2^n+\log_2n}{n} \end{align*}$$


For the second recurrence, let $S(n) = n^2(n-1) T(n)$, then

$$\begin{align*} S(n) &= (n-1)^2(n-2)T(n-1)+3(n-1)\\ &= S(n-1) + 3(n-1)\\ &= S(n-2) + 3(n-2) + 3(n-1)\\ &= \vdots\\ &= S(n-k) + 3 \sum_{i= n-k}^{n-1}i\\ &= S(1)+ 3\sum_{i=1}^{n-1}i && (k = n-1)\\ &= 1^2\cdot 0 T(1) + 3\cdot \frac{(n-1)n}2\\ &= \frac{3(n-1)n}{2} \end{align*}$$

For $n\ge 2$, $$T(n) = \frac{S(n)}{n^2(n-1)} = \frac{3}{2n}$$

And as given, when $n=1$, $$T(n) = T(1) = 0$$

$\endgroup$
  • $\begingroup$ Thanks a lot! @peterwhy $\endgroup$ – Vaibhav Agarwal Dec 8 '19 at 13:39
  • $\begingroup$ Could you guide me on how should I go on about solving this one, (n^2) T(n) = (n - 1)(n - 2)T(n-1) + 3, T(1) = 0. I was having difficulty, since I am new to recurrence relations. Help will be much appreciated $\endgroup$ – Vaibhav Agarwal Dec 8 '19 at 13:47
  • $\begingroup$ @VaibhavAgarwal Is that another question and another recurrence to solve? Please post another question or add to this question above. $\endgroup$ – peterwhy Dec 8 '19 at 13:52
  • $\begingroup$ Updated the question $\endgroup$ – Vaibhav Agarwal Dec 8 '19 at 13:55
  • $\begingroup$ @VaibhavAgarwal Updated the answer $\endgroup$ – peterwhy Dec 8 '19 at 14:48

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.