A Non-recursive Fibonacci Sequence How can I determine the general term of a Fibonacci Sequence? Is it possible for any one to calculate F2013 and large numbers like this?
Is there a general formula for the nth term of the Fibonacci Sequence?
If there is a combinatorial formula, that is more preferable; some formula like 
Fn = xCy or xPy or something like that for some x and y. 
 A: It can be shown that:
$$
F_n = \mathop{round}\left(\frac{(1 + \sqrt{5})^n}{2^n \sqrt{5}}\right)
$$
but that doesn't help much, as it needs high-precision $\sqrt{5}$.
The other technique is to see that:
$$
\begin{pmatrix}
  F_{n + 2} \\
  F_{n + 1}
\end{pmatrix}
  = \begin{pmatrix}
      1 & 1 \\
      1 & 0
    \end{pmatrix}
      \cdot \begin{pmatrix}
              F_{n + 1} \\
              F_n
            \end{pmatrix}
$$
so that:
$$
\begin{pmatrix}
  F_n \\
  F_{n - 1}
\end{pmatrix}
  = \begin{pmatrix}
      1 & 1 \\
      1 & 0
    \end{pmatrix}^{n - 1}
      \cdot \begin{pmatrix}
              1 \\
              0
            \end{pmatrix}
$$
You could compute this by diagonalizing the matrix, but that leads to the same trouble as the previous technique (not too surprisingly, the eigenvalues are precisely the troublesome irrational zeros of $z^2 - z - 1$). But if you compute the power of the matrix by an efficient exponentiation method (like exponentiation by squaring) you get a practical algorithm.
A: Yes; the Fibonnaci recursion is linear , so that it can be expressed as a $2\times 2$-matrix. The matrix is diagonalizable, so that its powers have a relatively nice form.
A: From wiki:
$\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$
A: There is a pretty slick way of finding a closed form for the Fibonacci sequence through the use of generating functions.
Let $G(x)$ be the generating function corresponding to the F. sequence.  That is, we let $G(x)$ be the power series with coefficient coming form the Fibonacci sequence.  $$G(x) = \sum_{n=0}^\infty F_n x^n = 1 + x + 2x^2 + 3x^3 + \cdots.$$
Note that we are taking $F_0 = 1$.  Also it can be shown through induction that $F_n$ grows slower than $2^n$, which means that $G(x)$ has a radius of convergence of at least 1/2.
Now consider the identity: $G(x) - x G(x) - x^2 G(x) = 1$ which can be found by using the properties of the F. sequence.
This tells us that $$G(x) = \frac{1}{1-x-x^2}.$$
Now this is where the interesting parts come in.  We can factor the denominator: into $-(x-\phi)(x-\hat\phi)$ where $\phi = \frac{1+\sqrt{5}}{2}$ and $\hat\phi = \frac{1-\sqrt{5}}{2}$.  Then we can use partial fraction decomposition to find $A$ and $B$ for which: $$G(x) = \frac{A}{x-\phi} + \frac{B}{x+\hat\phi}$$  Now you can expand each term into a geometric series involving $\phi$ and $\hat \phi$ respectively.
Finally you equate the coefficients of $F_n$ with the new terms found in the last step and you find what tsktsktsk posted from wikipedia.
This can be done for any finite linear recurrence relation.  It's pretty darned cool.
A: When
(1) $F_{n+2} = F_{n+1} + F_{n}$
one can try $F_n = \phi^n$, then we obtain
(2) $\phi^{n+2} - \phi^{n+1} - \phi^n = 0$,
thus
(3) $\phi^n \Big( \phi^2 - \phi - 1 \Big) = 0$,
ignoring the trivial case $F_n = 0$ we obtain
(4) $\phi = \frac{1}{2} \pm \frac{1}{2} \sqrt{5}$
So we get
(5) $F_n = a \left( \frac{1}{2} + \frac{1}{2} \sqrt{5} \right)^n + b \left( \frac{1}{2} - \frac{1}{2} \sqrt{5} \right)^n $
As $F_0 = 0$ and $F_1 = 1$, we get
(6a) $ a + b = 0 $
(6b) $ \frac{1}{2} \Big( a + b \Big) + \frac{1}{2} \Big( a - b \Big) \sqrt{5} = 1$
So
(7a) $\displaystyle a = \frac{1}{\sqrt{5}} $
(7b) $\displaystyle a = -\frac{1}{\sqrt{5}} $
Then
(8) $\displaystyle F_n = \frac{ \left( \frac{1}{2} + \frac{1}{2} \sqrt{5} \right)^n - \left( \frac{1}{2} - \frac{1}{2} \sqrt{5} \right)^n }{\sqrt{5}} $
A: yes there is a combinatoral formula 
$F_{n+1}=\sum_{k=[\frac{n+1}{2}]}^{n}{kC{n-k}}$
Proof is very simple.
This formula is related to this problem:-
In how many ways a number $n$ can be represented as sum of $1$'s and $2$'s?
