Maths Olympiad Prep

Library / HMMT February /303 of 1302

HMMT February

Algebra Difficulty 5.0 AIME, harder Find the answer

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

Before reducing, the numerator is F20032−F2002F2004F_{2003}^{2}-F_{2002} F_{2004}. We claim Fn2−Fn−1Fn+1=F_{n}^{2}-F_{n-1} F_{n+1}= (−1)n+1(-1)^{n+1}, which will immediately imply that the answer is 1 (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}\left(F_{n-1}+F_{n}\right)-F_{n}\left(F_{n}+F_{n+1}\right)=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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.