# Fibonacci nth term formula

1. Jun 23, 2012

### jd12345

I want to find a derivation for formula of nth term of fibonacci formula. Searching the net - I found two methods : (i) First one assumes that the nth terms will be some number raised to power of n....I don't like this one as it assumes the formula initially
(ii) the second one involves matrices but i don't understand a large portion of the derivation

Is there any other way? If not could you tell me what all i have to learn about matrices before i can understand the derivation( it involves eigenvalues and all other stuff that i don't understand).
The matrix proof is here : http://mathproofs.blogspot.in/2005/04/nth-term-of-fibonacci-sequence.html

2. Jun 23, 2012

### Millennial

1. It does not assume the formula initially. It assumes that a polynomial expression exists that satisfies the relation.
2. The matrix proof is a bit complicated. Eigenvalues and eigenvectors are simple concepts; you can look them up on Wikipedia or anywhere else. The proof is complicated in means that it is unnecessary for it to be that complex.

3. Jun 23, 2012

### awkward

4. Jun 23, 2012

### AlephZero

If you learn enough linear algebra to understand the matrix proof, it will then be easy to see why the solution involves power series.

I can't think of a "simple" way to motivate the assumption about power series, except an analogy with a geometric series. If you take a simpler difference equation like $a_{n+1} = c a_n$, the solution is $a_0, a_0c, a_0c^2, \dots a_0c^n \dots$ So you might expect the solution to a more complicated difference equation to involve power series as well.

There is also an analogy between linear difference equations with constant coefficients, where the solutions as power series, and linear differential equations with constant coefficients, where the solutions are exponential functions. But you need linear algebra to explain why the differential equations have that form of solution, so that doesn't really help you...

5. Jun 24, 2012

### haruspex

The supposition that the answer is in the form of a geometric sequence is only temporary. Having found the ratio, the correctness can then be established by induction. So the proof is quite sound.
Or is your objection that the solver had to make the right guess to get started? You can put that down to experience of handling recurrence relations generally.

6. Jun 24, 2012

### skiller

Just out of interest, I read this proof, and I understood it till the bit where he says:
Does the second column of that 2x2 matrix on the third line look wrong to anyone else?

I know it doesn't actually matter to the proof of his theorem (or whatever it is you call it) as it all depends on the first column, but anyway? Have I lost a brain cell or two?

7. Jun 25, 2012

### haruspex

No, it looks right to me. E.g. (√5-1)n+1(√5+1) = (√5-1)n(√5-1) (√5+1) = (√5-1)n(5-1) = (√5-1)n4

8. Jun 25, 2012

### sachav

Another way to prove it using basic linear algebra would be as follows.

First of all, the set $E$ of sequences $(u_n)$ such as $u_{n+2} = u_{n+1} + u_n$ for all $n \in \mathbf N$ is a vector space over $\mathbf R$ (this is very easy to show).

Also, $E$ is of dimension 2 (intuitively, any sequence of $E$ is entirely defined by its two first terms, i.e. $E$ is isomorphic to $\mathbf R^2$).

Next, by calling $(F_n)$ our Fibonacci sequence, $(F_n) \in E$, so $(F_n)$ can be expressed as a linear combination of two basis vectors (here, sequences) of $E$.
This is the tricky part. You have to find two sequences, not proportional to each other, verifying the recurrence relation $u_{n+2} = u_{n+1} + u_n$, that you can clearly explicit. You can easily show that $(\varphi^n)$ and $(\bar{\varphi}^n)$ verify that relation, where $\varphi$ and $\bar{\varphi}$ are the solutions to the equation $x^2=x+1$, namely $\dfrac{1+\sqrt 5}{2}$ and $\dfrac{1-\sqrt 5}{2}$ .
Indeed, $\varphi^2 = \varphi + 1$ by definition, and multiplying by $\varphi^n$ gives $\varphi^{n+2} = \varphi^{n+1} + \varphi^n$ (same goes for $\bar{\varphi}$).

So the sequences $(\varphi^n)$ and $(\bar{\varphi}^n)$ verify the recurrence relation, i.e. are vectors of $E$. They aren't proportional (you can see that by checking the two first terms of each sequence), so they form a basis of $E$. Thus, you can express $(F_n)$ as a linear combination of $(\varphi^n)$ and $(\bar{\varphi}^n)$, in other words, there exists $\lambda, \mu$ reals such that for all $n$, $F_n = \lambda \varphi^n + \mu\bar{\varphi}^n$.

Evaluating at $n = 0$ and $n = 1$ gives $\lambda + \mu = 0$ and $\lambda\varphi + \mu\bar{\varphi} = 1$, which solves into $\lambda = -\mu = \dfrac{1}{\varphi-\bar{\varphi}}$.

Finally, $F_n = \dfrac{\varphi^n - \bar{\varphi}^n}{\varphi-\bar{\varphi}}$.

Last edited: Jun 25, 2012
9. Jun 25, 2012

### skiller

Thanks. It's obvious now. That'll teach me to be considering maths at 6 in the morning after watching England losing again!