How to solve this second-order non-linear recurrence relation?

Question

Hello StackExchange community

I've been struggling to figure out a way to solve for a relation for this second-order non-linear recurrence :

nT(n) = 2(n-1)T(n-1)-(n-2)T(n-2)

I tried to solve this using the characteristic function, but the n coefficient terms become problematic. Then, I combed through several sources but couldn't find any useful info.

Any insights on how to solve this relation are greatly appreciated.

Answer 1

HINT: Notice that you have $nT(n)$, $(n-1)T(n-1)$, and $(n-2)T(n-2)$, all with the same form; this suggests letting $U(n)=nT(n)$ and rewriting the recurrence as

$$U(n)=2U(n-1)-U(n-2)\,.$$

That recurrence is straightforward, and once you’ve solved for $U(n)$ you can easily recover $T(n)=\frac{U(n)}n$.