Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Binet's Formula"
m
Line 13: Line 13:
 
==See Also==
 
==See Also==
 
*[[Fibonacci number]]
 
*[[Fibonacci number]]
−
{{stub}}
 
 
[[Category:Theorems]]
 
[[Category:Theorems]]

Revision as of 17:03, 4 March 2016

Binet's formula is an explicit formula used to find the $n$th term of the Fibonacci sequence. It is so named because it was derived by mathematician Jacques Philippe Marie Binet, though it was already known by Abraham de Moivre.

Formula

If $F_n$ is the $n$th Fibonacci number, then \[F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)\].

Proof

If we experiment with fairly large numbers, we see that the quotient of consecutive terms of the sequence approach $1.618\ldots$: $\frac{1}{1} = 1, \frac{2}{1} = 2, \frac{3}{2} = 1.5, \ldots, \frac{34}{21} \approx 1.617, \frac{55}{34} \approx 1.618, \ldots$. Thus we have a sequence resembling that of a geometric sequence. We let such a geometric sequence have terms $G_n = a \cdot r^n$. Then, $F_{n+1} = F_n + F_{n-1} \Longrightarrow a \cdot r^{n+1} = a \cdot r^{n} + a \cdot r^{n-1}$ $\Longrightarrow r^2 = r + 1$. Using the quadratic formula, we find $r = \frac{1 \pm \sqrt{5}}{2}$.

We now have two sequences $G_n = a \left(\frac{1 + \sqrt{5}}{2}\right)^n$ and $H_n = a \left(\frac{1 - \sqrt{5}}{2}\right)^n$, but neither match up with the Fibonacci sequence. In particular, $F_0 = 0$, but for $G_0, H_0$ to be zero, we need $a = 0$, but then the sequence just generates a constant $0$. After a bit of experimenting with these two sequences to find a sequence where the zeroth term being zero, notice that $G_{n+1} - H_{n+1} = G_{n} - H_{n} + G_{n-1} - H_{n-1}$, so $G_{n} - H_{n}$ also satisfies this recurrence. If we match up the numbers of $F_n$ and $G_n - H_n = a\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$, we note that $F_0 = G_0 - H_0 = 0$. However, $F_1 = 1 = G_1 - H_1$, which implies that $a = \frac{1}{\sqrt{5}}$. Now, $G_n - H_n$ satisfies the same recurrence as $F_n$ and has the same initial terms, so we are done.

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula&oldid=77311"