# 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.

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.

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.

From wiki:

$\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$

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.

• Put $x=0.01$ into your generating function, and you find $1/0.9899=1.010203050813....$ – Empy2 Oct 21 '13 at 6:26
• Haha I never thought of that! You could get longer strings with 0.001 and 0.0001 etc. Cool stuff! – Joel Oct 21 '13 at 6:33
• Something that should be mentioned is that even though we can find a closed form for the fibonacci sequence, the best way to calculate a term in the sequence is by using the recursion. There are approximation problems that arise when you have to compute the golden ratio $\phi$. – Joel Oct 21 '13 at 6:41
• @Joel You can also take the appropriate entry from $\begin{pmatrix}1&1\\1&0\end{pmatrix}^n$, avoiding approximation problems and recursion. – Teepeemm Jun 17 '14 at 21:15
• Yes that is true. You can write a general formula by diagonalizing that matrix and taking powers. The generating function approach applies to a broader class of recursions, so I usually just use that. By the way, with the matrix representation you can arrive at the identity $$(-1)^n = F_{n+1}F_{n-1} - F_{n}^2$$ which is occasionally useful. – Joel Jun 19 '14 at 18:26

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}}$

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?