# Binet's Formula

## Formula

Explicit formula to find the nth term of the Fibonacci sequence.

$\displaystyle F_n = \frac{1}{\sqrt{5}} \Bigg(\Bigg( \frac{1 + \sqrt{5}}{2} \Bigg)^n - \Bigg( \frac{1 - \sqrt{5}}{2} \Bigg)^n \Bigg)$

*Derived by Jacques Philippe Marie Binet, alreday known by Abraham de Moivre*

----

## Fibonacci Sequence

The Fibonacci sequence iterates with the next value being the sum of the previous two:

$F_{n+1} = F_n + F_{n-1}$



```python
def fib(n):
    a = b = 1
    for _ in range(n):
        yield a
        a, b = b, a + b

", ".join([str(x) for x in fib(20)])
```




    '1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765'



----
## Proof

### Fibonacci Ratios
The ratios of the Fibanacci sequence

$\displaystyle \lim_{n \rightarrow \infty} \frac{F_n}{F_{n-1}} = \varphi$ <br/>

$\displaystyle \frac{F_n}{F_{n-1}}$ converges to the limit $\phi$


```python
def fib_ratio(n):
    a = b = 1
    for _ in range(n):
        yield a/b
        a, b = b, a + b

", ".join(["{0:.6f}".format(x) for x in fib_ratio(20)])
```




    '1.000000, 0.500000, 0.666667, 0.600000, 0.625000, 0.615385, 0.619048, 0.617647, 0.618182, 0.617978, 0.618056, 0.618026, 0.618037, 0.618033, 0.618034, 0.618034, 0.618034, 0.618034, 0.618034, 0.618034'



### Compose as a Geometric Sequence

This sequence resembles a geometric sequence. Geometric sequences have terms in the form of $G_n = a \cdot r^n$ .

Therefore $F_{n+1} = F_n + F_{n-1} \implies a \cdot r^{n+1} = a \cdot r^n + a \cdot r^{n-1} \implies r^2 = r + 1$.

### Resolve Quadratic
Using the Quadratic formula we find r as $1+\varphi$, or $\displaystyle\frac{1 \pm \sqrt{5}}{2}$

Let's declare $G_n = \displaystyle\frac{1 + \sqrt{5}}{2}$, and $H_n = \displaystyle\frac{1 - \sqrt{5}}{2}$



```python
# x^2−x−1=0
from sympy import *
from sympy.plotting import plot
from sympy.solvers import solve

init_printing()
x = symbols('x')
exp = x**2 - x -1

plot(exp, (x, -2, 2))

answers = solve(x**2 -x -1, x)
[ratsimp(a) for a in answers]
```

### Conclusion
Although neither $G_n$ and $H_n$ conform to the Fibonacci sequence, through induction, $G_n - H_n$ does.

To find $a$, we can see that $F_0 = G_0 - H_0 = 0, and F_1 = G_1 - H_1 = 1 \implies a = \frac{1}{\sqrt{5}}$

----
## References
- [Art of Problem Solving - Binet's Formula][3]
- [Art of Problem Solving - Geometric Sequence][2]
- [Art of Problem Solving - Fibonacci Sequence][1]

 [1]: https://artofproblemsolving.com/wiki/index.php?title=Fibonacci_sequence
 [2]: https://artofproblemsolving.com/wiki/index.php?title=Geometric_sequence
 [3]: https://artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula

6e6e90986c00390ebd9217509a085ab7b81c477e
ipynb
Jupyter Notebook
notebooks/math/number_theory/binets_formula.ipynb
sparkboom/my_jupyter_notes
9255e4236b27f0419cdd2c8a2159738d8fc383be
MIT
notebooks/math/number_theory/binets_formula.ipynb
sparkboom/my_jupyter_notes
9255e4236b27f0419cdd2c8a2159738d8fc383be
MIT
notebooks/math/number_theory/binets_formula.ipynb
sparkboom/my_jupyter_notes
9255e4236b27f0419cdd2c8a2159738d8fc383be
MIT
Qwen/Qwen-72B
1. YES
2. YES