If your initial conditions are $a_0$ and $a_1$, $p(x)=c(x)=(a_1-a_0)x+a_0$. Look at it this way. You have $$a_n=a_{n-1}+a_{n-2}\tag{1}$$ for $n\ge 2$. Assume that $a_n=0$ for $n<0$. Then $(1)$ is valid for all integers $n$ except possibly $0$ and $1$. To make it valid for all integers, add a couple of terms using the Iverson bracket to get $$a_n=a_{n-1}+a_{n-2}+(a_1-a_0)[n=1]+a_0[n=0]\;.\tag{2}$$
Note that while $a_0$ is straightforward, you have to be careful for $n>0$, since the earlier initial values are automatically built into the basic recurrence.
Now multiply $(2)$ through by $x^n$ and sum:
$$\begin{align*}
\sum_na_nx^n&=\sum_na_{n-1}x^n+\sum_na_{n-2}x^n+(a_1-a_0)\sum_n[n=1]x^n+a_0\sum_n[n=0]x^n\\
&=x\sum_na_nx^n+x^2\sum_na_nx^n+(a_1-a_0)x+a_0\;.
\end{align*}$$
Thus, if your generating function is $A(x)=\displaystyle\sum_na_nx^n$, you have $$A(x)=xA(x)+x^2A(x)+(a_1-a_0)x+a_0\;,$$ and hence $$A(x)=\frac{(a_1-a_0)x+a_0}{1-x-x^2}\;.$$
This obviously generalizes to higher-order recurrences and other starting points for the initial values. For example, a third-order recurrence with initial values $a_0,a_1,a_2$ would have
$$\begin{align*}
p(x)=c(x)&=a_0+(a_1-a_0)x+\left(a_2-\big(a_0+(a_1-a_0)\big)\right)x^2\\
&=a_0+(a_1-a_0)x+(a_2-a_1)x^2\;.
\end{align*}$$
In general with initial values $a_0,\dots,a_m$ you’ll get Iverson terms
$$a_0[n=0]+(a_1-a_0)[n=1]+(a_2-a_1)[n=2]+\cdots+(a_m-a_{m-1})[n=m]$$
in the recurrence and
$$c(x)=p(x)=a_0+(a_1-a_0)x+\cdots+(a_m-a_{m-1})x^m\;.$$
You have more or less the right idea, but the right hand side is the sequence $(4n)$, not $(4)$. We have,
\begin{align*}
\sum_{n=0}^\infty 4n x^n &= \sum_{n=0}^\infty 4(n + 1)x^n - \sum_{n=0}^\infty 4x^n \\
&= \frac{\mathrm{d}}{\mathrm{d}x}\sum_{n=0}^\infty 4x^{n+1} - \sum_{n=0}^\infty 4x^n \\
&= \frac{\mathrm{d}}{\mathrm{d}x}\left(\frac{4}{1 - x} - 4\right) - \frac{4}{1 - x} \\
&= \frac{4}{(1 - x)^2} - \frac{4}{1 - x} \\
&= \frac{4x}{(1 - x)^2}.
\end{align*}
As you noted, we have
\begin{align*}
A(x) - xA(x) - 2x^2A(x) &= a_0 + (a_1 - a_0)x + (a_2 - a_1 - 2a_0)x^2 + (a_3 - a_2 - 2a_1)x^3 + \ldots \\
&= a_0 + (a_1 - a_0)x + (4 \cdot 2)x^2 + (4 \cdot 3)x^3 + \ldots + 4n x^n + \ldots \\
&= \frac{4x}{(1 - x)^2} + a_0 + (a_1 - a_0)x - 4x \\
&= \frac{4x}{(1 - x)^2} - 4 + (-5 + 4)x - 4x \\
&= \frac{4x}{(1 - x)^2} - 4 - 5x \\
&= \frac{4x - (4 + 5x)(1 - x)^2}{(1 - x)^2} \\
&= \frac{-5x^3+6x^2+7x-4}{(1 - x)^2} \\
A(x) &= \frac{-5x^3+6x^2+7x-4}{(1 - x)^2(1 - x - 2x^2)} \\
&= \frac{-5x^3+6x^2+7x-4}{(1 - x)^2(1 - 2x)(1 + x)}.
\end{align*}
Before we apply partial fractions, it's worth testing if this fraction can be simplified at all. Plugging in $x = -1$ produces $0$, meaning that $1 + x$ divides it. Dividing out $1 + x$ from the numerator and denominator,
$$A(x) = \frac{-5x^2 + 11x - 4}{(1 - x)^2(1 - 2x)}$$
Now we apply partial fractions. We wish to find $a, b, c$ such that
$$A(x) = \frac{a}{1 - x} + \frac{b}{(1 - x)^2} + \frac{c}{1 - 2x},$$
or equivalently,
$$-5x^2 + 11x - 4 = a(1 - x)(1 - 2x) + b(1 - 2x) + c(1 - x)^2.$$
Considering $x = 1$,
$$-5 \cdot 1^2 + 11 \cdot 1 - 4 = b \cdot (-1) \implies b = -2.$$
Considering $x = \frac{1}{2}$,
$$-5 \cdot \left(\frac{1}{2}\right)^2 + 11 \cdot \frac{1}{2} - 4 = c \cdot \left( \frac{1}{2}\right)^2 \cdot \implies c = 1.$$
Now, using these values of $b$ and $c$, we can find $a$ by substituting a different value for $x$, e.g. $x = 0$:
$$-4 = a + (-2) \cdot 1 + 1 \cdot 1^2 \implies a = -3.$$
That is,
$$A(x) = \frac{-3}{1 - x} + \frac{-2}{(1 - x)^2} + \frac{1}{1 - 2x}.$$
We finally convert these generating functions back to sequences:
$$a_n = -3 + (-2)(n + 1) + 2^n = -5 + 2n + 2^n,$$
as required.
Best Answer
You've used the denominator of $\frac{1+x}{1-x^2-2x^3}$ to get the recurrence: the numerator gives the initial terms. If we generalise slightly so that you can see the derivation, $$\frac{b+cx+dx^\alpha}{1-x^2-2x^3}$$ gives recurrence $$a_n=a_{n-2} + 2a_{n-3} + b[n = 0] + c[n = 1] + d[n = \alpha]$$ where $[\cdot]$ is an Iverson bracket and evaluates to $1$ when the condition inside is true and $0$ when it is false. So in your case ($b=c=1, d=0$) we have $$\begin{eqnarray}a_0 &=& a_{-2} &+& 2a_{-3} + b &=& b &=& 1 \\ a_1 &=& a_{-1} &+& 2a_{-2} + c &=& c &=& 1 \\ a_2 &=& a_{0} &+& 2a_{-1} &=& a_0 &=& 1 \end{eqnarray}$$
Why?
"$\phi_S(x)$ is the generating function for $a_i$" is another way of saying $$\phi_S(x) = \sum_{n} a_n x^n$$
If we substitute that into the given rational function, $$\sum_{n} a_n x^n = \frac{1+x}{1-x^2-2x^3}$$ we can rearrange to $$(1-x^2-2x^3)\sum_{n} a_n x^n = 1+x$$ and then to $$\sum_{n} a_n x^n = 1+x + \sum_{i} (a_i x^{i+2} + 2a_i x^{i+3})$$ Then if we apply the coefficient extraction operator $[x^n]$ to both sides, using its linearity, we get $$a_n = [x^n]1 + [x^n]x + \sum_{i} ([x^n]a_i x^{i+2} + [x^n] 2a_i x^{i+3}) \\ = [n=0] + [n=1] + \sum_{i} (a_i [n=i+2] + 2a_i [n=i+3]) \\ = [n=0] + [n=1] + a_{n-2} + 2a_{n-3}$$