The problem: Suppose we have the following recursive series
\begin{cases} a_{1}=0 & \\ a_{n+1} = 8a_{n} + 9 \cdot 10^{n-1}, & n \geq 1 \end{cases}
and we wish to find an explicit expression (formula) for $a_{n}$ using generating functions.
I stumbled upon this similiar question on this forum which is about a similiar problem to mine but is solved in some different way using quadratics? I am interested in knowing if my problem can be solved in the same way and if so how?
The following is my way of solving this problem.
Multiply both sides of the equation with $x^{n+1}$
$$a_{n+1} = 8a_{n} + 9 \cdot 10^{n-1} \implies a_{n+1}\color{red}{x^{n+1}} = 8a_{n}\color{red}{x^{n+1}} + 9 \cdot 10^{n-1}\color{red}{x^{n+1}}$$
$$\implies \sum_{n \geq 1} a_{n+1}x^{n+1}\ =\ \sum_{n \geq 1} \left(8a_{n}x^{n+1} + 9 \cdot 10^{n-1}x^{n+1}\right)$$
Split up the sums in the right side of the equation and transform the left side to have the form of an ordinary generating function $G(a_{n}; x) = \sum a_{n}x^{n}$.
$$\implies \sum_{n \geq 2} a_{n}x^{n}\ =\ \sum_{n \geq 1} 8a_{n}x^{n+1}\ +\ \sum_{n \geq 1} 9 \cdot 10^{n-1}x^{n+1}$$
Transform the left term in the right side of the equation to also have the form of an OGF and rewrite the right term so it looks like a geometric series.
$$ \implies \sum_{n \geq 2} a_{n}x^{n}\ = \ 8x\sum_{n \geq 1} a_{n}x^{n}\ +\ 9x^{2}\sum_{n \geq 1} 10^{n-1}x^{n-1} $$
$$ \implies \sum_{n \geq 1} a_{n}x^{n} - a_{1}x\ = \ 8x\sum_{n \geq 1} a_{n}x^{n}\ +\ 9x^{2}\sum_{n \geq 1} (10x)^{n-1} $$
Let $S = \sum_{n \geq 1} a_{n}x^{n}$ and keep in mind that $a_{1} = 0$.
$$\implies S = 8xS + 9x^{2} \cdot \underbrace{\frac{1}{1-10x}}_\text{formula for g.series}$$
Solve for $S$
$$\implies S - 8xS = \frac{9x^{2}}{1-10x}$$
$$\implies S = \frac{9x^2}{(1-10x)(1-8x)} \stackrel{PFD}{=} 9x^{2}\left(\frac{A}{1-10x} + \frac{B}{1-8x} \right)$$
Solving the partial fraction decomposition
$$\frac{1}{(1-10x)(1-8x)} = \frac{A}{1-10x} + \frac{B}{1-8x}$$
Multiply both sides of the equation by the denominator of the left hand side
$$1 = A(1-8x) + B(1-10x)$$
We can now solve for $A$ and $B$ by plugging in "smart" values for $x$. We start by plugging in a value for $x$ such that it makes one of the terms become 0. In this case $x=1/10$ works fine.
$$1 = A\left(1-\frac{8}{10}\right) + B\left(1-\frac{10}{10}\right) \implies 1 = A\frac{2}{10} \implies A = 5$$
Doing the same but with $x=\frac{1}{8}$ gives $B=-4$.
Notice how $\frac{5}{1-10x}$ can be written as $5\sum_{n \geq 0} (10x)^{n}$, going from the explicit expression of a geometric series to the actual original series. The same goes for $\frac{4}{1-8x}$.
$$\implies S = 9x^{2} \left(\frac{5}{1-10x} - \frac{4}{1-8x} \right) = 9x^{2}\left(5\sum_{n \geq 0} (10x)^{n} - 4\sum_{n \geq 0} (8x)^{n} \right)$$
Distribute the $9x^{2}$
$$\implies S = 45x^{2} \sum_{n \geq 0} (10x)^{n} - 36x^{2} \sum_{n \geq 0} (8x)^{n}$$
Combine the two sums in the right hand side of the equation
$$\implies \sum_{n \geq 1} a_{n}x^{n} = \sum_{n \geq 0} \left(45 \cdot 10^{n}x^{n+2} - 36 \cdot 8^{n}x^{n+2}\right)$$
Modify the right hand side expression to have the form $a_{n}x^{n}$
$$\implies \sum_{n \geq 1} a_{n}x^{n} = \sum_{n \geq 2} \left(45 \cdot 10^{n-2}x^{n} - 36 \cdot 8^{n-2}x^{n}\right)$$
Since $a_{1} = 0$
$$\implies \sum_{n \geq 1} a_{n}x^{n} = \sum_{n \geq 2} a_{n}x^{n} = \sum_{n \geq 2} \left(45 \cdot 10^{n-2} - 36 \cdot 8^{n-2}\right)x^{n}$$
Which gives us the final answer, the explicit expression for our above recursive equation.
$$a_{n} = 45 \cdot 10^{n-2} - 36 \cdot 8^{n-2}$$
Here is a classic alternative: define $b_{n}=10^{n-1}$ then we get the following recurrence relation:
$$ \begin{align} \begin{Bmatrix} a_{n+1}\\ b_{n+1} \end{Bmatrix} &= \begin{bmatrix} 8 & 9\\ 0 & 10 \end{bmatrix} \begin{Bmatrix} a_{n}\\ b_{n} \end{Bmatrix} \end{align} $$
From here it is easy to see that the explicit formula for $a_{n}$ and $b_{n}$ is the following, using eigen decomposition along the way:
$$ \begin{align} \begin{Bmatrix} a_{n}\\ b_{n} \end{Bmatrix} &= \begin{bmatrix} 8 & 9\\ 0 & 10 \end{bmatrix}^{n-1} \begin{Bmatrix} 0\\ 1 \end{Bmatrix}\\ \\ &=\frac{1}{2} \begin{bmatrix} 1 & 9\\ 0 & 2 \end{bmatrix} \begin{bmatrix} 8^{n-1} & 0\\ 0 & 10^{n-1} \end{bmatrix} \begin{bmatrix} 2 & -9\\ 0 & 1 \end{bmatrix} \begin{Bmatrix} 0\\ 1 \end{Bmatrix}\\ \\ &= \begin{Bmatrix} \frac{9}{2}\cdot\left(10^{n-1}-8^{n-1}\right)\\ 10^{n-1} \end{Bmatrix} \end{align} $$