Maths Olympiad Prep

Library / Singapur /19 of 23

Singapur, 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=fn−1+fn−2f_n = f_{n-1} + f_{n-2} if n≥2n \ge 2. Determine all possible positive integers nn so that there is a positive integer aa such that fn≤a≤fn+1f_n \le a \le f_{n+1} and that
a(1f1+1f1f2+1f1f2f3+⋯+1f1f2…fn) 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
af1⋯fn(f2⋯fn+f3⋯fn+⋯+fn−2fn−1fn+fn−1fn+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
fn∣a(f2⋯fn+f3⋯fn+⋯+fn−2fn−1fn+fn−1fn+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 fn∣af_n|a. First consider the case where n≥2n \ge 2. Then
fn≤a≤fn+1<2fn. f_n \le a \le f_{n+1} < 2f_n.
Hence a=fna = f_n. Then
1f1⋯fn−1(f2⋯fn+f3⋯fn+⋯+fn−2fn−1fn+fn−1fn+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 fn−1∣1f_{n-1}|1. Hence n−1=0n-1=0 or 11. This shows that the only possible values of nn are 1 and 2.
For n=1n=1, 1=f1≤1≤f21=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, f2≤2≤f3f_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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.