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