35
$\begingroup$

I was reading up on the Fibonacci Sequence, $\text {{1,1,2,3,5,8,13,....}}$ when I've noticed some were able to calculate specific numbers. So far I've only figured out creating an array and counting to the value, which is incredibly simple, but I reckon I can't find any formula for calculating a Fibonacci number based on it's position.

Is there a way to do this? If so, how are we able to apply these formulas to arrays?

$\endgroup$
22
$\begingroup$

Wikipedia has a closed-form function called "Binet's formula".

http://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratio

$F\left(n\right) = {{\varphi^n-(1-\varphi)^n} \over {\sqrt 5}}$

This is based on the Golden Ratio.

$\endgroup$
  • 1
    $\begingroup$ Oh, I figured as so. I remember learning about this a while ago with the graph as presentation. Thanks. $\endgroup$ – JonnyLitt Jul 20 '10 at 19:27
  • 1
    $\begingroup$ It is much better than an approximation: it gives the exact value for all $n$ $\endgroup$ – Fanfan Jul 20 '10 at 19:28
  • 1
    $\begingroup$ I see. That's the problem I notice in equations I was looking at before, the approximation kills the "closeness" to the number as the variable gets larger. I essentially see this as the solution, too bad I have to wait 7 minutes to accept yours as the answer. But, cheers, thanks. $\endgroup$ – JonnyLitt Jul 20 '10 at 19:32
  • 6
    $\begingroup$ By the way, if you want an approximation, you can neglect the second term, because $|1-\varphi|<1$, and get $F(n)={\varphi^n \over {\sqrt 5}}$ ; actually if you round that to the next integer you get the correct value. $\endgroup$ – Fanfan Jul 20 '10 at 19:41
30
$\begingroup$

A lot of people have mentioned Binet's formula. But I suspect this is not the most practical way to compute the nth Fibonacci number for large n, because it requires either having a very accurate value of $\sqrt{5}$ and carrying around lots of decimal places (if you want to do floating-point arithmetic) or expanding large powers of $1+\sqrt{5}$ using the binomial formula. The latter comes out to writing the Fibonacci number as a sum of binomial coefficients.

The following formulas hold, though: $$F(2n-1) = F(n)^2 + F(n-1)^2$$ $$F(2n) = (2F(n-1) + F(n)) \times F(n)$$ which you can find derivations of in the Wikipedia article on Fibonacci numbers. This lets you find $F(k)$, for any $k$ even or odd, in terms of two Fibonacci numbers with approximately half the index. The result is faster than Binet's formula.

$\endgroup$
29
$\begingroup$

Also you can use the matrix equation for Fibonacci numbers:

$$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n = \begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix} $$ To calculate $n$-th power of the matrix you can use exponentiation by squaring algorithm.

This approach could also be generalized on the case of arbitrary sequence with linear recurrence relation.

$\endgroup$
  • 8
    $\begingroup$ This is actually known to be (one of) the fastest ways to generate Fibonacci numbers (e.g. Mathematica uses this for integer arguments of the Fibonacci[] function). $\endgroup$ – J. M. is a poor mathematician Aug 23 '10 at 16:26
  • $\begingroup$ It's nearly as fast as mine, but does not rely on matrix operation. My answer runs at 3/2 of the ordinary exponent rate, when modulo is taken to account. $\endgroup$ – wendy.krieger Feb 22 '18 at 12:31
5
$\begingroup$

The closed form calculation for Fibonacci sequences is known as Binet's Formula.

$\endgroup$
4
$\begingroup$

You can use Binet's formula, described at http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

(see also Wikipedia for a proof: http://en.wikipedia.org/wiki/Binet_formula#Closed_form_expression )

$\endgroup$
4
$\begingroup$

To expand on falagar's answer, my favourite proof of Binet's formula:

...Which I was going to post a summary of here, but remembered that everything was awful without Tex, so here is a link to some notes on it I found on google.

The basic idea is to treat pairs of fibonnacci numbers, adjacent in the sequence, as vectors. Moving on to the next adjacent pair induces a linear transformation not unlike that of the matrix falagar posted. Calculating eigenvalues and eigenvectors can give a complete prediction of where an initial vector will find itself, predicting the whole sequence.

It's quite a lot of work but I think it's rather illuminating.

$\endgroup$
3
$\begingroup$

There's a perfectly general way for this sort of problem. I used it to look for instances of $p$, such that if $p$ divided a Fibonacci number, so did $p^2$. There are none under twenty million twelftywise $20.00.00.00.00_{120}=4147200000.$

This method can be used with modular arithmetic into the hundreds of millions.

These are a number of different series, the fibonacci, Lucas series, the side and diagonal of the square approximate, and Heron's triangle. It's written in the REXX programming language.

The actual process is to be found in the 'isoquad' routine, which extends an isoseries (ie a form $T_{n+1}= a.T_n - T_{n-1}$). The actual equation as written gives $T_p$, given in order $a, p, T_0 ,T_1$. It relies on that any isoseries, one can take steps of m, and thus take $T_{m+n} = a\text{^^}m \cdot T_n - T_{n-m}$.

The actual process is like this. The example is to find T(37) Numbers in brackets are the members of the original T(n). We halve out the T(n), and increase the step constant to $T(2x) = T(x)^2-2$, This is the difference between c0, c1, c2, c3.

The values in the second and third columns are as one divides 37 into binary.

 diff          c0   c1   c2   c3   (role, by col 3)     (regular powers)
 (1)  18  1 : (0)  (1)  (2)  (3)   keep odd places       18 1 (1)   (1)
 (2)   9  0 : (1)  (3)  (5)        keep even places       9 0 (2)   (1) = 1+0*2 
 (4)   4  1 : (1)  (5)  (9)  (13)  keep odd places        4 1 (4)   (5) = 1+1*4
 (8)   2  0 : (5)  (13) (21)       keep even places       2 0 (8)   (5) = 5+0*8
 (16)  1  0 :  (5)  (21) (37)       keep even places      1 0 (16)  (5) = 5+0*16
       0  1:   (5)  (37)        c2 = 0, so answer in c1.  0 1 (32)  (37) = 5+1*37

The actual method is similar to finding $a^m$ by binary methods, and runs at 2/3 of the speed of said process.

By adjusting the nature of the multiplication to be a modulus, one can test to see if something like $f_{14400}$ is a multiple of 14401 or not. The heron series, with p set to large powers of 2, is used to find fermat primes, by this very method.

fibon: ; procedure  ;parse arg t0; return isoquad(3,div(t0+2,2),mod(t0,2),1+mod(t0,2))
lucas: ; procedure  ;parse arg t0; return isoquad(3,div(t0+2,2),2-mod(t0,2),3+mod(t0,2))
qside: ; procedure  ;parse arg t0; return isoquad(6,div(t0+2,2),mod(t0,2),2+mod(t0,2)*3)
qdiag: ; procedure  ;parse arg t0; return isoquad(6,div(t0+2,2),  1  ,3+mod(t0,2)*4)
heron: ; procedure  ;parse arg t0; return isoquad(4,t0,2,4)

div:   ; procedure  ;parse arg a, b; c = a % b; if b < a*c then c = c-1 ; return c
mod:   ; procedure  ;parse arg a, b; c = a // b; if c<0 then c=c+b; return c

isoquad:  procedure
parse arg a2, a0, a3, a4
if a0 = 0 then do; a4 = a3; a0 = 1; end
if a0 < 0 then do; a0 = -a0; a4 = a3*a2-a4; end
do forever; if a0 = 1 then leave
a1 = a0//2; a5 = a4*a2 - a3;
if a1 = 0 then a4 = a5
else do; a3 = a4; a4 = a5*a2 - a3; end
a0 = a0 % 2; a2 = a2 * a2 - 2; end
return a4
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.