1

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.

Jerome
  • 113
  • 5
    The sequence is determined by the two values $F(0)$ and $F(1)$. – Daniel Fischer Dec 12 '14 at 13:47
  • @Daniel Fischer so are the sequences determined by $F(n+2)=\sin(F(n+1)) + \sin(F(n))$. I don't believe the sets of solutions to this recurrence is a vector space, and so it has no dimension – Jerome Dec 12 '14 at 13:52
  • You can also talk of the dimension of non-vector-spaces, then it is sensible to assign the space of sequences with the $\sin$-recurrence the dimension $2$. But here, we have a vector space, so we can use that concept of dimension. So you have a bijection between the space of the sequences satisfying the recurrence and the pairs $(F(0),F(1))$. Is it linear? – Daniel Fischer Dec 12 '14 at 13:58
  • Indeed. I can determine a linear combination of my 2 geometric sequences that fits $F(0)$ and $F(1)$. Thanks – Jerome Dec 12 '14 at 14:02

1 Answers1

2

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.

mookid
  • 28,236