Proof of $f(x) = \sum_{k=0}^\infty a_kx^k$ with $a_0 := a_1 := 1$ and $a_{n+2} := a_n+a_{n+1}$ A recursion is defined by $a_0 := a_1 := 1$ and $a_{n+2} := a_n+a_{n+1}$ for $n \geq 2$.
How can one prove that the power series
$$f(x) = \sum_{k=0}^\infty a_kx^k$$ converges absolutely for $|x| < \frac{1}{2}$ and 
$$f(x) = - \frac{1}{x^2+x-1} \text{ for } |x| < \frac{1}{2}$$
How can one conclude from what is given above that
$$a_{n-1} = \frac{1}{\sqrt{5}} \big( \big( \frac{1+\sqrt{5}}{2} \big)^n - \big ( \frac{1-\sqrt{5}}{2} \big )^n\big) \forall n \in \mathbb{N}$$
I have found this answer on another question. The problem is that it doesn't answer the $|x| < \frac{1}{2}$ part and the conclusion. 

The reciprocals of the poles of the denominator of this rational
  function are the roots of $X^2-X-1$, which are the golden ratio $\phi$
  and its "conjugate" $-\phi^{-1}$. The largest in absolute value of
  these two is $\phi$, so the coefficients $c_n$ of your series are
  asymptotically $\sim c\phi^n$ for some $c\neq0$, and the radius of
  convergence is $\frac1\phi$.
You make an interesting observation that this convergence condition is
  not equivalent to $|x+x^2|<1$. Let's see what happens when you expand
  $\sum_{i=0}^\infty (x+x^2)^i$. You get
  $1+x+2x^2+3x^3+5x^4-8x^5+\cdots$, which looks familiar; indeed it is
  $\sum_iF_{i+1}x^i$ where $F_i$ are the Fibonacci numbers (which indeed
  grow asymptotically as $\frac1{\sqrt5}\phi^n$). Now what happens if
  one sets $x=-1$, a value outside the radius of convergence, but which
  conveniently satisfies $|x+x^2|=0<1$? On one hand you have been
  expanding $\sum_{i=0}^\infty 0^i$ which should give $1$. On the other
  hand substituting $x=-1$ into the series gives $1-1+2-3+5-8+\cdots$
  which diverges. What gives? Well if you try to find your powers of
  $x+x^2$ back in the power series, you can group together parts of
  several terms so that each group of terms (except the initial $1$)
  evaluates to $0$ for $x=-1$. But in order to do so, you have been, at
  $x=-1$, grouping together terms in an absolutely divergent series, and
  that is not allowed (and may produce a convergent series). Indeed an
  easier form of this swindle is $$   \begin{align}   1-1+2-3+5-8-\cdots
> &= 1 - (0+1)+(1+1)-(1+2)+(2+3)-(3+5) \\   &=
> 1+(-1+1)+(1-1)+(-2+2)+(3-3)+(-5+\cdots \\ &=1.   \end{align} $$
Your power series is divergent at$~x=-1$ (and indeed everywhere
  outside the interval $[-\frac1\phi,\frac1\phi]$).

 A: Note that $|a_n| \le 2^k$, hence ${1 \over R} = \limsup_n \sqrt[n]{|a_n|} \le 2$.
To obtain the functional form we have $a_{n+2} = a_{n+1} + a_n$, so
$\sum_{n=0}^\infty a_{n+2} x^{n+2} = \sum_{n=0}^\infty a_{n+2} x^{n+2} + \sum_{n=0}^\infty a_{n+2} x^{n+2} $ from which we get
$f(x)-1-x = x(f(x)-1) + f(x) x^2$, and from this we get the desired form of $f$.
Let $\lambda_1 = { 1\over 2} (-1-\sqrt{5})$, $\lambda_2 = { 1\over 2} (-1+\sqrt{5})$
and note that $(x-\lambda_1)(x-\lambda_2) = x^2+x-1$ and write
$f(x) = {1\over \sqrt{5}} ({1 \over x-\lambda_2} - {1 \over x-\lambda_1})$, expand
as a series (using something like ${1 \over 1-x} = 1+x+x^2+...$) and
compare coefficients to get the $a_n$.
A: We have that $$\frac{1}{1-x-x^2}=\frac{1}{(1-\phi x)(1+\phi^{-1}x)}=\frac{a}{1-\phi x}+\frac{b}{1+\phi^{-1}x}$$
for some constants $a,b$ that are easily determined. each of these is a geometric series pf the form $$\sum_{n\ge0}p(qx)^n, $$
so adding them together and comparing coefficients to that of the generating function, we have the explicit formula. I leave the details and algebra to you.
