Solving Recursion With Characteristic Polynomial Say a linear recursion has the form: $a_n=a_{n-1}+a_{n-2}+2^{n-2}$, I know it would be possible to solve it with $a_n=a_{n-1}+a_{n-2}$ and $a_n=2^{n-2}$ and then combine the two using some coefficient A, B.
However, is there any proof to this will always work for linear recursions? (to separate and then combine it) I have seen this method being using a few times on math exchange.

This is very similar to the way you solve linear differential equations with constant coefficients, and for a good reason... We can identify a basis for the space of solutions, which depends on the roots of the polynomial characteristic.
In this case, the characteristic polynomial is $p(\lambda) = \lambda^2 -\lambda -1$ and the solution can be written as $a_n = h_n + p_n$, where $h_n$ is the general solution of the homogeneous equation $h_n = h_{n-1} + h_{n-2}$ and $p_n$ is a particular solution of our equation.
The roots of the characteristic polynomial are $\lambda = \frac{1 \pm \sqrt{5}}{2}$ and so we have that
$$
h_n = c_1 \left( \frac{1-\sqrt{5}}{2}\right)^n+ c_2 \left( \frac{1+\sqrt{5}}{2}\right)^n
$$
Regarding the particular solution, one usual option is to try something "similar" to the RHS, in this case we can try $p_n= c 2^{n}$. If we plug that into the equation, we can see that $p_n = 2^{n}$ is a solution to the equation.
Finally, the general solution to our equation is given by
$$
a_ n = 2^{n}  +c_1 \left( \frac{1-\sqrt{5}}{2}\right)^n+ c_2 \left( \frac{1+\sqrt{5}}{2}\right)^n
$$.
