Viết lại công thức truy hồi $U_n=3U_{n-1}+(n-1)^2+1=3U_{n-1}+n^2-2n+2$Mà $n^2-2n+2=\frac{-1}{2}n^2-\frac{1}{2}n-1+\frac{3}{2}(n-1)^2+\frac{3}{2}(n-1)+3$
$\Rightarrow U_n+\frac{1}{2}n^2+\frac{1}{2}n+1=3(U_{n-1}+\frac{1}{2}(n-1)^2+\frac{1}{2}(n-1)+1)$
$\Rightarrow V_n=3V_{n-1}=3^{n-1}.V_1=4.3^{n-1}$
$\Rightarrow U_n=4.3^{n-1}-\frac{n^2+n}{2}-1$