Maths Olympiad Prep

Library / /9 of 18

Algebra Difficulty 4.5 AIME Find the answer United States

The Fibonacci numbers are defined by F1=1F_1 = 1, F2=1F_2 = 1, and Fn=Fn1+Fn2F_n = F_{n-1} + F_{n-2} for n3n \ge 3. What is
F2F1+F4F2+F6F3++F20F10? \frac{F_2}{F_1} + \frac{F_4}{F_2} + \frac{F_6}{F_3} + \dots + \frac{F_{20}}{F_{10}}?

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

Solution

The Fibonacci sequence starts out 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, \ldots
so the given sum is
11+31+82+213+555+1448+37713+98721+258434+676555, \frac{1}{1} + \frac{3}{1} + \frac{8}{2} + \frac{21}{3} + \frac{55}{5} + \frac{144}{8} + \frac{377}{13} + \frac{987}{21} + \frac{2584}{34} + \frac{6765}{55},
which equals 1+3+4+7+11+18+29+47+76+123=3191 + 3 + 4 + 7 + 11 + 18 + 29 + 47 + 76 + 123 = 319.

The Fibonacci sequence starts out 1,1,2,3,5,8,13,21,34,551, 1, 2, 3, 5, 8, 13, 21, 34, 55, so the given sum starts out
11+31+82+213+555=1+3+4+7+11. \frac{1}{1} + \frac{3}{1} + \frac{8}{2} + \frac{21}{3} + \frac{55}{5} = 1 + 3 + 4 + 7 + 11.

It appears that these summands satisfy the same recurrence relation, namely
F2nFn=F2(n1)Fn1+F2(n2)Fn2. \frac{F_{2n}}{F_n} = \frac{F_{2(n-1)}}{F_{n-1}} + \frac{F_{2(n-2)}}{F_{n-2}}.

To prove the identity for (LnL_n) displayed above, recall Binet's formula, Fn=15(ϕnψn)F_n = \frac{1}{\sqrt{5}}(\phi^n - \psi^n), where ϕ=1+52\phi = \frac{1+\sqrt{5}}{2} and ψ=152\psi = \frac{1-\sqrt{5}}{2} are the roots of the polynomial x2x1x^2 - x - 1. Then
Ln=F2nFn=ϕ2nψ2nϕnψn=ϕn+ψn. L_n = \frac{F_{2n}}{F_n} = \frac{\phi^{2n} - \psi^{2n}}{\phi^n - \psi^n} = \phi^n + \psi^n.
Therefore

Ln1+Ln2=ϕn1+ϕn2+ψn1+ψn2=ϕn2(ϕ+1)+ψn2(ψ+1)=ϕn2ϕ2+ψn2ψ2=ϕn+ψn=Ln.\begin{align*} L_{n-1} + L_{n-2} &= \phi^{n-1} + \phi^{n-2} + \psi^{n-1} + \psi^{n-2} \\ &= \phi^{n-2}(\phi + 1) + \psi^{n-2}(\psi + 1) \\ &= \phi^{n-2} \cdot \phi^2 + \psi^{n-2} \cdot \psi^2 \\ &= \phi^n + \psi^n = L_n. \end{align*}

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.