*2017 April 29*

Find the formula for the

nth term of the Fibonacci sequence.

Find the formula for thenth 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 *n*th iterate as

\[f^n(x)=\frac{F_{n-1}x+F_n}{F_nx+F_{n+1}}\]

where \(F_n\) denotes the *n*th 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 *n*th 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.