Maths Olympiad Prep

Library / /23 of 27

, 2015

Number theory Difficulty 6.2 National Olympiad Prove it Singapore

Let f0,f1,f_0, f_1, \dots be the Fibonacci sequence: f0=f1=1f_0 = f_1 = 1, fn=fn1+fn2f_n = f_{n-1} + f_{n-2} if n2n \ge 2. Determine all possible positive integers nn so that there is a positive integer aa such that fnafn+1f_n \le a \le f_{n+1} and that
a(1f1+1f1f2+1f1f2f3++1f1f2fn) a\left(\frac{1}{f_1} + \frac{1}{f_1f_2} + \frac{1}{f_1f_2f_3} + \dots + \frac{1}{f_1f_2\dots f_n}\right)
is an integer.

Solution

The number may be rewritten as
af1fn(f2fn+f3fn++fn2fn1fn+fn1fn+1). \frac{a}{f_1 \cdots f_n} (f_2 \cdots f_n + f_3 \cdots f_n + \cdots + f_{n-2}f_{n-1}f_n + f_{n-1}f_n + 1).
If this is an integer, then
fna(f2fn+f3fn++fn2fn1fn+fn1fn+1). f_n|a(f_2 \cdots f_n + f_3 \cdots f_n + \cdots + f_{n-2}f_{n-1}f_n + f_{n-1}f_n + 1).
Thus fnaf_n|a. First consider the case where n2n \ge 2. Then
fnafn+1<2fn. f_n \le a \le f_{n+1} < 2f_n.
Hence a=fna = f_n. Then
1f1fn1(f2fn+f3fn++fn2fn1fn+fn1fn+1) \frac{1}{f_1 \cdots f_{n-1}} (f_2 \cdots f_n + f_3 \cdots f_n + \cdots + f_{n-2}f_{n-1}f_n + f_{n-1}f_n + 1)
is an integer. Thus fn11f_{n-1}|1. Hence n1=0n-1=0 or 11. This shows that the only possible values of nn are 1 and 2.
For n=1n=1, 1=f11f21=f_1 \le 1 \le f_2 and a/f1=1/1=1a/f_1 = 1/1 = 1 is an integer.
For n=2n=2, f22f3f_2 \le 2 \le f_3 and
2(1f1+1f1f2)=2(1+12) 2\left(\frac{1}{f_1} + \frac{1}{f_1 f_2}\right) = 2\left(1 + \frac{1}{2}\right)
is an integer.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.