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.
