Spivak's Calculus - Fibonacci Sequence In one of the questions in Spivak's Calculus he defines a Fibonacci sequence $a_1$, $a_2$, $a_3$ as:
$$a_1 = 1$$
$$a_2 = 1$$
$$a_n = a_{n-1} + a_{n-2}$$
for $n\ge3$
and proves $$a_n = \frac{(\frac{1+\sqrt5}{2})^n - (\frac{1-\sqrt5}{2})^n}{\sqrt{5}}$$
According to his proof:

But from his proof I don't quite understand how he got from the second line to the third and from the third to the fourth. What throws me off here is where he got the $(1+\frac{1+\sqrt5}{2})$ from and the sudden n, $(1+\frac{1-\sqrt5}{n})$ under the last fraction. For someone who understands what Spivak did, could you please explain this to me, thanks.
 A: Going from the second line to the third line, he uses that
\begin{align*}
\left(\frac{1 + \sqrt{5}}{2}\right)^2 &= \frac{1 + 2 \sqrt 5 + 5}{4} \\
&= \frac{4 + (2 + 2 \sqrt 5)}{4} \\
&= 1 + \frac{1 + \sqrt 5}{2}
\end{align*}
Going from line three to four is just using the fact that
$$a^{n - 2} a^2 = a^{n - 2 + 2} = a^n$$
A: Actually you don't need to complete that computation. In general if you have the relation:
$$
a x_{n+2} + b x_{n+1} + c x_{n} = 0
$$
you consider the associated polinomial
$$
p(\lambda) = a \lambda^2 + b \lambda + c 
$$
and consider its roots $\lambda_1$ and $\lambda_2$.
Now, notice that $x_n=\lambda^n$ satisfies the relation:
$$
a\lambda^{n+2} + b \lambda^{n+1} + c \lambda^n = \lambda^n(a\lambda^2 + b \lambda +c) = 0
$$
if $p(\lambda)=0$ i.e. if $\lambda=\lambda_1$ or $\lambda=\lambda_2$. Moreover the relation is linear. Hence since $\lambda_1^n$ and $\lambda_2^n$ are solutions, any combination like $x_n = \alpha \lambda_1^n + \beta \lambda_2^n$ is also a solution. One could also prove that these are all possible solutions.
Hence you only have to find coefficients $\alpha$ and $\beta$ so that $x_0$ and $x_1$ are the given first terms of your sequence.
