How are we able to calculate specific numbers in the Fibonacci Sequence? 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: The closed form calculation for Fibonacci sequences is known as Binet's Formula.
A: 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 )
A: 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.
A: 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.
A: 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.
A: 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.
A: 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.
