Maths Olympiad Prep

Library / /26 of 39

Algebra Difficulty 5.7 AIME, harder Find the answer Italy

Problem:

The sequence of Fibonacci numbers F1,F2,,Fn,F_{1}, F_{2}, \ldots, F_{n}, \ldots is such that F1=F2=1F_{1}=F_{2}=1 and the n-th term ( n3n \geq 3 ) is the sum of the two preceding ones (the first terms of the sequence are thus F1=1,F2=1,F3=2=1+1,F4=3=2+1,F5=5=3+2F_{1}=1, F_{2}=1, F_{3}=2=1+1, F_{4}=3=2+1, F_{5}=5=3+2 ). How many Fibonacci numbers have exactly 2016 digits in their decimal representation?
(A) At least 2 and at most 3
(B) At least 4 and at most 5
(D) At least 8 and at most 9
(E) 10 or more
(C) At least 6 and at most 7

This was a multiple-choice question, but the options didn't survive into the source we have. The answer given is B, and the solution below works it through.

Solution

Solution:

The answer is (B)\mathbf{( B )}. First observe that (for n2n \geq 2 ) the relation Fn+1=Fn+Fn1F_{n+1}=F_{n}+F_{n-1}, together with the fact that Fn1FnF_{n-1} \leq F_{n}, implies that FnF_{n} is at least half of Fn+1F_{n+1}. Now let k1k \geq 1 and let FnF_{n} be the smallest Fibonacci number with k+1k+1 decimal digits (hence Fn10kF_{n} \geq 10^{k} ). We have Fn11210kF_{n-1} \geq \frac{1}{2} \cdot 10^{k} and therefore Fn+1=Fn+Fn1(1+12)10kF_{n+1}=F_{n}+F_{n-1} \geq\left(1+\frac{1}{2}\right) \cdot 10^{k}. Proceeding in the same way we successively obtain the inequalities Fn+2(32+1)10k,Fn+3(52+32)10k,Fn+4(4+52)10kF_{n+2} \geq\left(\frac{3}{2}+1\right) \cdot 10^{k}, F_{n+3} \geq\left(\frac{5}{2}+\frac{3}{2}\right) 10^{k}, F_{n+4} \geq\left(4+\frac{5}{2}\right) \cdot 10^{k} and Fn+5(132+4)10k>10k+1F_{n+5} \geq\left(\frac{13}{2}+4\right) \cdot 10^{k}>10^{k+1}, from which we see that Fn+5F_{n+5} has at least k+2k+2 decimal digits.

On the other hand, by definition we have Fn2Fn1<10kF_{n-2} \leq F_{n-1}<10^{k}, from which we successively obtain Fn<210k,Fn+1<310k,Fn+2<510k,Fn+3<810kF_{n}<2 \cdot 10^{k}, F_{n+1}<3 \cdot 10^{k}, F_{n+2}<5 \cdot 10^{k}, F_{n+3}<8 \cdot 10^{k}, so Fn+3F_{n+3} still has k+1k+1 decimal digits. In conclusion, given any number k2k \geq 2, there are at least 4 and at most 5 Fibonacci numbers with kk digits.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.