Prove that for a Fibonnaci sequence $f(5n)$ is divisible by $5$ for all $n$. 
QUESTION: Let $f:\mathbb{N}→\mathbb{N}$ be the function defined by $f(0)=0$ ,$f(1)=1$ and $f(n)=f(n-1)+f(n-2)$ for all $n≥2$ , where $\mathbb{N}$ is the set of all non negative integers. Prove that $f(5n)$ is divisible by $5$ for all $n$.

MY ANSWER: It's clear that this is a Fibonacci sequence which goes like$→$
$0,1,1,2,3,5,8,13,21,.......$
Now intuitively, we can see that $f(5n)$ is congruent to $0(mod 5)$. But how do I rigorously prove the same?
Any help is much appreciated. 
Thank you.
 A: Use$$f_{5k+5}=f_{5k+4}+f_{5k+3}=2f_{5k+3}+f_{5k+2}=3f_{5k+2}+2f_{5k+1}=5f_{5k+1}+3f_{5k},$$so $5|f_{5k}\implies5|f_{5k+5}$.
A: The Fibonacci recurrence relation holds modulo $5$ as well: You get one term by adding the two previous terms. Let's see what it looks like modulo $5$:
$$
1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, \ldots
$$
We see that after each $0$, we get the same pattern: $0, a, a, 2a, 3a, 0$, for some $a$. This follows directly from the recurreence relation: After a $0$ there must be two identical terms, as the second $a$ is just $a+0$. After that must come $a+a = 2a$, then $a+2a = 3a$, and finally $2a+3a = 5a = 0$, bringing us back into another loop of the same pattern.
A: Here's another way to look at the problem.  The next number is in the Fibonacci sequence is determined by the previous two; you don't need to know its entire history.  If you are working modulo $n$ then the number of possible states is $n^2$.  You have a finite state machine.  In your case, you are working modulo $5$ so $25$ states.  You can map the transitions easily.  
State $(0, 0)$ is dull it just stays where it is.  
Starting at the usual state $(0, 1)$ gives this loop:
$$(0,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (2,3) \rightarrow (3,0)$$
$$\rightarrow (0,3) \rightarrow (3,3) \rightarrow (3,1) \rightarrow (1,4) \rightarrow (4,0)$$
$$\rightarrow (0,4) \rightarrow (4,4) \rightarrow (4,3) \rightarrow (3,2) \rightarrow (2,0)$$
$$\rightarrow (0,2) \rightarrow (2,2) \rightarrow (2,4) \rightarrow (4,1) \rightarrow (1,0)$$
which then repeats.  This is just Arthur's answer in a slightly different format.  
That's $20$ states in a loop.  Together with the trivial loop of $(0,0)$, that's $21$ states and there must be $4$ that did not occur.  These form a loop.  
$$(1,3) \rightarrow (3,4) \rightarrow (4,2) \rightarrow (2,1)$$
Similarly, you will find loops for any modulus but it is kind of a coincidence that every 5th Fibonacci number is a multiple of $5$.  For example, work in modulus $2$ and you get a loop of $3$ not $2$.  Every second number is not even.  The pattern is odd, odd, even.  In modulus $3$, you get a loop of $8$ states so not every 3rd is a multiple of $3$.  
A little searching found this which looks interesting but I have not fully read it yet: The Period of the Fibonacci Sequence Modulo j.
A: Proof using induction.
For the Base Case we have
$$f_{5}=f_{5-1}+f_{5-2}=f_{4}+f_{3}=3+2=5\equiv0\pmod{5}$$
so the theorem holds for $n=1$.
Now you can use the recurrence directly on  $f_{5n}$ to prove this holds in general for all $n\ge1$.
Now for the induction: Assume for some $k\in\mathbb{N}$ that $5$ divides $f_{5k}$. Hence
\begin{align}
f_{5k}&=f_{5k-1}+f_{5k-2}\\
&= f_{5(k-1)+4}+f_{5(k-1)+3} \equiv0\pmod{5}
\end{align}
Now look at the $k+1$ case:
\begin{align}
f_{5(k+1)}&=f_{5(k+1)-1}+f_{5(k+1)-2}\\
&= f_{5k+4}+f_{5k+3}\\ 
&= (f_{5k+3}+f_{5k+2})+(f_{5k+2} +f_{5k+1})\\
&= f_{5k+3}+2f_{5k+2}+f_{5k+1}\\
&= 3f_{5k+2}+2f_{5k+1}\\
&= 3f_{5k+1}+3f_{5k}+2f_{5k+1}\\
&= 5f_{5k+1}+3f_{5k}\equiv0\pmod{5}
\end{align}
which holds true since by the inductive hypothesis we assumed $5\mid f_{5k}$.
