(50g) Nth Fibonacci Number

[rprosperi]

(02-27-2015 05:10 AM)Thomas Klemm Wrote:  

(02-26-2015 01:42 PM)rprosperi Wrote:  So, can you explain that?

For \(x_{n+2}=x_n+x_{n+1}\) you can define a 2nd sequence \(y_n=x_{n+1}\).
Thus the relation becomes:

\(y_{n+1}=x_{n+2}=x_n+y_n\).

Now you combine both sequences into a vector:

\(z_n=\begin{bmatrix}
x_n \\
y_n
\end{bmatrix}\)

This allows to merge both equations into a single one:

\(z_{n+1}=\begin{bmatrix}
x_{n+1} \\
y_{n+1}
\end{bmatrix}=\begin{bmatrix}
y_n \\
x_n+y_n
\end{bmatrix}=\begin{bmatrix}
0 & 1 \\
1 & 1
\end{bmatrix}\cdot\begin{bmatrix}
x_n \\
y_n
\end{bmatrix}=M\cdot z_n\)

But this is just the recursive definition of a geometric sequence leading to:

\(z_n=M^n\cdot z_0\) with \(z_0=\begin{bmatrix}
1 \\
0
\end{bmatrix}\)

HTH
Thomas

Another one! There are mathematicians everywhere I look here. And thank god for that, as us mere mortals need folks like you to explain stuff like this so we can go about implementing the algorithms on our machines, without having to derive the equations ourselves.

More seriously, thanks Thomas for these nice derivations. Your patient step-by-step approach is easy to follow and instructional. I certainly make no claim about having any of the inspiration behind the derivation, which is of course where the magic lies, but its still interesting to follow along.