 ## Fibonacci Numbers

The Fibonacci Numbers have been of great interest since they were first seen as a solution to an algebra word problem published in 1202. The Fibonacci Numbers have many interesting properties which have many applications. For this the focus will be on finding a formula to find the nth Fibonacci number in the sequence.

The sequence is set up so that –

$$F_0=1$$

$$F_1=1$$

$$F_2=2$$

$$F_3=3$$

$$F_4=5$$

$$F_5=8$$

The pattern for generating new terms relies on the previous two terms and is written as  $$F_{n+2}=F_{n+1}+F_n$$

For any integer value of $$n>0$$.

This is called the renewal equation. It uses information from the current and previous steps to generate future steps. It is also a second order difference equation.

Because it is a difference equation this may be rewritten as follows:

$$F_{n+2}=F_{n+1}+F_n$$

$$F_n = \lambda^n$$

$$\lambda^{n+2}=\lambda^{n+1}+\lambda^n$$

This can be factored:

$$\lambda^n \lambda^2 = \lambda^n \lambda^1 + \lambda^n \lambda^0$$

Each term has $$\lambda^n$$ which when divided out leaves:

$$\lambda^2 = \lambda^1 +1$$

Solving for $$\lambda$$:

$$\lambda^2 -\lambda^1 -1 =0$$

$$\lambda_{1,2}=\frac{1\pm\sqrt{1+4}}{2}$$

$$\lambda_1 = \frac{1}{2}\left(1+\sqrt{5}\right)$$

$$\lambda_2 = \frac{1}{2}\left(1-\sqrt{5}\right)$$

Since this is a difference equation that is linear, a solution can be made from the linear superposition of the known solutions.

$$F_n = a \lambda_1^n + b\lambda_2^n$$

To solve for $$a$$ and $$b$$ the values for $$F_0$$ and $$F_1$$ make the system of equations:

$$F_0=1 \rightarrow a \lambda_1^{0} + b \lambda_2^{0} = a + b$$

$$a = 1 – b$$

$$F_1=1 \rightarrow a \lambda_1^{1} + b \lambda_2^{1}$$

$$1 = a \frac{1}{2} \left(1+\sqrt{5}\right) + b \frac{1}{2} \left(1-\sqrt{5}\right)$$

Substituting and solving for b:

$$2 =\left(1-b\right)\left(1+\sqrt{5}\right) + b \left(1-\sqrt{5}\right)$$

$$2 =1+ \sqrt{5} -b -b\sqrt{5} + b – b\sqrt{5}$$

$$1-\sqrt{5}=-2\sqrt{5} b$$

$$b = -\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)$$

Solving for a

$$a = 1 + \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)$$

$$a = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)$$

Putting it back together

$$F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)\left(\frac{1-\sqrt{5}}{2}\right)^n$$

$$F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}$$

This is for $$0$$ or greater integer values of $$n=0,1,2,3…$$

This is a system of irrational numbers that always answers with an integer.

Also $$\lambda_1\approx 1.6180339887…$$ is the value known as the Golden Section or Golden Ratio.