Your approach to prove a [theorem][1] usually depends on how you define things. As [Elaqqad][2] said, you can't get rid of induction when you define the Fibonacci sequence by Induction. But if you define Fibonacci sequence from the start with no induction, you can prove some of its features without induction.

I usually suggest to be pragmatic, and accept [mathematical induction][3]. But, as you wish, I _DO_ prove **Fibonacci sequence is periodic mod 5 without using induction**.

Let's start from a non-inductive definition of Fibonacci sequence. I use [Binet's formula][4], as a [closed-form expression of the Fibonnaci number][5].

Fibonnaci number is defined as a function of $n$, which outputs an _Integer_, and defined as\*:

$F[n] := \cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\cfrac{1}{\sqrt{5}}\cdot\left(\cfrac{1-\sqrt{5}}{2}\right)^n$

We are about to show $$F_{n}\equiv F_{n+20}\pmod 5$$ for all $n \geq 2$

Actually, we also calculate the reminder. We prove that:

$F[n+20]-F[n]=10945.F[n]+6765F[n−1]$

Doing this is really cumbersome. You can't do this by hand, but using a computational software program like Mathematica as a form of **[Automated theorem proving][6]** you can do it easily:

Define the functions as above statement, and do this in Mathematica:

    Simplify[f[n + 20] - f[n] - 10945 f[n] - 6765 f[n - 1]]

and you get exact **zero**:

    0

which compeltes the proof.

I'm trying to extract the exact intermediatory simplifying steps from Mathematica. I'll post it as soon as I get it.

\* I am not going to prove that F(n) is actually an integer here.


  [1]: https://en.wikipedia.org/wiki/Theorem
  [2]: http://math.stackexchange.com/users/204937/elaqqad
  [3]: https://en.wikipedia.org/wiki/Mathematical_induction
  [4]: https://en.wikipedia.org/wiki/Jacques_Philippe_Marie_Binet
  [5]: https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression
  [6]: https://en.wikipedia.org/wiki/Automated_theorem_proving