Proof: Let n = 5k for k = 0, 1, 2, 3, … For k =0, F(0) = 0 which is divisible by 5. For k=1, F(5) = 5 which is also divisible by 5.
Assume that F(5k) is divisible by 5 for a positive integer k. F(5(k+1)) = F(5k+5) = F(5k+4) + F(5k+3) = F(5k+3) + F(5k+2) + F(5k+3) = 2F(5k+3) + F(5k+2) = 3F(5k+2) + 2F(5k+1) = 5F(5k+1) + 3F(5k)
Since F(5k) and 5F(5k+1) are divisible by 5, F(5(k+1)) is also divisible by 5. Therefore, by induction, we can say that every 5kth element of the Fibonacci sequence is divisible by 5.