Category Archives: Fibonacci

October 18, 2024 · 7:06 am

Fibonacci Sequence – Finding the Closed Form

I have been reading An Imaginary Tale – The Story of $\sqrt{-1}$ by Paul J Nahin, which is fabulous. There was a bit in chapter 4 where he found the closed form of the generalised Fibonacci sequence. I thought it would be a good exercise to find the closed from of the Fibonacci sequence.

Just to remind you, the Fibonacci sequence is

$1, 1, 2, 3, 5, 8, 13, 21, ...$

and it is defined recursively

$\begin{equation*}T_{n+2}=T_{n+1}+T_n, T_0=1, T_1=1\end{equation}$

That is, the next term is the sum of the two previous terms, i.e.

$\begin{equation*}T_3=T_2+T_1=1+1=2\end{equation}$

Now the starting off point is slightly dodgy as it involves and educated guess as Paul Nahin writes,

How do I know that works? Because I have seen it before, that’s how! […] There is nothing dishonourable about guessing correct solutions – indeed, great mathematicians and scientists, are invariable great guessers – just as long as eventually the guess is verified to work. The next time you encounter a recurrence formula, you can guess the answer too because then you will have already seen how it works.

We start with $T_n=kz^n$

This means $T_{n+2}=T_{n+1}+T_n$ is $kz^{n+2}=kz^{n+1}+kz^n$

$\begin{equation*}kz^{n+2}=kz^{n+1}+kz^n\end{equation}$

$\begin{equation*}kz^n(z^2-z-1)=0\end{equation}$

$\begin{equation*}z^2-z-1=0\end{equation}$

$\begin{equation*}z=\frac{1\pm\sqrt{(-1)^2-4(1)(-1)}}{2}\end{equation}$

$\therefore z=\frac{1+\sqrt{5}}{2}$ or $z=\frac{1-\sqrt{5}}{2}$

Hence $T_n=k_1(\frac{1+\sqrt{5}}{2})^n+k_2(\frac{1-\sqrt{5}}{2})^n$ and we can use the initial conditions $T_0=1$ and $T_1=1$ to find $k_1$ and $k_2$

When $n=0, T_0=1$

(1) $\begin{equation*}1=k_1+k_2\end{equation*}$

When $n=1, T_1=1$

(2) $\begin{equation*}1=k_1(\frac{1+\sqrt{5}}{2})+k_2(\frac{1-\sqrt{5}}{2})\end{equation*}$

From equation $1$ , $k_2=(1-k_1)$ , substitute into equation $2$

$\begin{equation*}1=k_1(\frac{1+\sqrt{5}}{2})+(1-k_1)(\frac{1-\sqrt{5}}{2})\end{equation}$

$\begin{equation*}1=k_1(\frac{1+\sqrt{5}}{2})+\frac{1-\sqrt{5}}{2}-k_1(\frac{1-\sqrt{5}}{2})\end{equation}$

$\begin{equation*}1=k_1\sqrt{5}+\frac{1-\sqrt{5}}{2}\end{equation}$

$\begin{equation*}1-(\frac{1-\sqrt{5}}{2})=\sqrt{5}k_1\end{equation}$

$\begin{equation*}k_1=\frac{1}{\sqrt{5}}(\frac{1}{2}+\frac{\sqrt{5}}{2})\end{equation}$

$\begin{equation*}k_1=\frac{1}{2}(\frac{1}{\sqrt{5}}+1)\end{equation}$

$\begin{equation*}k_1=\frac{1+\sqrt{5}}{2\sqrt{5}}\end{equation}$

$\begin{equation*}k_2=1-\frac{1+\sqrt{5}}{2\sqrt{5}}\end{equation}$

$\begin{equation*}k_2=-(\frac{1-\sqrt{5}}{2\sqrt{5}})\end{equation}$

$\therefore T_n=(\frac{1+\sqrt{5}}{2\sqrt{5}})(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2\sqrt{5}})(\frac{1-\sqrt{5}}{2})^n$

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

Does it work?

Remember the sequence is $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...$

If $n=5, T_n=8$

$\begin{equation*}T_5=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^6-\frac{1-\sqrt{5}}{2})^6)\end{equation}$

As you can see it works!

Leave a Comment

Filed under Complex Numbers, Fibonacci, Fibonacci Sequence, Interesting Mathematics, Sequences