<s>[INST] Solving recurrence relation with generating functions - Nearly got the answer I'm trying to solve the following recurrence relation (Find closed formula) using generating functions:
$f(n)=10f(n-1)-25f(n-2)$, $f(0)=0$, $f(1)=1$ 
I'm having a small difficulty at the end and can use a nudge in the right direction.
My solution
Define $$g(x)=\sum_{n=0}^{\infty}f(n)x^n = \sum_{n=2}^{\infty}f(n)x^n+x=10\sum_{n=2}^{\infty}f(n-1)x^n-25\sum_{n=2}^{\infty}f(n-2)x^n+x =$$
$$=10x\sum_{n=2}^{\infty}f(n-1)x^{n-1}-25x^2\sum_{n=2}^{\infty}f(n-2)x^{n-2}+x =$$
$$=10x\sum_{n=1}^{\infty}f(n)x^n-25x^2\sum_{n=0}^{\infty}f(n)x^n+x$$
But since the first element of $f(n)$ is $0$, then $$10x\sum_{n=1}^{\infty}f(n)x^n=10x\sum_{n=1}^{\infty}f(n)x^n+0=10x\sum_{n=0}^{\infty}f(n)x^n$$
So overall:
$$g(x)=10x\sum_{n=0}^{\infty}f(n)x^n-25x^2\sum_{n=0}^{\infty}f(n)x^n+x=10xg(x)-25x^2g(x)+x$$
To sum up:
$$g(x)=10xg(x)-25x^2g(x)+x$$
Solve for $g(x)$ and get:
$$g(x)=\frac{x}{(x-\frac{1}{5})^2}$$
But what do I do now? How can I extract $f(n)$ from this information?
 [/INST] An orderly way of attacking such problems is as follows: Define $F(z) = \sum_{n \ge 0} f(n) z^n$, write the recurrence so there are no substractions in indices:
$$
f(n + 2) = 10 f(n + 1) - 25 f(n)
$$
Multiply by $z^n$, sum over $n \ge 0$, recognize:
\begin{align}
\sum_{n \ge 0} f(n + 1) z^n &= \frac{F(z) - f(0)}{z} \\
\sum_{n \ge 0} f(n + 2) z^n &= \frac{F(z) - f(0) - f(1) z}{z^2} \\
\end{align}
to get:
$$
\frac{F(z) - z}{z^2} = 10 \frac{F(z)}{z} - 25 F(z)
$$
Maxima spits out the partial fraction expansion:
$$
F(z) = \frac{1}{5 (1 - 5 z)^2} - \frac{1}{5 (1 - 5 z)}
$$
Using the generalized binomial theorem, as $(-1)^n \binom{-2}{n} = \binom{n + 2 - 1}{1} = n + 1$:
$$
f(n) = \frac{(n + 1) 5^n}{5} - \frac{5^n}{5}
     = n 5^{n - 1}
$$
</s>