Maths Olympiad Prep

Library / HMMT February /1201 of 1302

HMMT February

Algebra Difficulty 6.0 AIME, harder Find the answer

The Fibonacci numbers are defined by F0=0,F1=1F_{0}=0, F_{1}=1, and Fn=Fn−1+Fn−2F_{n}=F_{n-1}+F_{n-2} for n≥2n \geq 2. There exist unique positive integers n1,n2,n3,n4,n5,n6n_{1}, n_{2}, n_{3}, n_{4}, n_{5}, n_{6} such that ∑i1=0100∑i2=0100∑i3=0100∑i4=0100∑i5=0100Fi1+i2+i3+i4+i5=Fn1−5Fn2+10Fn3−10Fn4+5Fn5−Fn6\sum_{i_{1}=0}^{100} \sum_{i_{2}=0}^{100} \sum_{i_{3}=0}^{100} \sum_{i_{4}=0}^{100} \sum_{i_{5}=0}^{100} F_{i_{1}+i_{2}+i_{3}+i_{4}+i_{5}}=F_{n_{1}}-5 F_{n_{2}}+10 F_{n_{3}}-10 F_{n_{4}}+5 F_{n_{5}}-F_{n_{6}}. Find n1+n2+n3+n4+n5+n6n_{1}+n_{2}+n_{3}+n_{4}+n_{5}+n_{6}.

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

Solution

We make use of the identity ∑i=0ℓFi=Fℓ+2−1\sum_{i=0}^{\ell} F_{i}=F_{\ell+2}-1 (easily proven by induction) which implies ∑i=kℓFi=Fℓ+2−Fk+1\sum_{i=k}^{\ell} F_{i}=F_{\ell+2}-F_{k+1}. Applying this several times yields ∑i1=0100∑i2=0100∑i3=0100∑i4=0100∑i5=0100Fi1+i2+i3+i4+i5=∑i1=0100∑i2=0100∑i3=0100∑i4=0100(Fi1+i2+i3+i4+102−Fi1+i2+i3+i4+1)=∑i1=0100∑i2=0100∑i3=0100(Fi1+i2+i3+204−2Fi1+i2+i3+103+Fi1+i2+i3+2)=∑i1=0100∑i2=0100(Fi1+306−3Fi1+205+3Fi1+104−Fi1+3)=∑i1=0100(Fi1+408−4Fi1+307+6Fi1+206−4Fi1+105+Fi1+4)=F510−5F409+10F308−10F207+5F106−F5\sum_{i_{1}=0}^{100} \sum_{i_{2}=0}^{100} \sum_{i_{3}=0}^{100} \sum_{i_{4}=0}^{100} \sum_{i_{5}=0}^{100} F_{i_{1}+i_{2}+i_{3}+i_{4}+i_{5}} = \sum_{i_{1}=0}^{100} \sum_{i_{2}=0}^{100} \sum_{i_{3}=0}^{100} \sum_{i_{4}=0}^{100}\left(F_{i_{1}+i_{2}+i_{3}+i_{4}+102}-F_{i_{1}+i_{2}+i_{3}+i_{4}+1}\right) = \sum_{i_{1}=0}^{100} \sum_{i_{2}=0}^{100} \sum_{i_{3}=0}^{100}\left(F_{i_{1}+i_{2}+i_{3}+204}-2 F_{i_{1}+i_{2}+i_{3}+103}+F_{i_{1}+i_{2}+i_{3}+2}\right) = \sum_{i_{1}=0}^{100} \sum_{i_{2}=0}^{100}\left(F_{i_{1}+306}-3 F_{i_{1}+205}+3 F_{i_{1}+104}-F_{i_{1}+3}\right) = \sum_{i_{1}=0}^{100}\left(F_{i_{1}+408}-4 F_{i_{1}+307}+6 F_{i_{1}+206}-4 F_{i_{1}+105}+F_{i_{1}+4}\right) = F_{510}-5 F_{409}+10 F_{308}-10 F_{207}+5 F_{106}-F_{5}. This representation is unique because the Fibonacci terms grow exponentially quickly, so e.g. the F510F_{510} term dominates, forcing n1=510n_{1}=510 and similarly for the other terms. The final answer is 510+409+308+207+106+5=1545510+409+308+207+106+5=1545.

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.