Best to ask by example. Given the recurrence relation $a_{n}=a_{n-1}+a_{n-2}$, and some given initial conditions, we can find a similar relation for the generating function for the sequence, $f(x)=\sum_{n=0}^\infty a_nx^n$:
$$f(x)=xf(x)+x^2f(x)+c(x)$$
Where $c(x)$ is a polynomial encoding the initial conditions. My main question is how can this polynomial be computed as painlessly as possible from the initial conditions? This is interesting not only for Fibonacci but in general, of course.
A similar, probably equivalent questions is this: If for some sequence we have a rational generating function $\frac{p(x)}{q(x)}$ then the coefficients of $q(x)$ are exactly the coefficients of the recurrence relation for the sequence. Also, $p(x)$ is dependent on the initial conditions – but again, it's not clear to me how to compute those initial conditions from $p(x)$.
Best Answer
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\;.$$