Basis for recurrence relation solutions

Question

So, I have a question: Imagine a recurrence relation $U(n+2) = 2U(n+1) + U(n)$. How do I determine the dimension (and the vectors that constitute the basis) of a vector space which contains all sequences that satisfy that rule?

Answer 1

The sequences that result from such a recurrence relation are determined by the initial conditions, which would ordinarily be prescribed as $U(0)$ and $U(1)$. It should be clear that any values can be assigned for these first two values, and that once that is done the rest of the sequence is fully determined by repeated application of the recurrence relation.

It follows that the dimension of the vector space you define (all sequences satisfying the rule) is exactly two, and a basis may be given (for example) by the respective two sequences that correspond to:

$$ U_1(0) = 0, U_1(1) = 1 $$

$$ U_2(0) = 1, U_2(1) = 0 $$

In other words, it is obvious that sequences $U_1,U_2$ so developed are linearly independent, and further that any sequence satisfying the recurrence relation may be expressed as a linear combination of these two (to fit the required initial conditions).