Finding Binet's formula using generating functions $\newcommand{\fib}{\operatorname{fib}}$
I am trying to solve the Fibonacci recurrence using generating functions, but I've run into a bit of a snag. Here's what I've done so far:
$$\begin{align}
&\fib(0) = 0\\
&\fib(1) = 2\\
&\fib(n) = \fib(n-1) + \fib(n-2)
\end{align}
$$
$$\begin{align}
A(x) &= \sum_{i=0}^\infty a_ix^i=\sum_{i=1}^{\infty}a_ix^i\\
&=x+\sum_{i=2}^\infty a_ix^i\\
&=x+\sum_{i=2}^\infty (a_{i-1} + a_{i-2})x^i\\
&=x+x\sum_{i=1}^\infty a_ix^i + x^2\sum_{i=0}^{\infty}a_ix^i\\
\\
A(x)&=x+xA(x)+x^2A(x)\\
\\
&=\frac{-x}{x^2+x-1}
\end{align}
$$
I then need to rearrange $A(x)$ back into the form $A(x)=\sum_{i=0}^\infty f(i)x^i$ to obtain $f(i)$, which should be Binet's closed-form equation for the $i$'th Fibonnacci number, but I don't know any techniques to do so. Is there a method for rearranging arbitrary rationals into infinite sums?
 A: Partial fractions.  $\frac{x}{1-x-x^2}$ can be written in the form $\frac{a}{1-\alpha x} + \frac{b}{1-\beta x}$, and you should recognize the sequence naturally associated to this generating function.
A: The general technique is to use partial fractions. You may not have had much experience decomposing things into slightly messy partial fractions, so I’ll go into a bit of detail.
I would write it $$A(x)=\frac{x}{1-x-x^2}\;.$$ Now factor the denominator: $1-x-x^2=(1-\alpha x)(1-\beta x)$; equating coefficients, we see that $\alpha\beta=-1$ and $\alpha+\beta=1$, so $\beta=1-\alpha$, and $\alpha(1-\alpha)=-1$, i.e., $\alpha^2-\alpha-1=0$. The quadratic formula then gives us
$$\alpha=\frac{1\pm\sqrt5}2\;,$$
so we can set $\alpha=\frac12(1+\sqrt5)$ and $\beta=\frac12(1-\sqrt5)$. Now a partial fraction decomposition of $A(x)$ is possible:
$$A(x)=\frac{x}{1-x-x^2}=\frac{A}{1-\alpha x}+\frac{B}{1-\beta x}\;,$$
so $A(1-\beta x)+B(1-\alpha x)=x$. Thus, $A+B=0$, and $-\beta A-\alpha B=1$, and you can solve for $A$ and $B$. Finally, you can easily convert each of these rational functions to an infinite series:
$$\frac{A}{1-\alpha x}=A\sum_{n\ge 0}(\alpha x)^n=A\sum_{n\ge 0}\alpha^nx^n\;,$$
for instance.
