Prove that the set of solutions to $F_{n+2} = F_{n+1} + F_n$ is of dimension 2

Question

I was playing with the Fibonacci sequence, willing to prove that $$ F(n) = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right) $$

I did the usual, looking for geometric sequences satisfying the recurrence, and while I could find the 2 sequences that generate all the solution, I found myself unable to prove that those two solutions were enough to generates all of the other.

So, how to prove that they are sufficient, ie. the set of solutions is of dimension 2 ?

If possible, I'd like the proof with only basic linear algebra. If I remember correctly, there is an ab absurdo proof to it.

Answer 1

The application $F(u) = (u(0), u(1))$ is linear from the set $X$ of solutions of the Fibonacci equation to $\Bbb R^2$. It is injective, as $$ F(u) = 0 \implies u(1) = u(0) = 0 \implies \forall n\ge 0\ \ u(n) = 0 \implies u=0 $$ so $$ \text{dim }X\le \text{dim }\Bbb R^2 = 2 $$

---

A general proof that $\text{dim }X\ge 2$ (that is, generalizable to linear recursive sequences) is based on a linear algebra theorem:

if $B:E\to E$ is linear and that $F = P(B)$, with a polynomial $P = \prod_i P_i$ such as the $P_i$s are relatively prime, then $\ker F = \bigoplus \ker P_i(B)$.

Here, use $E = \Bbb R ^\Bbb N$, $B(u)(n) = u(n+1)$, $P(t) = t^2 - t - 1 = (t-\phi)(t-\hat \phi)$. You get

$$ X = \ker F = \ker (B -\phi I)\oplus \ker (B -\hat\phi I) $$ of dimension 2.