Nontrivial question about Fibonacci numbers?

Here you have some of the coolest ones I have heard of:

1) Let $a$ be a positive integer. Then $a$ is a Fibonacci number if and only if at least one member of the set {$5a^{2}-4, 5a^{2}+4$} is a perfect square.

I think the result is original with Prof. Ira Gessel.

2) Let $\phi$ denote the Euler totient function. Prove that $\phi(F_{n}) \equiv 0 \pmod{4}$ if $n \geq 5$.

The proof consists of an unexpected application of Lagrange's theorem in Group Theory. Guess there are some other ways to prove it, but that approach will always remain my cup of tea. The problem was posed and solved in the Monthly in the 70's (if my memory serves me right). Look for all entries by Clark Kimberling in that magazine and you'll surely find it.

3) Can you find $(a,b,c) \in \mathbb{N}^{3}$ such that $ 2 < a < b < c$ and $F_{a} \cdot F_{b} = F_{c}$?

This problem would be trivial if instead of the $\cdot$ we had placed a plus sign there. In any case, there is no need to panic with this proposal. All you need to recall is the corresponding primitive divisor theorem.

4) Ben Linowitz mentioned above a beautiful result by Professor Florian Luca, namely:

There aren't any perfect numbers in the Fibonacci sequence.

I read the paper in my junior year and I didn't find it that hard to follow. The easy part of this cute note resides in the proof of the fact that there are no even perfect numbers in the Fibonacci sequence. Guess this result is interesting enough to deserve consideration in those lectures that you intend to give. If this proposal is not exactly your idea of excitement, you can take a look at some of the other papers by Professor Florian. He writes a lot about recurrence sequences. Another theorem of his, closely related with the subject matter of this discussion, ascertains that

There is no non-abelian finite simple group whose order is a Fibonacci number.

5) Last but not least... Prove that the sequence {$F_{n+1}/F_{n}$}$_{n \in \mathbb{N}}$ converges and use this fact to derive the continued fraction development for the golden ratio.

This one should be well-known, yet it would be nice to see what your students come up with...

Added (Nov 20/2010) I've just noticed that the Fibonacci Assn. has made available the articles published in The Fibonacci Quarterly between 1963 and 2003. I'm sure you will find plenty of additional material among those files that they have so generously released for our enjoyment. For instance, the seminal paper by J. H. E. Cohn that K. Buzzard mentions below can be found here.

An accessible (and interesting) thing to look at with Fibonacci numbers is their periodicity modulo various integers, especially primes and prime powers. One example of an accessible result is that if $k(p)$ is the period of the Fibonacci numbers modulo a prime $p$, then $k(p)\mid p^2-1$. You can get sharper results by examining whether or not 5 is a quadratic residue mod $p$ (think of the importance of $\frac{1\pm\sqrt{5}}{2}$ to the Fibonacci numbers). You can prove things about this periodicity directly, or reduce the 2x2 matrix which Gowers mentions modulo $p$ and get the same thing, depending on what you'd like to emphasize to your students. Some good resources for this subject are

http://en.wikipedia.org/wiki/Pisano_period

http://euclid.math.temple.edu/~renault/fibonacci/fib.html

Another neat thing about the Fibonacci numbers is their appearance as sums of "diagonals" in Pascal's Triangle, as in this picture:

However, this fact is provable simply by induction, so maybe this is too easy for what you have in mind.

In 1964 J. H. E. Cohn proved that the largest square in the Fibonacci sequence was 144. The proof uses standard facts about squares mod $p$, up to and including quadratic reciprocity, in an ingenious way. It's MR0163867 at Math Reviews if you want to chase this up. This is one of those proofs that you can easily read and understand, but it would be a devil to discover yourself. I have given this problem to undergraduates as a super-long exercise with hints.