Skip to page content Home     Posts     CV     Contact     People

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 $$f(x)=\frac{1}{x+1}$$

When iterating rational functions with linear numerator and denominator, some interesting patterns can come up, like with the function $$f(x)=\frac{1}{x+1}$$

Whose first couple iterates are $$f^2(x)=\frac{x+1}{x+2}$$ $$f^3(x)=\frac{x+2}{2x+3}$$ $$f^4(x)=\frac{2x+3}{3x+5}$$

It becomes apparent very quickly that the fibonacci sequence is emerging. In fact, we can write the formula for the nth iterate as $$f^n(x)=\frac{F_{n-1}x+F_n}{F_nx+F_{n+1}}$$

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 $$\frac{F_n}{F_{n-1}}\longrightarrow \frac{F_{n-1}}{F_{n-2}}$$

So that, for large $n$, $$\frac{F_n}{F_{n-1}}\approx \frac{F_{n-1}}{F_{n-2}}$$

And since the ratio becomes very close, the sequence begins to behave like a geometric one. Let $\phi$ represent this ratio. Then $$\frac{F_n}{F_{n-1}}\approx \phi$$ $$\frac{F_{n-1}+F_{n-2}}{F_{n-1}}\approx \phi$$ $$1+\frac{F_{n-2}}{F_{n-1}}\approx \phi$$ $$1+\frac{1}{\phi}\approx \phi$$ $$\phi^2-\phi-1\approx 0$$ $$\phi^2\approx \frac{1\pm \sqrt 5}{2}$$

These are two separate ratios. We shall define them both as $$\phi_+=\frac{1+\sqrt 5}{2}$$ $$\phi_-=\frac{1-\sqrt 5}{2}$$

Now let $G_n$ and $H_n$ be two sequences approximating $F_n$ so that $$G_n=\phi_{+}^n$$ $$H_n=\phi_{-}^n$$

Both of these also have the same property as the fibonacci sequence; namely $$G_n=G_{n-1}+G_{n-2}$$ $$H_n=H_{n-1}+H_{n-2}$$

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 $$G_1-H_1=\sqrt 5$$ $$G_2-H_2=\sqrt 5$$

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 $$\frac{1}{\sqrt 5}(G_n-H_n)=\frac{1}{\sqrt 5}(G_{n-1}-H_{n-1})+\frac{1}{\sqrt 5}(G_{n-2}-H_{n-2})$$ $$G_1-H_1=1$$ $$G_2-H_2=1$$

This sequence has the same definition as the fibonacci sequence, so $$F_n=\frac{1}{\sqrt 5}(G_n-H_n)$$ $$F_n=\frac{1}{\sqrt 5}(\phi_{+}^n-\phi_{-}^n)$$ $$F_n=\frac{1}{\sqrt 5}((\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n)$$

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 $$f^n(x)=\frac{K_{n-1}x+K_n}{K_nx-K_{n+1}}$$

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