# [Linear Algebra] Closed formula for recursive sequence

1. Jul 25, 2016

### reminiscent

1. The problem statement, all variables and given/known data

2. Relevant equations
a) the one given
b) det(A-λI) = 0
find λ values using A
c)use λ values to find eigenvectors

3. The attempt at a solution
This wasn't explained well enough so I can understand it in class. So far, I made the matrix being multiplied to A have the following elements from top to bottom: x0 = 1, x1 = 1, x2 = 2. The one on the right has the following elements: x1 = 1, x2= 2, x3=7. Is this correct thinking? Do I just find a matrix A that maps the vector on the left to the vector on the right?
I know how to do b) and c), I just don't know how to get A correctly.

2. Jul 26, 2016

### Stephen Tashi

The usual way to describe an element of a matrix is to give it two indices, such as A[1][1] , A[1][2] or $A_{1,1}, A_{1,2}$ etc. Which elements are you trying to describe with the phrase "from top to bottom" ?

You need a matrix A such that:

eq. 1: $A_{1,1} x_k + A_{1,2} x_{k+1} + A_{1,3} x_{k+2} = x_{k+1}$
eq 2: $A_{2,1} x_k + A_{2,2} x_{k+1} + A_{2,3} x_{k+2} = x_{k+2}$
eq 3: $A_{3,1} x_k + A_{3,2} x_{k+1} + A_{3,3} x_{k+2} = x_{k+3}$

An solution to eq. 1 is $A_{1,1} = 0, A_{1,2} = 1, A_{1,3} = 0$.

3. Jul 26, 2016

### reminiscent

Sorry, I completely forgot that A was a 3x3 matrix.
Anyways, I see how you are getting the solutions.
For equation 2, I found these solutions:
A21 = 0 A22 =0 A23= 1
For equation 3, I found:
A31 = 0 A32 = 1 A33 =3

Are those correct? Does what they give for xk+3 have anything to do with the last equation?

4. Jul 26, 2016

### reminiscent

So A can be more than 1 matrix?

5. Jul 26, 2016

### Ray Vickson

You can (and should) check that for yourself. When you substitute in your values for $A_{31}, A_{32}$ and $A_{33}$ do you get the correct recursion?

And, for your next question in post #4, why do you think there is more than one matrix? The matrix $A$ has 9 elements called $A_{11}, A_{12} \ldots, A_{33}$.

6. Jul 26, 2016

### reminiscent

Yes, I do. I just changed the bottom row of A to be the constants of the recursive formula given, but I kept the first 2 rows I stated the same. I verified and got the eigenvalues in b.
I thought there was more than one matrix because in the equations, there are a combination of values for each element in A that can produce the desired elements. But it seems like there will be only one because the eigenvalues have to be verified, correct?

7. Jul 26, 2016

### Ray Vickson

I have no idea what you are saying.

While it is the case that IF you apply the matrix to some smal number of initial values like $x_0=1,x_1=, x_2 =2$ (and a few more obtained from the recursion) you will get numbers on the left and numbers on the right, so will have equations like
$$A_{31}\: \text{number one} + A_{32}\: \text{number two} + A_{33} \:\text{number three} = \text{number four}$$
with actual numbers. Of course you can have many possible values of $A_{31}, A_{32}, A_{33}$ that "work". However, that is irrelevant: you are supposed to find a matrix that works for all values of $x_k, x_{k+1}, x_{k+2}, x_{k+3}$ that you will ever encounter in the calculations (say for $x_{27}, x_{28}, x_{29}, x_{30}$ or for $x_{1000}, x_{1001}, x_{1002}, x_{1003}$, etc.) and when you use that fact there can be only one possible choice for the three numbers $A_{31}, A_{32}, A_{33}$. There is only one matrix $A$.

Last edited: Jul 26, 2016
8. Jul 26, 2016

### Stephen Tashi

You solution for eq. 3 doesn't work. Your solution gives $x_{k+2} = x_{k+3}$.

Yes !

9. Jul 26, 2016