# Solving recurrence relation with non-constant coefficient.

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

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

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

• Thanks a lot! @peterwhy – Vaibhav Agarwal Dec 8 '19 at 13:39
• 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 – Vaibhav Agarwal Dec 8 '19 at 13:47
• @VaibhavAgarwal Is that another question and another recurrence to solve? Please post another question or add to this question above. – peterwhy Dec 8 '19 at 13:52
• Updated the question – Vaibhav Agarwal Dec 8 '19 at 13:55
• @VaibhavAgarwal Updated the answer – peterwhy Dec 8 '19 at 14:48