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
(→‎Proof)
Line 7: Line 7:
  
 
==Proof==
 
==Proof==
−
If we experiment with fairly large numbers, we see that the quotient of consecutive terms of the sequence approach <math>1.618\ldots</math>: <math>\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</math>. Thus we have a sequence resembling that of a [[geometric sequence]]. We let such a geometric sequence have terms <math>G_n = a \cdot r^n</math>. Then, <math>F_{n+1} = F_n + F_{n-1} \Longrightarrow a \cdot r^{n+1} = a \cdot r^{n} + a \cdot r^{n-1} </math> <math>\Longrightarrow r^2 = r + 1</math>. Using the [[quadratic formula]], we find <math>r = \frac{1 \pm \sqrt{5}}{2}</math>.
+
If we experiment with fairly large numbers, we see that the quotient of consecutive terms of the sequence approach <math>1.618\ldots</math>: <math>\frac{1}{1} = 1, \frac{2}{1} = 2, \frac{3}{2} = 1.5, \ldots, \frac{34}{21} \approx 1.61904761905, \frac{55}{34} \approx 1.61764705882, \ldots</math>. Thus we have a sequence resembling that of a [[geometric sequence]]. We let such a geometric sequence have terms <math>G_n = a \cdot r^n</math>. Then, <math>F_{n+1} = F_n + F_{n-1} \Longrightarrow a \cdot r^{n+1} = a \cdot r^{n} + a \cdot r^{n-1} </math> <math>\Longrightarrow r^2 = r + 1</math>. Using the [[quadratic formula]], we find <math>r = \frac{1 \pm \sqrt{5}}{2}</math>.
  
 
We now have two sequences <math>G_n = a \left(\frac{1 + \sqrt{5}}{2}\right)^n</math> and <math>H_n = a \left(\frac{1 - \sqrt{5}}{2}\right)^n</math>, but neither match up with the Fibonacci sequence. In particular, <math>F_0 = 0</math>, but for <math>G_0, H_0</math> to be zero, we need <math>a = 0</math>, but then the sequence just generates a constant <math>0</math>. After a bit of experimenting with these two sequences to find a sequence where the zeroth term being zero, notice that <math>G_{n+1} - H_{n+1} = G_{n} - H_{n} + G_{n-1} - H_{n-1}</math>, so <math>G_{n} - H_{n}</math> also satisfies this recurrence. If we match up the numbers of <math>F_n</math> and <math>G_n - H_n = a\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)</math>, we note that <math>F_0 = G_0 - H_0 = 0</math>. However, <math>F_1 = 1 = G_1 - H_1</math>, which implies that <math>a = \frac{1}{\sqrt{5}}</math>. Now, <math>G_n - H_n</math> satisfies the same recurrence as <math>F_n</math> and has the same initial terms, so we are done.
 
We now have two sequences <math>G_n = a \left(\frac{1 + \sqrt{5}}{2}\right)^n</math> and <math>H_n = a \left(\frac{1 - \sqrt{5}}{2}\right)^n</math>, but neither match up with the Fibonacci sequence. In particular, <math>F_0 = 0</math>, but for <math>G_0, H_0</math> to be zero, we need <math>a = 0</math>, but then the sequence just generates a constant <math>0</math>. After a bit of experimenting with these two sequences to find a sequence where the zeroth term being zero, notice that <math>G_{n+1} - H_{n+1} = G_{n} - H_{n} + G_{n-1} - H_{n-1}</math>, so <math>G_{n} - H_{n}</math> also satisfies this recurrence. If we match up the numbers of <math>F_n</math> and <math>G_n - H_n = a\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)</math>, we note that <math>F_0 = G_0 - H_0 = 0</math>. However, <math>F_1 = 1 = G_1 - H_1</math>, which implies that <math>a = \frac{1}{\sqrt{5}}</math>. Now, <math>G_n - H_n</math> satisfies the same recurrence as <math>F_n</math> and has the same initial terms, so we are done.

Revision as of 21:08, 3 February 2018

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.61904761905, \frac{55}{34} \approx 1.61764705882, \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=90201"