Competition problem — Algebra — Maths Olympiad Prep

Library / /855 of 860

Algebra Difficulty 6.0 AIME, harder Find the answer

The Fibonacci numbers are defined by $F_{0}=0, F_{1}=1$ , and $F_{n}=F_{n-1}+F_{n-2}$ for $n \geq 2$ . There exist unique positive integers $n_{1}, n_{2}, n_{3}, n_{4}, n_{5}, n_{6}$ such that $\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 $n_{1}+n_{2}+n_{3}+n_{4}+n_{5}+n_{6}$ .

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

We make use of the identity $\sum_{i=0}^{\ell} F_{i}=F_{\ell+2}-1$ (easily proven by induction) which implies $\sum_{i=k}^{\ell} F_{i}=F_{\ell+2}-F_{k+1}$ . Applying this several times yields $\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 $F_{510}$ term dominates, forcing $n_{1}=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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.