big list - 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.