Existence of a Fibonacci number divisible by $10^n$

Question

Prove that for any given positive integer $n$,there exists a Fibonacci number divisible by $10^n$.

Another application of pigeon hole principle,and the main problem is finding the holes and pigeons.If we consider $10^n+1$ consecutive Fibonacci numbers,we can NOT claim that one of them is certainly divisible by $10^n$,but of course two of them have equal remainders mod $10^n$.
I DO KNOW this question has an elementary solution using pigeon hole principle,although the older question asked for $n=2014$ has received many advanced solutions.

Answer 1

Three hints:

1. Make your pigeonholes pairs of remainders module $10^n$.
2. If you know that $F_m=F_n \mod 10^n$ and $F_{m+1}=F_{n+1}\mod 10^n$ then you can work backwards in the sequence to show that $F_{m-1}=F_{n-1} \mod 10^n$.
3. Use the fact that $F_0=0$.