The following is a try for a proof which is supposed to give a concrete formula for the generating function of a homogeneous linear recurrence equation (with constant coefficients).
However, when I tried applying the formula onto a concrete problem, I've ended up with results that made me pretty sure that there's something wrong with my proof.
Here it is:
Let $(g_n)_{n\in\mathbb{N}}\in \mathbb{C}^\mathbb{N}$ be a sequence and $(\alpha_1,…,\alpha_d)\in\mathbb{C}^d $ complex numbers.
Let the following inhomogeneous recurrence equation be given:
$$
a_{n+d}+\alpha_1\cdot a_{n+d-1} + \alpha_2\cdot a_{n+d-2}+…+\alpha_d\cdot a_{n} + g_{n+d}=0 , \qquad n\ge 0
$$
We're starting off with the generating functioin of $a_n$:
$$\sum_{n\geq0}{a_nx^n}=\left(\sum_{n=0}^{d-1}{a_nx^n}\right)+\left(\sum_{n\geq d}{a_nx^n}\right)=
\\
\left(\sum_{n=0}^{d-1}{a_nx^n}\right)+\left(\sum_{n\geq d}{\left(\left(\sum_{i=1}^{d}{-\alpha_ia_{n-i}}\right)-g_n\right)x^n}\right)
$$
Rearranging the summands:
$$
=\left(\sum_{n=0}^{d-1}{a_nx^n}\right)-\left(\sum_{n\geq d}{\sum_{i=1}^{d}{\alpha_ia_{n-i}}x^n}\right)-\left(\sum_{n\geq d}{g_nx^n}\right)
$$
Swapping inner and outer sum:
$$=\left(\sum_{n=0}^{d-1}{a_nx^n}\right)-\left(\sum_{i=1}^{d}{\alpha_i\sum_{n\geq d}{a_{n-i}x^n}}\right)-\left(\sum_{n\geq d}{g_nx^n}\right)
$$Index shift $n\gets n+i $ in the inner sum:
$$
=\left(\sum_{n=0}^{d-1}{a_nx^n}\right)-\left(\sum_{i=1}^{d}{\alpha_ix^i\sum_{n\geq d-i}{a_nx^n}}\right)-\left(\sum_{n\geq d}{g_nx^n}\right)
$$
We're adding a zero (by putting sum summands into the inner sum):
$$=\left(\sum_{n=0}^{d-1}{a_nx^n}\right)-\left(\sum_{i=1}^{d}{\alpha_ix^i\sum_{n\geq0}{a_nx^n}}\right)-\left(\sum_{n\geq d}{g_nx^n}\right)+\left(\sum_{i=1}^{d}{\alpha_ix^i\sum_{n\geq0}^{d-i-1}{a_nx^n}}\right)
$$
The equation now looks like this:
$$
\sum_{n\geq0}{a_nx^n}+\left(\sum_{i=1}^{d}{\alpha_ix^i\sum_{n\geq0}{a_nx^n}}\right)=\left(\sum_{n=0}^{d-1}{a_nx^n}\right)-\left(\sum_{n\geq d}{g_nx^n}\right)+\left(\sum_{i=1}^{d}{\alpha_ix^i\sum_{n\geq0}^{d-i-1}{a_nx^n}}\right)
$$
Replacing $\sum_{n\ge 0} a_n x^n $ by its generating function $f_a(x)$:
$$
f_a\left(x\right)+\left(\sum_{i=1}^{d}{\alpha_ix^if_a\left(x\right)}\right)=\left(\sum_{n=0}^{d-1}{a_nx^n}\right)-\left(\sum_{n\geq d}{g_nx^n}\right)+\left(\sum_{i=1}^{d}{\alpha_ix^i\sum_{n\geq0}^{d-i-1}{a_nx^n}}\right)
$$
Factoring $f_a(x) $ out:
$$
f_a\left(x\right)\left(1+\left(\sum_{i=1}^{d}{\alpha_ix^i}\right)\right)=\left(\sum_{n=0}^{d-1}{a_nx^n}\right)-\left(\sum_{n\geq d}{g_nx^n}\right)+\left(\sum_{i=1}^{d}{\alpha_ix^i\sum_{n=0}^{d-i-1}{a_nx^n}}\right)
$$
We arrive at the desired form:
$$
f_a\left(x\right)=\frac{\left(\sum_{n=0}^{d-1}{a_nx^n}\right)-\left(\sum_{n\geq d}{g_nx^n}\right)+\left(\sum_{i=1}^{d}{\alpha_ix^i\sum_{n=0}^{d-i-1}{a_nx^n}}\right)}
{\left(1+\left(\sum_{i=1}^{d}{\alpha_ix^i}\right)\right)}
$$
The question now is:
Where is the mistake in this calculation?
The scenario where it fails is the following:
Consider the recurrence equation
$$
f(n):= \frac{f(n-1)^3}{2f(n-2)^2}\qquad f(0)=2, f(1)=16
$$
Then we have:
$$
\log_2(f(n))= \log_2\left(\frac{f(n-1)^3}{2f(n-2)^2}\right)
\\\Leftrightarrow\\
\log_2(f(n))= 3\log_2\left(f(n-1)\right)-2\log_2\left(f(n-2)\right) -\log_2(2)
$$
By defining $a_n :=\log_2(f(n))$ we therefore arrive at an inhomogeneous lineare recurrence equation, i.e.:
$$
a_{n+2}- 3a_{n+1}+2a_{n} +1 =0
$$
We prepare for substituting into the formula:
$$
\left(\sum_{n=0}^{d-1}{a_nx^n}\right) = \log_2(2) + \log_2(16)x = 1+4x
$$
$$
\left(\sum_{n\geq d}{g_nx^n}\right) =x^2+x^3+…= \frac{x^2}{1-x}
$$
$$
\left(\sum_{i=1}^{d}{\alpha_ix^i\sum_{n=0}^{d-i-1}{a_nx^n}}\right)=-3x\cdot 2=-6x
$$
$$
{\left(1+\left(\sum_{i=1}^{d}{\alpha_ix^i}\right)\right)}= 1-3x+2x^2
$$
We therefore get:
$$
f_a\left(x\right)=\frac{\left(\sum_{n=0}^{d-1}{a_nx^n}\right)
-\left(\sum_{n\geq d}{g_nx^n}\right)
+\left(\sum_{i=1}^{d}{\alpha_ix^i\sum_{n=0}^{d-i-1}{a_nx^n}}\right)}
{\left(1+\left(\sum_{i=1}^{d}{\alpha_ix^i}\right)\right)}
$$
$$f_a(x) = \frac{1+4x-\frac{x^2}{1-x} – 6x}{1-3x+2x^2}
$$
However if I develop this using Taylor at $x=0$, I get the coefficients:
$$- 119·x^7 – 56·x^6 – 25·x^5 – 10·x^4 – 3·x^3 + x + 1$$
Which is for $a_2$ already wrong.
Best Answer
Your derivation is fine. There is just a small typo in the example. From the recurrence relation \begin{align*} a_{n+2}-3a_{n+1}+2a_n+1&=0\qquad\qquad n\geq 0\\ a_0&=1\\ a_1&=4\\ \end{align*} with generating function \begin{align*} A(x)=\color{blue}{1}+4x+9x^2+18x^3+\cdots \end{align*}
we have $a_0=\color{blue}{1}$ and we obtain as your third substitution with $d=2$ and $\alpha_1=-3$:
\begin{align*} \sum_{i=1}^{2}&{\alpha_ix^i\sum_{n=0}^{1-i}{a_nx^n}}\\ &=\alpha_1x\sum_{n=0}^0a_nx^n+\alpha_2x^2\sum_{n=0}^{-1}a_nx^n\\ &=\alpha_1xa_0\\ &=-3x\cdot \color{blue}{1}=-3x \end{align*}
Note: I've just seen, that all the relevant information was already given in the comment section. Since I've checked this problem for some time in order to find the mistake, I think I will keep the answer as well.