Calculating Fibonacci numbers 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.
 A: 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).
A: The simplest direct calculation is to take the integer nearest to $\frac{\varphi^n}{\sqrt5}$, where $\varphi=\frac12(1+\sqrt5)$; see here.
A: 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.
A: 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$.
A: 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}$
