Maths Olympiad Prep

Library / /700 of 860

Algebra Difficulty 5.4 AIME, harder Find the answer

Find the value of (20031)+(20034)+(20037)++(20032002) \binom{2003}{1}+\binom{2003}{4}+\binom{2003}{7}+\cdots+\binom{2003}{2002}

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

Solution

Let ω=1/2+i3/2\omega=-1 / 2+i \sqrt{3} / 2 be a complex cube root of unity. Then, by the binomial theorem, we have ω2(ω+1)2003=(20030)ω2+(20031)ω3+(20032)ω4++(20032003)ω200522003=(20030)+(20031)+(20032)++(20032003)ω2(ω1+1)2003=(0030)ω2+(20031)ω3+(20032)ω4++(20032003)ω2005 \begin{aligned} \omega^{2}(\omega+1)^{2003} & =\binom{2003}{0} \omega^{2}+\binom{2003}{1} \omega^{3}+\binom{2003}{2} \omega^{4}+\cdots+\binom{2003}{2003} \omega^{2005} \\ 2^{2003} & =\binom{2003}{0}+\binom{2003}{1}+\binom{2003}{2}+\cdots+\binom{2003}{2003} \\ \omega^{-2}\left(\omega^{-1}+1\right)^{2003} & =\binom{003}{0} \omega^{-2}+\binom{2003}{1} \omega^{-3}+\binom{2003}{2} \omega^{-4}+\cdots+\binom{2003}{2003} \omega^{-2005} \end{aligned} If we add these together, then the terms (2003n)\binom{2003}{n} for n1(mod3)n \equiv 1(\bmod 3) appear with coefficient 3 , while the remaining terms appear with coefficient 1+ω+ω2=01+\omega+\omega^{2}=0. Thus the desired sum is just (ω2(ω+1)2003+22003+ω2(ω1+1)2003)/3\left(\omega^{2}(\omega+1)^{2003}+2^{2003}+\omega^{-2}\left(\omega^{-1}+1\right)^{2003}\right) / 3. Simplifying using ω+1=ω2\omega+1=-\omega^{2} and ω1+1=ω\omega^{-1}+1=-\omega gives (1+22003+1)/3=(220032)/3\left(-1+2^{2003}+-1\right) / 3=\left(2^{2003}-2\right) / 3.

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.