I was reading up on the Fibonacci Sequence, $1,1,2,3,5,8,13,\ldots $ when I 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?
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)\cdot 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.
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.
Wikipedia has a closed-form function called "Binet's formula".
$$F\left(n\right) = {{\varphi^n-(1-\varphi)^n} \over {\sqrt 5}}$$
This is based on the Golden Ratio.
The closed form calculation for Fibonacci sequences is known as Binet's Formula.
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 )
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.
This is an old post, but still... The relation $$ F_0=1, F_1 =1, F_n = F_{n-1}+F_{n-2}, n \ge 2 $$
defines a linear second order homogeneous difference equation. The solution can be found after computing the roots of the associated characteristic polynomial $p(\lambda)=\lambda^2-\lambda -1$, which are $\lambda = \frac{1 \pm \sqrt{5}}{2}$. The general solution is then given by $$ F_n= C_1 \left(\frac{1 + \sqrt{5}}{2} \right)^n + C_2 \left(\frac{1 - \sqrt{5}}{2} \right)^n $$
and the constants $C_1, C_2$ are computed knowing that $F_0 = F_1 = 1$. so, finally, $$ F_n= \frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2} \right)^n - \frac{1}{\sqrt{5}} \left(\frac{1 - \sqrt{5}}{2} \right)^n $$
This is obviously equivalent to Binet's formula, but provides a general process to deal with linear recurrences.
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
