Calculating how many 2's appear in the last digits of the first 2004 Fibonacci numbers.

Question

I have had some trouble with the following question (It is from the Australian Mathematics Competition). If anyone would be able to produce a solution (with considerable working), that requires no use of calculator or programming software, that would be great.

The Fibonacci numbers are F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, F(7)=13, … where the first two are both equal to 1, and from then on, each one is the sum of the two preceding it. Of the first 2004 Fibonacci numbers, how many have 2 as their last digit?

Answer 1

I’d write down the last digits of the Fibonacci numbers until I see the same sequence of two digits repeat, and then it is easy.

Last digits are 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 7 7 4 ...

The 15/16th numbers have the same last digits as the 44/45th, and there is one number at position 35 with last digit 2. Just check if I counted right. The next numbers with last digit 2 are at 64, 93 and so on. Just a bit of maths now.

Ps Made a mistake but go on with the same principle.

Answer 2

I'll answer both the question in the title, and the one in the actual question, since most of the work is the same.

First, reduce everything modulo $10$. Then our sequence is given by the recurrence relation $F(n) = F(n-1) + F(n-2) \mod 10$. Note that if there are $a\neq b$ such that $F(a) = F(b)$ and $F(a+1) = F(b+1)$, then our sequence necessarily repeats with period $b-a$ thereafter.

So, we need only find such a repetition, which must happen in finite time, because there are only $10^2 = 100$ possible pairs of residues modulo $10$.

Our first few values are:

$1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1, 1$.

Now, notice, we have repeated: $1,1$ appears at both the first and second positions, and the 61st and 62nd. Thus, our pattern repeats in blocks of 60, each of which contain exactly four twos. Thus, the first $1980 = 33\times60$ Fibbonacci numbers modulo $10$ contain $33 \times 4 = 132$ twos. The $24$ after that are $1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8$, so contain one two, and the whole first $2004$ terms contain exactly $133$ twos. To answer the question in your title, the final digit of the $2004$th Fibbonacci number is $8$.