Maths Olympiad Prep

Library / /1358 of 1394

, 2020

Algebra Difficulty 6.2 National Olympiad Prove it United States

Problem:
The Fibonacci numbers are defined by F0=0F_{0}=0, F1=1F_{1}=1, and Fn=Fn1+Fn2F_{n}=F_{n-1}+F_{n-2} for n2n \geq 2. There exist unique positive integers n1n_{1}, n2n_{2}, n3n_{3}, n4n_{4}, n5n_{5}, n6n_{6} such that
i1=0100i2=0100i3=0100i4=0100i5=0100Fi1+i2+i3+i4+i5=Fn15Fn2+10Fn310Fn4+5Fn5Fn6 \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}.

Solution

Solution:
We make use of the identity
i=0Fi=F+21 \sum_{i=0}^{\ell} F_{i}=F_{\ell+2}-1
(easily proven by induction) which implies
i=kFi=F+2Fk+1 \sum_{i=k}^{\ell} F_{i}=F_{\ell+2}-F_{k+1}
Applying this several times yields
i1=0100i2=0100i3=0100i4=0100i5=0100Fi1+i2+i3+i4+i5=i1=0100i2=0100i3=0100i4=0100(Fi1+i2+i3+i4+102Fi1+i2+i3+i4+1)=i1=0100i2=0100i3=0100(Fi1+i2+i3+2042Fi1+i2+i3+103+Fi1+i2+i3+2)=i1=0100i2=0100(Fi1+i2+3063Fi1+i2+205+3Fi1+i2+104Fi1+i2+3)=i1=0100(Fi1+4084Fi1+307+6Fi1+2064Fi1+105+Fi1+4)=F5105F409+10F30810F207+5F106F5. \begin{aligned} & \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}+i_{2}+306}-3 F_{i_{1}+i_{2}+205}+3 F_{i_{1}+i_{2}+104}-F_{i_{1}+i_{2}+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} . \end{aligned}
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=1545 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.