Illich Jackal
24-04-2004, 16:01
I’m a big fan of the fibonnaci series 1,1,2,3,5…
f(n) = f(n-1) + f(n-2) , f(0) = 0, f(1) = 1
or explicit: f(n) = 1/sqrt(5) * [((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n]
What I find interesting is that the explicit form isn’t that easy to find, but it can be found in different ways. I already know two ways, but I’m sure there are other ways, so if you know one, post it.
1)using the Z-transformation from analyses:
Define F(z) = Z(f(n)) (the z-transformation
We know:
f(n+2) = f(n+1) + f(n)
=>Z(f(n+2)) = Z(f(n+1)+f(n))
the Z-transformation is linear
=>Z(f(n+2)) = Z(f(n+1)) + Z(f(n))
translation
=>z^2*[F(z)-f(0)-f(1)/z] = z*[F(z)-f(0)] + F(z)
=>z^2*F(z) –z = z*F(z) + F(z)
=>(z^2-z-1)*F(z) = z
=> F(z) = z/(z^2-z-1)
now take the inverse Z-transformation and you get:
f(n) = 1/sqrt(5) * [((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n]
2) using matrices from linear algebra:
f(n+1) = f(n) + f(n-1) can be written in matrix-form:
matrix X = [[f(n)],[f(n+1)]]
matrix B = [[f(n-1)],[f(n)]]
matrix A = [[0,1],[1,1]]
then we have:
X=A*B
Matrix S = [[f(0)],[f(1)]] = [[0],[1]]
Gives us:
X = A^n*S
Now we calculate the eigenvalues of A:
Det(x*I-A) = x^2-x-1 = 0
Gives us:
x1 = (1+sqrt(5))/2
x2 = (1-sqrt(5))/2
now A is a 2-2 matrix with 2 different eigenvalues.
Each of these eigenvalues therefore has exactly one Jordanblok in the Jordannormalform of A
Therefore we know the Jordannormalform of A:
[[x1,0],[0,x2]]
so, without knowing the matrix Q, we know that:
A = Q^-1*diag(x1,x2)*Q
Therefore:
A^n = (Q^-1*diag(x1,x2)*Q)^n
= Q^-1*(diag(x1,x2))^n*Q
= Q^-1*diag(x1^n,x2^n)*Q
and we know: X = Q^-1*diag(x1^n,x2^n)*Q *S
f(n) is an element of X, and is therefore a linear combination of the elements of diag(x1^n,x2^n)
so f(n) can be written as:
f(n) = a*x1^n + b*x2^n
this leads to:
f(0) = 0 = a + b
f(1) = 1 = a*(1+sqrt(5))/2 + b*(1-sqrt(5))/2
so:
a = 1/sqrt(5)
b = -1/sqrt(5)
put this in f(n) = a*x1^n + b*x2^n
and you receive:
f(n) = 1/sqrt(5) * [((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n]
f(n) = f(n-1) + f(n-2) , f(0) = 0, f(1) = 1
or explicit: f(n) = 1/sqrt(5) * [((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n]
What I find interesting is that the explicit form isn’t that easy to find, but it can be found in different ways. I already know two ways, but I’m sure there are other ways, so if you know one, post it.
1)using the Z-transformation from analyses:
Define F(z) = Z(f(n)) (the z-transformation
We know:
f(n+2) = f(n+1) + f(n)
=>Z(f(n+2)) = Z(f(n+1)+f(n))
the Z-transformation is linear
=>Z(f(n+2)) = Z(f(n+1)) + Z(f(n))
translation
=>z^2*[F(z)-f(0)-f(1)/z] = z*[F(z)-f(0)] + F(z)
=>z^2*F(z) –z = z*F(z) + F(z)
=>(z^2-z-1)*F(z) = z
=> F(z) = z/(z^2-z-1)
now take the inverse Z-transformation and you get:
f(n) = 1/sqrt(5) * [((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n]
2) using matrices from linear algebra:
f(n+1) = f(n) + f(n-1) can be written in matrix-form:
matrix X = [[f(n)],[f(n+1)]]
matrix B = [[f(n-1)],[f(n)]]
matrix A = [[0,1],[1,1]]
then we have:
X=A*B
Matrix S = [[f(0)],[f(1)]] = [[0],[1]]
Gives us:
X = A^n*S
Now we calculate the eigenvalues of A:
Det(x*I-A) = x^2-x-1 = 0
Gives us:
x1 = (1+sqrt(5))/2
x2 = (1-sqrt(5))/2
now A is a 2-2 matrix with 2 different eigenvalues.
Each of these eigenvalues therefore has exactly one Jordanblok in the Jordannormalform of A
Therefore we know the Jordannormalform of A:
[[x1,0],[0,x2]]
so, without knowing the matrix Q, we know that:
A = Q^-1*diag(x1,x2)*Q
Therefore:
A^n = (Q^-1*diag(x1,x2)*Q)^n
= Q^-1*(diag(x1,x2))^n*Q
= Q^-1*diag(x1^n,x2^n)*Q
and we know: X = Q^-1*diag(x1^n,x2^n)*Q *S
f(n) is an element of X, and is therefore a linear combination of the elements of diag(x1^n,x2^n)
so f(n) can be written as:
f(n) = a*x1^n + b*x2^n
this leads to:
f(0) = 0 = a + b
f(1) = 1 = a*(1+sqrt(5))/2 + b*(1-sqrt(5))/2
so:
a = 1/sqrt(5)
b = -1/sqrt(5)
put this in f(n) = a*x1^n + b*x2^n
and you receive:
f(n) = 1/sqrt(5) * [((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n]