# The Fibonacci Sequence

The Fibonacci Sequence is by far the most famous and probably the oldest recursive sequence orginating from a problem published 1202 by Leonardo Pisano Fibonacci in his book Liber abacci.

 It also represents the first and thus simplified attempt to describe dynamic structures within mathematics: A man puts a young pair of rabbits into a closed garden. After two months they start to produce offspring: two little rabbits every month. How many pairs of rabbits live in that garden after a year's time?

Counting the rabbits for, let's say seven months, we get the following table (k denotes a juvenile, k a one month old, K an adult rabbit):

 month parents and juveniles one month old rabbits pairs 1 kk 1 2 kk 1 3 KK kk 2 4 KK kk kk 3 5 KK kk KK kk kk 5 6 KK kk KK kk KK kk kk kk 8 7 KK kk KK kk KK kk KK kk KK kk kk kk kk 13

Obviously the number of pairs coincides with the first seven Fibonacci numbers. From that we can solve the rabbit problem with the twelfth Fibonacci number: 144.

Besides this modest start of population dynamics the Fibonacci numbers unfold a surprising richness of mathematical coherence. There is for example a relation to the golden section
 i The golden section is the solution of a partition task: A given line of length $s>0$ is to be devided into two parts, so that the ratio 'whole line to bigger segment' is exactly the same as 'bigger segment to smaller one'. Let the given line be the interval $\left[0,s\right]$. Then we have to find a real number x from $\right]0,s\left[$ satisfying $\frac{s}{x}=\frac{x}{s-x}\text{.}$ Thus our problem is solved as soon as we could solve the quadratic equation ${s}^{2}-sx={x}^{2}$ for x. With $x\in \right]0,s\left[$ however we get from the p/q-formula: $\begin{array}{ll}\hfill & {x}^{2}+sx-{s}^{2}=0\hfill \\ ⇔\hfill & x=-\frac{s}{2}+\sqrt{\frac{{s}^{2}}{4}+{s}^{2}}\hfill \\ ⇔\hfill & x=-\frac{s}{2}+\frac{s}{2}\sqrt{5}\hfill \\ ⇔\hfill & x=s\cdot \frac{-1+\sqrt{5}}{2}\hfill \\ ⇔\hfill & x=s\cdot \mathsf{\varphi }\text{.}\hfill \end{array}$ So we get the value for x simply by multiplying the length s with the golden section number $\mathsf{\varphi }$.
which we will use to find a non-recursive representation for the Fibonacci sequence. To that end we need the golden section numbers

Consider:

There are some interesting properties of the section numbers. We need the following ones for the remainder.

• $\mathsf{\Phi }-\mathsf{\varphi }=1$

• $\mathsf{\Phi }\cdot \mathsf{\varphi }=1$

• $\left(x-\mathsf{\Phi }\right)\cdot \left(x+\mathsf{\varphi }\right)={x}^{2}-\left(\mathsf{\Phi }-\mathsf{\varphi }\right)x-\mathsf{\Phi }\cdot \mathsf{\varphi }={x}^{2}-x-1$

From the last equation we see that satisfy  ${x}^{2}-x-1=0$, that means:

$\begin{array}{l}{\mathsf{\Phi }}^{2}=\mathsf{\Phi }+1\hfill \\ {\left(-\mathsf{\varphi }\right)}^{2}=-\mathsf{\varphi }+1\text{.}\hfill \end{array}$

These preparations enable us to present a non-recursive version of the Fibonacci sequence.

 Proposition:  Let $\left({a}_{n}\right)$ denote the Fibonacci sequence. Then we have: $\left({a}_{n}\right)=\left(\frac{{\mathsf{\Phi }}^{n}-{\left(-\mathsf{\varphi }\right)}^{n}}{\sqrt{5}}\right)\text{.}$ Proof:  We prove by induction. The two stage recursion however now needs a two step basis of induction. ${1\in A}:\frac{\mathsf{\Phi }-\left(-\mathsf{\varphi }\right)}{\sqrt{5}}=\frac{\mathsf{\Phi }+\mathsf{\varphi }}{\sqrt{5}}=\frac{1+\sqrt{5}-1+\sqrt{5}}{2\sqrt{5}}=1={a}_{1}\text{.}$ ${2\in A}:\frac{{\mathsf{\Phi }}^{2}-{\left(-\mathsf{\varphi }\right)}^{2}}{\sqrt{5}}=\frac{\mathsf{\Phi }+1-\left(-\mathsf{\varphi }+1\right)}{\sqrt{5}}=\frac{\mathsf{\Phi }+\mathsf{\varphi }}{\sqrt{5}}=1={a}_{2}\text{.}$ ${n\in A⇒n+1\in A}:$ $\begin{array}{ll}\hfill \frac{{\mathsf{\Phi }}^{n+2}-{\left(-\mathsf{\varphi }\right)}^{n+2}}{\sqrt{5}}& =\frac{{\mathsf{\Phi }}^{n}{\mathsf{\Phi }}^{2}-{\left(-\mathsf{\varphi }\right)}^{n}{\left(-\mathsf{\varphi }\right)}^{2}}{\sqrt{5}}\hfill \\ \hfill & =\frac{{\mathsf{\Phi }}^{n}\left(\mathsf{\Phi }+1\right)-{\left(-\mathsf{\varphi }\right)}^{n}\left(-\mathsf{\varphi }+1\right)}{\sqrt{5}}\hfill \\ \hfill & =\frac{{\mathsf{\Phi }}^{n+1}+{\mathsf{\Phi }}^{n}-{\left(-\mathsf{\varphi }\right)}^{n+1}-{\left(-\mathsf{\varphi }\right)}^{n}}{\sqrt{5}}\hfill \\ \hfill & =\frac{{\mathsf{\Phi }}^{n+1}-{\left(-\mathsf{\varphi }\right)}^{n+1}}{\sqrt{5}}+\frac{{\mathsf{\Phi }}^{n}-{\left(-\mathsf{\varphi }\right)}^{n}}{\sqrt{5}}\hfill \\ \hfill & ={a}_{n+1}+{a}_{n}\hfill \\ \hfill & ={a}_{n+2}\text{.}\hfill \end{array}$

There is much more information on Fibonacci numbers on the net. This site e.g. is very comprehensive.