AlgebraDifficulty 6.2National OlympiadProve itUnited States
Problem: The Fibonacci numbers are defined by F0=0, F1=1, and Fn=Fn−1+Fn−2 for n≥2. There exist unique positive integers n1, n2, n3, n4, n5, n6 such that i1=0∑100i2=0∑100i3=0∑100i4=0∑100i5=0∑100Fi1+i2+i3+i4+i5=Fn1−5Fn2+10Fn3−10Fn4+5Fn5−Fn6 Find n1+n2+n3+n4+n5+n6.
Solution
Solution: We make use of the identity i=0∑ℓFi=Fℓ+2−1 (easily proven by induction) which implies i=k∑ℓFi=Fℓ+2−Fk+1 Applying this several times yields =====i1=0∑100i2=0∑100i3=0∑100i4=0∑100i5=0∑100Fi1+i2+i3+i4+i5i1=0∑100i2=0∑100i3=0∑100i4=0∑100(Fi1+i2+i3+i4+102−Fi1+i2+i3+i4+1)i1=0∑100i2=0∑100i3=0∑100(Fi1+i2+i3+204−2Fi1+i2+i3+103+Fi1+i2+i3+2)i1=0∑100i2=0∑100(Fi1+i2+306−3Fi1+i2+205+3Fi1+i2+104−Fi1+i2+3)i1=0∑100(Fi1+408−4Fi1+307+6Fi1+206−4Fi1+105+Fi1+4)F510−5F409+10F308−10F207+5F106−F5. This representation is unique because the Fibonacci terms grow exponentially quickly, so e.g. the F510 term dominates, forcing n1=510 and similarly for the other terms. The final answer is 510+409+308+207+106+5=1545
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.