## Explicit Fibonacci Sequence

2017 April 29

Find the formula for the nth term of the Fibonacci sequence. Find the formula for the nth iterate of the function

When iterating rational functions with linear numerator and denominator, some interesting patterns can come up, like with the function

Whose first couple iterates are

It becomes apparent very quickly that the fibonacci sequence is emerging. In fact, we can write the formula for the nth iterate as

where $F_n$ denotes the nth number of the fibonacci sequence (there are discrepancies online about where exactly the fibonacci sequence starts, but I'm letting $F_1=F_2=1$). This definition isn't a very good definition yet - it's still in terms of the numbers in the fibonacci sequence. However, there is an explicit formula for the terms of the fibonacci sequence, and its derivation goes something like this:

Notice that as $n\longrightarrow \infty$, the ratio

So that, for large $n$,

And since the ratio becomes very close, the sequence begins to behave like a geometric one. Let $\phi$ represent this ratio. Then

These are two separate ratios. We shall define them both as

Now let $G_n$ and $H_n$ be two sequences approximating $F_n$ so that

Both of these also have the same property as the fibonacci sequence; namely

If $G_1=G_2$ or $H_1=H_2$, then we could just multiply by a constant to get the explicit definition of the fibonacci sequence. However, the first two terms of $G_n$ are different, and the same applies for $H_n$.

$G_n$ is an overestimate of $F_n$ and $H_n$ is an underestimate, so perhaps $G_n-H_n$ will be a slightly better estimate. $G_n-H_n$ also has the property of the fibonacci sequence mentioned above. The first terms of $G_n-H_n$ are

Since $G_1-H_1$ and $G_2-H_2$ are the same, we can multiply by the constant $\frac{1}{\sqrt 5}$ so that we will now have a sequence $\frac{1}{\sqrt 5}(G_n-H_n)$ with the properties

This sequence has the same definition as the fibonacci sequence, so

Which is the explicit formula for the fibonacci sequence. We can now write a more exact formula for our iteration, but it will be pretty messy, so we'll skip doing that.

Perhaps this method can also be applied to similar functions whose nth iterates can be expressed in the form

where $K_n$ is another sequence defined in terms of the two previous terms.