Deriving the Formula for the nth Term of the Fibonacci Sequence Using Matrices

[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

 

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

 

[awkward]

Another way to derive the formula is via generating functions. Here is a link to one such derivation:

http://courses.csail.mit.edu/6.042/fall05/ln11.pdf

 

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

 

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

 

[skiller]

The matrix proof is here : http://mathproofs.blogspot.in/2005/04/nth-term-of-fibonacci-sequence.html

Just out of interest, I read this proof, and I understood it till the bit where he says:

And now we plug it all into find a formula for the nth power of A

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?

 

[haruspex]

No, it looks right to me. E.g. (√5-1)ⁿ⁺¹(√5+1) = (√5-1)ⁿ(√5-1) (√5+1) = (√5-1)ⁿ(5-1) = (√5-1)ⁿ4

 

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

 

[skiller]

No, it looks right to me. E.g. (√5-1)ⁿ⁺¹(√5+1) = (√5-1)ⁿ(√5-1) (√5+1) = (√5-1)ⁿ(5-1) = (√5-1)ⁿ4

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