What is the dimension of this vector space (sub space)? Given the vector space
$U:=\{f:\mathbb{N}\rightarrow\mathbb{R}:f(n)=f(n-1)+f(n-2)$ for $n \geq 3\}$
which is a sub space of
$V:=\{f:\mathbb{N}\rightarrow\mathbb{R}\}$

The dimension of the sub space $U$ is 2, supposedly.
But why 2? How do I have to start to get the dimension?
 A: Let's first just play around for a while.
Take any $f\in U$. Then, say you know what $f(1)$ and $f(2)$ are. From that, you can calculate $f(3)=f(1)+f(2)$, and from that, you can calculate $f(4)=f(2)+f(3)$ and so on.
OK, now can we generalize this? Is it true that a function in $U$ is uniquely defined by its first two points? That is, can we prove the statement:

If $f_1, f_2\in U$, and if $f_1(1)=f_2(1)$ and $f_1(2)=f_2(2)$, then $f_1=f_2$


Once you have that, you can go one of two ways:


*

*it should be relatively simple to find a very natural bijection from $U$ to $\mathbb R^2$, and to show that it is actually an isomorphism (i.e. that it is bijective and linear)

*You could also find a basis for $U$ by looking at interesting functions from $U$. Remember, you only need to focus on $f(1)$ and $f(2)$, everything else is uniquely determined by those two numbers!

A: I'm assuming you've already proved this is, in fact, a vector subspace of $\mathbb{R}^{\mathbb{N}}$. You can now consider the basis $\{\phi_1, \phi_2\}$ where
$$
\phi_1(1) = 1, \phi_1(2) = 0, \phi_1(n) = \phi_1(n-1) + \phi_1(n-2) \ \forall n >  2
$$
$$
\phi_2(1) = 0, \phi_2(2) = 1, \phi_2(n) = \phi_2(n-1) + \phi_2(n-2) \ \forall n >  2
$$
Now, if $f \in U$, I claim that $f \equiv f(1)\phi_1 + f(2)\phi_2$. 
Let's prove it by induction. If $n = 1 $ or $ n = 2$ this is trivial. Now, assuming that $n > 2$ and $f(m) = f(1)\phi_1(m) + f(2)\phi_2(m) \ (\forall m < n)$,
$$
f(n) = f(n-1) + f(n-2) = \\f(1)\phi_1(n-1) + f(2)\phi_2(n-1) + f(1)\phi_1(n-2) + f(2)\phi_2(n-2) = \\ f(1)(\phi_1(n-1) + \phi_1(n-2) ) + f(2)(\phi_2(n-1) + \phi_2(n-2)) = \\f(1)\phi_1(n) + f(2)\phi_2(n)
$$
The linear independence of  $\{\phi_1, \phi_2\}$ is given by the following fact: suppose that  $a\phi_1 + b\phi_2 \equiv 0$. Then,
$$
a = a\phi_1(1) + b\phi_2(1) = 0 \\
b = a\phi_1(2) + b\phi_2(2) = 0
$$ 
This proves that $\{\phi_1, \phi_2\}$ is a basis for $U$ and therefore $dim(U) = 2$.
