<s>[INST] Solving linear recurrence relation Solve the following linear recurrence relation:
$$h_n=4h_{n-1}-4h_{n-2}+n^2 2^n$$
for $n\geq2$ and $h_0=h_1=1$
 [/INST] $$h_n - 2h_{n-1} = 2(h_{n-1} - 2h_{n-2}) + n^2 \cdot 2^n$$
Let $h_n - 2h_{n-1} = f_n$. We then have
$$f_n = 2f_{n-1} + n^2 \cdot 2^n = 2(2f_{n-2} + (n-1)^2 \cdot 2^{n-1}) + n^2 \cdot 2^n = 4 f_{n-2} + 2^n \cdot (n^2 + (n-1)^2)$$
Hence, by induction, we have
$$f_n = 2^n \cdot (n^2 + (n-1)^2 + \cdots + 2^2 + 1^2) + 2^n \cdot f_0 = 2^n \cdot \left( f_0 + \dfrac{n(n+1)(2n+1)}6\right)$$
Hence,
\begin{align}
h_n & = 2h_{n-1} + 2^n \cdot \left( c + \dfrac{n(n+1)(2n+1)}6\right)\\
& = 4h_{n-2} + 2^n \cdot \left(2c + \dfrac{n(n+1)(2n+1) + (n-1)n(2n-1)}6\right)\\
& = 2^n \cdot h_{0} + 2^n \cdot \left(nc + \dfrac{\displaystyle \sum_{k=1}^n k(k+1)(2k+1)}6\right)
\end{align}
Hence,
$$h_n = 2^n \left(an^4+bn^3+cn^2+dn+e\right)$$
where the $a,b,c,d$ and $e$ can be obtained using the recurrence in terms of the initial values $h_0$ and $h_1$.
</s>