Finding a Basis for the Vector space of sequences of the form $u_{n+1} = u _{n-1} + u_n$?

Question

The question asks to show that the set of real sequences $u_n$ satisfying the recurrence $u_{n+1} = u_n + u_{n-1}$ is a subspace of the space of all real sequences and then to find its basis.

To show that the set is a subspace I used the subspace test, but I had a problem finding the basis.

Here's how far I have got:

Any $u_n$ satisfying the recurrence $u_{n+1} = u_n + u_{n-1}$ could be expressed as a linear combination of $u_0$ and $u_1$ $$u_n = \lambda u_0 + \mu u_1$$ so to find the basis for this subspace, all we need to do is find the basis of $R^2$, which is $(1,0), (0,1)$.

Is that the right way to approach the question?

Thanks!

Answer 1

What you did is correct. You have proved that your vector space is spanned by the Fibonacci sequence $0,1,1,2,3,5,8,\ldots$ and by a similar one: $1,0,1,1,2,3,5,\ldots$ Since they are linearly independent, your space has dimension $2$, and these two sequences form a basis of it.