Binet's Formula

From AoPSWiki

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.

Personal tools

Navigation

Search

Toolbox

Binet's Formula

From AoPSWiki

Formula

Proof

See Also