Mock AIME 1 Pre 2005 Problems/Problem 11

Problem

Let $S$ denote the value of the sum \[\sum_{n=0}^{668} (-1)^{n} {2004 \choose 3n}\] Determine the remainder obtained when $S$ is divided by $1000$.

Solution

Consider the polynomial \[f(x)=(x-1)^{2004}=\sum_{n=0}^{2004}\binom{2004}{n}\cdot(-1)^n x^{2004-n}.\]

Let $\omega^3=1$ with $\omega\neq 1$. We have

\begin{align*} \frac{f(1)+f(\omega)+f(\omega^2)}{3} &= \frac{(1-1)^{2004}+(\omega-1)^{2004}+(\omega^2-1)^{2004}}{3} \\ &= \frac{1}{3}\sum_{n=0}^{2004}\binom{2004}{n}\cdot(-1)^n\cdot(1^{2004-n}+\omega^{2004-n}+(\omega^2)^{2004-n}) \\ &= \sum_{n=0}^{668}(-1)^n \binom{2004}{3n}. \end{align*}

where the last step follows because $1^k+\omega^k+\omega^{2k}$ is 0 when $k$ is not divisible by 3, and $3$ when $k$ is divisible by 3.

We now compute $\frac{(1-1)^{2004}+(\omega-1)^{2004}+(\omega^2-1)^{2004}}{3}$. WLOG, let $\omega = \frac{-1+\sqrt{3}i}{2}, \omega^2=\frac{-1-\sqrt{3}i}{2}$. Then $\omega-1=\frac{-3+\sqrt{3}i}{2} = \sqrt{3}\cdot \frac{-\sqrt{3}+i}{2}$, and $\omega^2-1=\sqrt{3}\cdot\frac{-\sqrt{3}-i}{2}$. These numbers are both of the form $\sqrt{3}\cdot\varphi$, where $\varphi$ is a 12th root of unity, so both of these, when raised to the 2004-th power, become $3^{1002}$. Thus, our desired sum becomes $2\cdot3^{1001}$.

To find $2\cdot3^{1001} \pmod{1000}$, we notice that $3^{\phi{500}}\equiv 3^{200}\equiv 1 \pmod{500}$ so that $3^{1001}\equiv 3 \pmod{500}$. Then $2\cdot3^{1001}=2(500k+3)=1000k+6$. Thus, our answer is $\boxed{006}$.

See also

Mock AIME 1 Pre 2005 (Problems, Source)
Preceded by
Problem 10
Followed by
Problem 12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Invalid username
Login to AoPS