Maths Olympiad Prep

Library / /51 of 377

Algebra Difficulty 4.5 AIME Find the answer United States

Problem:
The Fibonacci numbers are defined by F1=F2=1F_{1} = F_{2} = 1, and Fn=Fn−1+Fn−2F_{n} = F_{n-1} + F_{n-2} for n≥3n \geq 3. If the number
F2003F2002−F2004F2003 \frac{F_{2003}}{F_{2002}} - \frac{F_{2004}}{F_{2003}}
is written as a fraction in lowest terms, what is the numerator?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
Before reducing, the numerator is F20032−F2002F2004F_{2003}^{2} - F_{2002} F_{2004}. We claim Fn2−Fn−1Fn+1=(−1)n+1F_{n}^{2} - F_{n-1} F_{n+1} = (-1)^{n+1}, which will immediately imply that the answer is 11 (no reducing required). This claim is straightforward to prove by induction on nn: it holds for n=2n=2, and if it holds for some nn, then
Fn+12−FnFn+2=Fn+1(Fn−1+Fn)−Fn(Fn+Fn+1)=Fn+1Fn−1−Fn2=−(−1)n+1=(−1)n+2. F_{n+1}^{2} - F_{n} F_{n+2} = F_{n+1}(F_{n-1} + F_{n}) - F_{n}(F_{n} + F_{n+1}) = F_{n+1} F_{n-1} - F_{n}^{2} = -(-1)^{n+1} = (-1)^{n+2}.

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.