The Fibonacci sequence is a recursive sequence, defined by
The sequence can then be written as
where is the golden ratio.
We are given this recurrence relation,
Which is subject to and . One may form an auxiliary equation in accordingly and solve for .
Through the use of the quadratic formula, one will obtain,
So we have,
where and are constants to be determined. Substituting the values we have
Solving for both variables, we obtain,
So, one has
For all integers ,
as defined above,
Therefore the proposition holds for . Assume that the proposition holds for . We may now make use of the inductive step. Let .
We know that
from the assumption that the proposition holds for .
So, we have,
Using the definition,
which obeys the proposition
As the proposition holds for , and , the proposition holds for all natural numbers.
Binet's Formula is a theorem that allows one to determine , where represents the Fibonacci Number.
The theorem is as follows:
- Fibonacci numbers are claimed to be common in nature; for example, the shell of a nautilus being a Fibonacci spiral. However, this has been disputed with the spiral having a ratio measured between 1.24 to 1.43.
- Peterson, Ivars (April 1, 2005). "Sea Shell Spirals". Science News. https://www.sciencenews.org/article/sea-shell-spirals.