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.

Proof by Contradiction: Infinite Prime Numbers

There are many complex and obscure methods of proving that there are infinite prime numbers, but this one is certainly the easiest and it is a demonstration of how unpredictable numbers can be dealt with in an efficient manner, it is also an easy introduction to proofs by contradiction.

First, just to clarify what proof by contradiction actually means:
1.) We assume that what we are trying to prove to be false is in fact true.
2.) If we find a contradiction in our assumed hypothesis that we have assumed then it can not be true. And that means that our assumed hypothesis is false, proving what we originally wanted.

So using this as our basis we are going to assume that there is in actual fact a finite amount of prime numbers, how many there is does not matter just that at some point there are no more prime numbers. If we multiply all of these prime numbers together we will get:

2 × 3 × ... × p_n-1 × p_n

Where p_n is the last prime number and this number is clearly not prime as is has every single prime number as a factor. However if we add 1 to this number then any of the prime numbers that we try to divide it by will give a remainder of 1, this means that it too is prime!
p = 2 × 3 × ... × p_n-1 × p_n + 1

If this number is also prime it means that our original statement about there being finite prime numbers is incorrect, therefore there are an infinite number of prime numbers!

This took literally two lines of working to prove that there are an infinite number of prime numbers, this massive, beautiful and unfathomable concept was proved so efficiently and beautifully. This is what Maths is about, how concisely you can express complicated statements. Maths is solely about explaining the world around us and where this leads us is some amazing, incomprehensible places.