5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ If I had to compute $F_{28}$, I would certainly do it be successive additions the obvious way. Finding a shortcut solution would take more time. $\endgroup$ Commented Aug 10, 2016 at 18:52
  • $\begingroup$ If I had to compute $F_{28}$, I would certainly do it be successive additions the obvious way. Finding a shortcut solution would take more time. Maybe with the doubling formula ? $\endgroup$ Commented Aug 10, 2016 at 19:21
  • $\begingroup$ $F_{28} = \underbrace{3}_{= F_4} \times \underbrace{\overbrace{13}^{=F_7} \times \color{red}{29}}_{= F_{14}} \times 281$ $\endgroup$ Commented Aug 10, 2016 at 19:28
  • 5
    $\begingroup$ Calling this a duplicate of this one(among others). At least I didn't see the answers here adding anything to the answers from 6 years ago. I recall having posted links to those answers on other sites (or other answers from approximately the same year) $\endgroup$ Commented Aug 10, 2016 at 20:14
  • $\begingroup$ @achillehui That's true because they form a divisibility sequence.. But that doesn't lead to a fast general way to compute them. $\endgroup$ Commented Aug 10, 2016 at 20:48

5 Answers 5

Reset to default
7
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ Why do you think they wrote the prime factorization first? $\endgroup$ Commented Aug 10, 2016 at 18:41
  • $\begingroup$ @Puzzled417: I have no idea. Apparently they had some use for it, but it’s not connected with any nice way of calculating the Fibonacci numbers. $\endgroup$ Commented Aug 10, 2016 at 18:42
  • 1
    $\begingroup$ @Puzzled417 perhaps they were trying to point out some property by means of example which was to be proven in a later example or exercise. For example, $F_{4n}$ is always a multiple of three for any natural number $n$. (Notice a pattern: $\color{red}{0},1,1,2,\color{red}{3}, 5, 8, 13, \color{red}{21}, 34, 55, 89, \color{red}{144},\dots$) (If this wasn't included in your textbook, it is a nice problem that I recommend trying to prove). In particular, $F_{28}$ also follows this pattern. $\endgroup$ Commented Aug 10, 2016 at 18:49
  • $\begingroup$ Could you compute that by hand ? $\endgroup$ Commented Aug 10, 2016 at 18:52
  • $\begingroup$ @Yves: Yes. Would I? Of course not: for that I’d use the recurrence. $\endgroup$ Commented Aug 10, 2016 at 18:55
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ I am just confused why they would write the prime factorization first. $\endgroup$ Commented Aug 10, 2016 at 18:49
2
$\begingroup$

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}$

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.