DE-MO 2001 Problem 5

The Fibonacci sequence is given by $x_1 = x_2 = 1$ and $x_{k+2} = x_{k+1} + x_k$ for each $k \in N$ . (a) Prove that there are Fibonacci numbes that end in a $9$ in the decimal system. (b) Determine for which $n$ can a Fibonacci number end in $n$ $9$ -s in the decimal system.