Are you familiar with differential equations? Solving linear recurrences is the same as solving linear differential equations, essentially. Linear recurrences (ie., difference equations) are discrete differential equations.
So for $a_{n} = 4a_{n-1} - 3a_{n-2}$, we start by setting up our characteristic polynomial: $\lambda^{2} - 4\lambda + 3 = 0$. You then solve for $\lambda$, getting solutions $\lambda = 1, 3$. And so your general form equation $a_{n} = c_{1}(\lambda_{1})^{n} + c_{2}(\lambda_{2})^{n}$.
To set up the characteristic polynomial, you look at the difference of the indices. So for $a_{n}$, we see indices $n, n-1, n-2$. Clearly there is a difference of two between the largest and smallest index. So we have a quadratic. The largest indexed term has the largest power. So $a_{n} \to \lambda^{2}$, $4a_{n-1} \to 4\lambda$, and $-3a_{n-2} \to -3$. Do you see how I got that?
So $a_{n} = c_{1} + c_{2}3^{n}$. Then plug in your constraints and solve for $c_{1}$ and $c_{2}$.
Now for your example with Fibonacci, we have $a_{n} = a_{n-1} + a_{n-2}$, we have another quadratic. Do you see why? So $a_{n} \to \lambda^{2}$, $a_{n-1} \to \lambda$, $a_{n-2} \to 1$. And so our characteristic polynomial is $\lambda^{2} - \lambda - 1 = 0$. Solve for $\lambda$, which gives you two distinct roots $\lambda_{1}, \lambda_{2}$, then plug in: $a_{n} = c_{1} \lambda_{1}^{n} + c_{2}\lambda_{2}^{n}$ and solve the system of equations from your initial conditions.
Now for a first order non-homogenous recurrence of the form $a_{n} = ra_{n-1} + c$, we get a solution of the form $a_{n} = kr^{n} + c \frac{r^{n}-1}{r -1 }$ for $r \neq 1$. If $r = 1$, we get $a_{n} = k + cn$.
The constant $k$ is what we solve for based on the initial conditions.
You made a mistake somewhere in the generating function derivation (hard to tell where since you did not include this part), I've got
\begin{align}
A(x)&=2x+5x^2+\sum_{n \geq 3}a_{n}x^n\\
&=2x+5x^2+5\sum_{n \geq 3}a_{n-1}x^n-7\sum_{n \geq 3}a_{n-2}x^n+3\sum_{n \geq 3}a_{n-3}x^n+\sum_{n \geq 3}2^{n-3}x^n\\
&=2x+5x^2+5x\sum_{n \geq 2}a_{n}x^n-7x^2\sum_{n \geq 1}a_{n}x^n+3x^3\sum_{n \geq 0}a_{n}x^n+x^3\sum_{n \geq 0}2^{n}x^n\\
&=2x+5x^2+5x(A(x)-2x)-7x^2(A(x)-0)+3x^3A(x)+x^3\cdot \frac{1}{1-2x}
\end{align}
which solves to
\begin{align}
A(x)&=\frac{x(11x^2-9x+2)}{(1-2x)(1-3x)(x-1)^2}\\
&=\frac{2}{(x-1)^2}-\frac{3}{2}\frac{1}{1-x}-\frac{1}{1-2x}+\frac{1}{2}\frac{1}{1-3x}.
\end{align}
Check your solution, hopefully you can finish it from here.
Best Answer
Choosing conveniently the sum limits we have
$$ \frac 1x\left(G(x)-r_0\right)-2G(x) + x\left(G(x)-r_w x^w\right) = 0 $$
or
$$ G(x) = \frac{r_w x^{w+2}+r_0}{1-2x+x^2} $$
NOTE
$$ \sum_{k=0}^w\left(\frac 1x r_{k+1} x^{k+1}-2r_k x^k+x r_{k-1}x^{k-1}\right)=0 $$
NOTE
Considering $w = 5, r_0 = 0, r_5= 1$ we have
$$ \frac{x^7}{1-2x+x^2} = x^5+2x^4+3x^3+4x^2+5x+\cdots $$
so we have
$$ r_4 = 2, r_3 = 3, r_2 = 4, r_1 = 5 $$
and as we can easily verify, they obey the recurrence
$$ r_{k+1}-2r_k+r_{k-1} = 0 $$