With $a_0 =1$, $a_n = 8a_{n-1} + 10^{n-1}$
Let a generating function with it, $G(x) = \sum a_k x^k$ = $a_0 + \sum (8a_{k-1} +10^{k-1}) x^k =a_0 + \sum 8a_{k-1}x^k + \sum10^{k-1} x^k = a_0 + 8x\sum a_kx^k + x\sum10^{k} x^k $
Now I think that, $\sum 10^k x^k \neq\frac{1}{1-10x}$, since it has no limitation on $x$, such as $|x|<1$ (If so, $10^nx^n$ cannot be less than 1, too).
What should I do? How can I deal with $\sum 10^k x^k$ ??
Or is it fine to do just like that?
The generating function uses formal power series. As long as there is some radius of convergence, the result will apply.
We have $$\begin{align} G(x) &= \sum_{k=0}^\infty a_k x^k \\ &= a_0 + \sum_{k=1}^\infty (8a_{k-1} + 10^{k-1})x^k \\ &= a_0 + 8x \sum_{k=0}^\infty a_k x^k + x \sum_{k=0}^\infty (10x)^k \\ &= 1 + 8x G(x) + \frac{x}{1 - 10x} \\ &= 8x G(x) + \frac{1 - 9x}{1 - 10x}. \end{align}$$
Therefore, $$G(x) = \frac{1 - 9x}{(1 - 8x)(1 - 10x)} = \frac{1}{2} \left(\frac{1}{1-8x} + \frac{1}{1-10x}\right) = \frac{1}{2} \sum_{k=0}^\infty (8^k + 10^k) x^k$$ and $$a_n = \frac{8^n + 10^n}{2}$$ and you can check that this works.
