Solving recurrence relation with generating functions - Nearly got the answer

Question

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?

Answer 1

Hint: The binomial theorem says $$ \begin{align} (1-x)^{-2} &=\sum_{k=0}^\infty\binom{-2}{k}(-x)^k\\ &=\sum_{k=0}^\infty\binom{k+1}{k}x^k\\ &=\sum_{k=0}^\infty(k+1)x^k\\ \end{align} $$ and $$ \frac{x}{(x-\frac15)^2}=\frac{25x}{(1-5x)^2} $$

Answer 2

Hint: The Taylor series for $g(x)$ is $\sum_{n=0}^{\infty}{g^{(n)}(0)x^{n}/n!}$ so we get that $f(n) = g^{(n)}(0)/n!$