Calculating Fibonacci numbers

Question

In my book they calculated the $28$th Fibonacci number and said $F_{28} = 3 \times 13 \times 19 \times 281 = 317811$. This made me wonder if there was an easier way to find the $28$th Fibonacci number than by doing it by hand.

Answer 1

The simplest direct calculation is to take the integer nearest to $\frac{\varphi^n}{\sqrt5}$, where $\varphi=\frac12(1+\sqrt5)$; see here.

Answer 2

There is a formula which is now called Binet's Formula, but was allready known to Euler, Daniel Bernoulli and de Moivre,

$$F_n=\frac{\phi^n}{\sqrt{5}}+(-1)^{n+1}\frac{\phi^{-n}}{\sqrt{5}},$$ in which $\phi=(1+\sqrt{5})/2$ is the golden ratio.

The result of Brian M. Scott follows by an estimation of the second term.

Answer 3

There are identities that relate $F_n$ and $F_{kn}$ like this one:

$$F_{4n} = 4F_nF_{n+1}(F_{n+1}^2 + 2F_n^2) - 3F_n^2(F_n+2F_{n+1}^2)$$

Here you can express $F_{28}$ in terms of $F_7=13$ and $F_8=21$.

Answer 4

They can be computed by matrix exponentiation, which is quick by repeated squaring. Recall $$ \left(\begin{array}{ccc} \,1 & 1 \\\ 1 & 0 \end{array}\right)^{\large n}\ =\ \left(\begin{array}{ccc} F_{\large n+1} & F_{\large n} \\\ F_{\large n} & F_{\large n-1} \end{array}\right) $$

More simply $ $ if $\: (a,b)_{\large n} := (f_{\large n-1},\,f_{\large n}),\ $ then applying the above yields

that a $\:\rm\color{#0a0}{shift}\:$ is $\ (a,b)_{\large n}\color{#0a0}\Rightarrow(b,\,a+b)_{\large n+1}\ $

and $\,\rm\color{#c00}{doubling}$ $\ (a,b)_{\large n} \color{#c00}\Rightarrow (a^2\!+b^2,\,b^2\!+2ab)_{\large 2n}.\ $ For example, let's compute your $\, F_{\large 28}$

$$(0,1)_{\large 1}\!\color{#0a0}\Rightarrow (1,1)_{\large 2}\color{#0a0}\Rightarrow (1,2)_{\large 3} \color{#c00}\Rightarrow (5,8)_{\large 6}\color{#0a0}\Rightarrow (8,13)_{\large 7}\color{#c00}\Rightarrow (233,377)_{\large 14}\color{#c00}\Rightarrow(\ldots,317811)_{\large 28}$$

is computable using only mental arithmetic (except possibly the final step).

Answer 5

Unfortunately this requires (sometimes) a calculator to compute. You could potentially use the following: Let $\phi = \frac{1+\sqrt5}{2}$

$F_{n}=\frac{\phi^x-(1-\phi)^x}{\sqrt5}$