I need to derive Binet's formula and I don't know how to start.
You should really start by telling us what tools you have to work with.
Either way, you should try Wikipedia first: Fibonacci number - Wikipedia, the free encyclopedia.
Thank you. Part of my problem is that the tools haven't really been defined. I am in a Combinatorics class and all I was told was to derive the formula. Actually, I have seen a version of the derivation that seeks a solution of the form f_n =q^n, q <> 0, but I am not sure what lead the writer to this approach. It seems to me that whatever prompted that approach is key to the whole thing. The rest of the steps are just algebra.
Hello, tarheelborn!
If you've never seen a derivation for a recursive functions,
. . these moves will seem like Black Magic.
I need to derive Binet's formula and I don't know how to start.
The Fibonacci Sequence $\displaystyle 1,1,2,3,5,8,\:\hdots$ can be expressed like this:
. . $\displaystyle f(n\!+\!1) \:=\:f(n) + f(n\!-\!1),\;\;f(1) = 1,\;f(2)=1$
The sequence begins with 1 and 1; each subsequent term is the sum of the preceding two terms.
We assume that $\displaystyle f(n)$ is an exponential function: .$\displaystyle f(n) \,=\,X^n$
The equation $\displaystyle f(n\!+\!1) \:=\:f(n) + f(n\!-\!1)$ becomes:
. . $\displaystyle X^{n+1} \:=\:X^n + X^{n-1} \quad\Rightarrow\quad X^{n+1} - X^n - X^{n-1} \:=\:0 $
Divide by $\displaystyle X^{n-1}\!:\;\;X^2 - X - 1 \:=\:0$
Quadratic Formula: .$\displaystyle X \;=\;\dfrac{1\pm\sqrt{5}}{2}$
Form a linear combination of the roots:
. . $\displaystyle f(n) \;=\;A\left(\dfrac{1+\sqrt{5}}{2}\right)^n + B\left(\dfrac{1-\sqrt{5}}{2}\right)^n $
Use the first two terms of the sequence:
. . $\displaystyle \begin{array}{cccccccc}f(1) = 1\!: & A\left(\frac{1+\sqrt{5}}{2}\right) + B\left(\frac{1-\sqrt{5}}{2}\right) & = & 1 \\ \\[-3mm]
f(2) = 1\!: & A\left(\frac{1+\sqrt{5}}{2}\right)^2 + B\left(\frac{1-\sqrt{5}}{2}\right)^2 &=& 1 \end{array}$
Solve the system of equations: .$\displaystyle A \,=\,\dfrac{1}{\sqrt{5}},\;\;B \,=\,-\dfrac{1}{\sqrt{5}}$
Hence: .$\displaystyle f(n) \;=\;\dfrac{1}{\sqrt{5}}\left(\dfrac{1+\sqrt{5}}{2 }\right)^n - \dfrac{1}{\sqrt{5}}\left(\dfrac{1-\sqrt{5}}{2}\right)^n $
. . . . . .$\displaystyle f(n) \;=\;\dfrac{(1+\sqrt{5})^n - (1 - \sqrt{5})^n}{2^n\sqrt{5}} $