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.


  • 1
    $\begingroup$ Oh I get you. Your "$x$"s are different but your $a,b$ are same across all sequences. $\endgroup$ – 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).)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.