Fibonacci Numbers and Continued Fractions

I feel I needed an updated post on the Fibonacci sequence with some of the more core ideas behind it, you can still access the old post.

The definition of the Fibonacci sequence is:

$\begin{align}F_{n+2}=F_{n+1}=F_n\ where\ F_0=1,\ F_1=1\end{align}$

You can see quickly that the first few values of the sequence are 1, 1, 2, 3, 5, 8, 13, ..., etc. this is a weakly increasing sequence, that is ${F}_{n+1}\ge F_n \forall\ n \ge 1$.

This clearly means that the sequence does not tend towards a limit, but does the ratio between terms tend towards a limit?

Consider that the $\lim_{n\to\infty}(\frac{F_{n+1}}{F_n})=x$. If we divide $(1)$ through by $F_{n+1}$ we get:

$\begin{align*}\frac{F_{n+2}}{F_{n+1}}=1 + \frac{F_n}{F_{n+1}}\end{align*}\tag{2}$

Clearly from our definition of the $\lim_{n\to\infty}(\frac{F_{n+1}}{F_n})=x$ we get that $(2)\equiv x=1+\frac{1}{x}$. This is easy enough to solve, we simply multiply through by $x$ and rearrange to get a quadratic we can solve.

$\begin{align*}x^2-x-1=0
\\\Rightarrow x = \frac{1\pm\sqrt{5}}{2}\end{align*}$

Only one of these two possible x values are logical, as the sequence is weakly increasing and all of the terms are greater than or equal to 0 clearly the ratio between terms is positive $\therefore\ x = \frac{1+\sqrt{5}}{2}$. This is the golden ratio, $\phi$.

Our definition that $x=1+\frac{1}{x}$ has interesting implications when we represent it as a recurrence relation, $x_{n+1}=1+\frac{1}{x_n}$. If we set $x_0 = 1$ then $x_1 = 1+\frac{1}{1},\ x_2 = 1 + \frac{1}{1+\frac{1}{1}}$, etc. This continues on such that $\lim_{n\to\infty}(x_{n+1})\equiv\phi = 1 + \frac{1}{1+\frac{1}{1+\frac{1}{\ddots}}}$, this is an example of an infinite continued fraction.

A continued fraction is essentially fractions within fractions (frac-cep-tions?), $a_1 + \frac{1}{a_2 + \frac{1}{\ddots \, + \frac{1}{a_m}}}$.

An infinite continued fraction is one that does not terminate after a finite sequence of iterations, $a_1 + \frac{1}{a_2 + \frac{1}{\ddots}}$. An irrational number can be continually, more accurately, approximated using infinite continued fractions.

If we want to represent any integers as an infinite continued fractions we can begin by thinking of the general continued fraction:

$\begin{align*}a=\frac{k}{1+\frac{k}{1+\frac{k}{\ddots}}} \Rightarrow a=\frac{k}{1+a} \Rightarrow a^2+a-k=0\end{align*}\tag{3}$

For a to be rational in this quadratic $1+4k$ must be a square number, clearly this square will be odd (odd + even = odd) from this you can quickly calculate the first few values of k to be $k = 2,\ 6,\ 12,\ 20,\ ...$, it can be quickly shown that the nth term $k_n=n^2+n$. Using the quadratic formula on $(3)$ we find that $a=\frac{-1+\sqrt{4(n^2+n)+1}}{2}\equiv\frac{-1\pm\sqrt{(2n+1)^2}}{2}\equiv\frac{2n}{2}=n$.

Therefore for all positive integers, a, we can represent them as an infinite continued fraction if and only if $k=a^2+a$. Or to put it mathematically:

$a=\frac{k}{1+\frac{k}{1+\frac{k}{\ddots}}},\ a\in\mathbb{N} \Leftrightarrow k=a^2+a$

This is one example of how useful (and fun!) continued fractions can be, they are also much more mathematically relevant than decimals as they provide a lot more useful information about the nature of the number itself.

See if you can express $\sqrt{2}$ as an infinite continued fraction. Leave any answers in the comment section.

AS and GCSE Maths Free Tuition

I am offering free help to anyone who needs it on any GCSE or AS Maths (I am best at C1, C2 and FP1; but can help at any). If you need any help on any of these, or just a general mathematical query, just leave a comment here and I will try to explain here and if you need long term support I will provide you with my email address and we can talk more regularly there. So what are you waiting for? Post your questions now!

GCSE Maths

I know the time of the dreaded GCSE's (for all non-British readers, it's the most important exam taken when you are 16, end of mandatory education exam). And I know that there is countless numbers of revision websites out there, but in my experience they're very hard to follow, do not explain everything fully and are not specialised in helping you.

What am I offering? Free, personalised help. Got a question on anything Maths wise that you do not understand? Post a comment or catch me on twitter. I will reply to you, and I will help you. If you leave your email address in the comment you post I can email a response, and if I find the particular question you ask interesting I will do a whole post dedicated to the topic, going more in depth and explaining it at a higher level.

So what have you got to lose? Free help, no need to pay £25 an hour for a tutor when you can ask me and I will help you entirely for free! Please tell your friends about the help I am offering, as I want to help as many people as I possibly can.