<s>[INST] Recurrence relation $a_n = 11a_{n-1} - 40a_{n-2} + 48a_{n-3} + n2^n$ I didn't do a lot of maths in my career, and we asked me to solve the following recurrence relation:
$$a_{n} = 11a_{n-1} - 40a_{n-2} + 48a_{n-3} + n2^n$$
with 
$a_0 = 2$, $a_1 = 3$ and $a_2 = 1$
What is the procedure to solve such relation? So far, I just know that $a_n$ could be split into two difference recurrence relations (homogeneous and non-homogeneous) as $a_n = b_n + c_n$, where 
$$b_n = 11b_{n-1} - 40b_{n-2} + 48b_{n-3}$$
and 
$$c_n = n2^n$$
 [/INST] The general way of solving this kind of problem is to define relation $G(n)$ as
$$G(n) = (a_n - 11a_{n - 1} + 40a_{n - 2} - 48a_{n - 3} = n2^n)$$
Then write out:
$$\begin{array} {rrl}
G(n) = &(a_n + \dots &= n2^n) \\
G(n + 1) = &(a_{n + 1} + \dots &= 2n2^n + 2 \cdot 2^n) \\
G(n + 2) = &(a_{n + 2} + \dots &= 4 n 2^n + 8 \cdot 2^n) \\
\end{array}$$
until you have more equations than nonlinear terms per equation.  Then let variables replace the nonlinear terms, $u = n2^n$ and $v = 2^n$ to get:
$$\begin{align}
a_n + \dots &= u \\
a_{n + 1} + \dots &= 2u + 2v \\
a_{n + 2} + \dots &= 4u + 8v \\
\end{align}$$
2 variables, 3 equations, so you can eliminate $u$ and $v$ and you get:
$$a_{n+2} - 15 a_{n+1} + 88 a_{n} - 252 a_{n-1} + 352 a_{n-2} - 192 a_{n-3}=0 \tag{T}$$
And that is just a regular linear recursion.  Note that if the characteristic polynomial of the linear part of $G(n)$ is $g'$, and the characteristic polynomial of (T) is $t'$, then $g'$ is polynomial factor of $t'$.  So 3 roots of $t'$ are known and you only need to find the remaining $2$ if you wish to continue in the standard fashion.
In this case, the roots of $g'$ are $\{4, 4, 3\}$ so the roots of $t'$ are $\{4, 4, 3, 2, 2\}$, so the final equation is $a_n = (An + B)4^n + (Cn + D)2^n + E3^n$ based on whatever the initial conditions are.
</s>