# Predicting future numbers in a sequence, using linear algebra,

We have several sequences, $x_k$, that satisfy the recurrence relation

$$x_{k+1} = a_kx_k + b_kx_{k-1} + x_{k-2}.$$

We do not know the numbers $a_k$ or $b_k$, but they are the same for each sequence. Parts of two of the sequences we have are listed below:

Sequence number 1: $x_1$ = 2, $x_2$ = 0, $x_3$ = 3 ... $x_8$ = 2

Sequence number 2: $x_1$ = 1, $x_2$ = 1, $x_3$ = 2 ... $x_8$ = 1

For example, the first sequence has $x_1$ = 2, $x_2$ = 0, etc. We want to be able to predict the numbers $x_8$, $x_9$, $x_{10}$ from $x_1$, $x_2$, and $x_3$.

a) Which of the following sequences has the information to do this? Explain what happens in both cases.

Sequence number 3: $x_1$ = 0, $x_2$ = 2, $x_3$ = 1 ... $x_8$ = 0

Sequence number 4: $x_1$ = 1, $x_2$ = 2, $x_3$ = 1 ... $x_8$ = 0

b) Using the correct sequence from part (a), find $x_8$ in the sequence that starts with $x_1$ =0, $x_2$ = 3, $x_3$ = 0.

EDIT: I posted an answer for part(a). Feel free to comment on my work.

Thanks,

• Oh I get you. Your "$x$"s are different but your $a,b$ are same across all sequences. – user21820 Aug 16 '15 at 5:56

For part(a):

We can consider a linear operator T: $R^3$->$R^{10}$, where T's domain of definition is the space of $x_1, x_2, x_3$. I.e., T takes as inputs the first three terms of any sequence and returns a ten-term sequence. The initial space is then 3-dimensional, and the image space $T(R^3)$ is again 3-dimensional - a three-dimensional subspace of $R^{10}$. Together with the recurrence relation, T is a one-to-one mapping.

We find a basis for the initial space, which will then give a basis for $T(R^3)$, which then gives us enough information to determine $x_8$, $x_9$, and $x_{10}$, from $x_1, x_2, x_3$, for each sequence.

Now, observe that $v_1$ = (2,0,3) and $v_2$= (1,1,2), from sequences 1 and 2, respectively, are linearly independent vectors in $R^3$. (0,2,1), from sequence 3, is linearly dependent on $v_1$ and $v_2$, while (1,2,1), from sequence 4, is linearly independent, easily verified with row reduction. Call this vector $v_3$.

Thus, sequence 4 gives us enough information. And the set $(T(v_1), T(v_2), T(v_3))$ forms a basis for the image space, $T(R^3)$.

Feel free to comment on my answer.

(I'm not sure how to proceed for part(b).)

• Correct approach. For part (b) just find a linear combination of sequences 1,2,4 that begins (0,3,0,...) – user21820 Aug 16 '15 at 5:57