$n^{2}T(n)=(n-1)(n-2)T(n-1)+3$ with initial condition $T(1) = 1$

Question

I find that the above nonlinear recurrence could be written as the following $n^{2}T(n)=(n-1)^{2}T(n-1)-(n-1)T(n-1)+3$. Then, I let $\alpha(n) = nT(n-1)$. However, I am stuck here. I don't know how to solve it. Hope that someone could give me some hint about it.

Answer 1

I think you made a type, however defining $\alpha(n) := n T(n)$ leads to the following expression: $$ n \alpha(n) = (n-2)\alpha(n-1) + 3. $$ We know that $\alpha(1) = 1$, then from this we get $\alpha(2) = 3/2$ and we notice that it is true for all $n \ge 2$. To prove this we use induction.

Assume it is true for $n - 1$, i.e. $\alpha(n - 1) = 3/2$ then $$ n \alpha(n) = (n - 2) \cdot 3/2 + 3 = n \cdot 3/2 \implies \alpha(n) = 3/2, $$ concluding the proof by induction. Hence, $\alpha(n) = 3/2$ for all $n \ge 2$.

Finally, $T(n) = \frac{3}{2n} ~ \forall n \ge 2.$