Use eigendecomposition to compute number in modified Fibonacci sequence

I constructed the following code to compute x13:

clear all
close all
clc

f(1) = 3;
f(2) = 5; 

for i = 3 : 13
    f(i) = (f(i-1) + f(i-2))-4;
end

Unfortunately, the desired response is: Use the method of eigendecomposition to compute x13 for this Fibonacci Cat sequence. What is the largest eigenvalue? What is the eigenvector corresponding to this largest eigenvalue?

I was able to use a for-loop to figure out x13, but I do not know how to use the eigendecomposition to compute this value. Thanks!

Answer 1

[Roger Stafford]

First, you can convert the recursion to

 y_(k+1) = y_k + y_(k-1)

where y_k = x_k - 4. Then you can write

 [y_(k+2);y_(k+1)] = A * [y_(k+1);y_k]

where A = [1,1;1,0]. Then find the eigenvalues and eigenvectors of A.

 [V,D] = eig(A);

Hence you would have

 [y_13; y_12] = A^11*[y_2;y_1] = (V*D^11*V')*[y_2;y_1]

where D^11 is merely the eleventh power of the diagonal eigenvalues. This expresses the value of y_13 (and therefore x_13) directly in terms of y_2 and y_1 without any iterated steps.

The Wikipedia article at:

 http://en.wikipedia.org/wiki/Fibonacci_number

describes this procedure in their section 5 - Matrix Form.

[Nicolas]

Thank you for your response.

I have attempted to utilize the code you provided, but am receiving errors when trying to run it.

This is what I am trying to run:

clear all
close all
clc

y_k = x_k - 4;
A = [1,1;1,0];

y_(k+1) = y_k + y_(k-1);

[y_(k+2);y_(k+1)] = A * [y_(k+1);y_k];

[V,D] = eig(A);

[y_13; y_12] = A^11*[y_2;y_1] = (V*D^11*V')*[y_2;y_1];

I am receiving the error message:

Error: File: hw5exercise3.m Line: 10 Column: 8
Multiple left-hand sides must be separated by commas.

Do you know how I can resolve this problem?

Thanks!