<s>[INST] Find closed formula $f(n)$ from generating function I'm asked to find a closed formula for
$f(n)=6f(n-1)-9f(n-2)$ for $n>1$ with $f(0)=-1. f(1)=0$,
using the ordinary generating function $F(X)$. 
I found $F(X)=-1/(1-3x)^2$ but from there I don't manage to get a satisfactory formula for $f(n)$. Can anyone give me a hint ?
Thanks
 [/INST] Write the recurrence as:
$$
f(n + 2) = 6 f(n + 1) - 9 f(n) \qquad f(0) = - 1, f(1) = 0
$$
Multiply by $z^n$ and 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}
and get:
$$
\frac{F(z) + 1}{z^2} = 6 \frac{F(z) + 1}{z} - 9 F(z)
$$
Solving for $F(z)$, and splitting into partial fractions:
$$
F(z) = \frac{1 - 6 z}{1 - 6 z + 9 z^2} = \frac{1}{(1 - 3 z)^2} - \frac{2}{1 - 3 z}
$$
This tells us:
$$
f(n) = \binom{-2}{n} (-1)^n 3^n - 2 \cdot 3^n
     = \left( \binom{n + 1}{1} - 2 \right) \cdot 3^n
     = \frac{n - 3}{2} \cdot 3^n
$$
</s>