Question

Let $\sum_{k=0}^{1000} \binom{2000}{2k}9^k$ is divisible by $2^a$, then the maximum value of $a$ is:

• A. 2001
• B. 1998
• C. 2000
• D. 1999

Answer 1

Answer: (D)

1999

Answer 2

The sum is $S = \sum_{k=0}^{1000} \binom{2000}{2k}9^k$. We use the identity: $(1+x)^n + (1-x)^n = 2 \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k} x^{2k}$. Let $n=2000$ and $x=3$. Then, $(1+3)^{2000} + (1-3)^{2000} = 2 \sum_{k=0}^{1000} \binom{2000}{2k} 3^{2k}$. $4^{2000} + (-2)^{2000} = 2 \sum_{k=0}^{1000} \binom{2000}{2k} 9^k$. $4^{2000} + 2^{2000} = 2S$. $S = \frac{4^{2000} + 2^{2000}}{2} = \frac{(2^2)^{2000} + 2^{2000}}{2} = \frac{2^{4000} + 2^{2000}}{2}$. $S = \frac{2^{2000}(2^{2000} + 1)}{2} = 2^{1999}(2^{2000} + 1)$. Since $2^{2000} + 1$ is odd, the maximum power of 2 that divides $S$ is $2^{1999}$. Thus, $a=1999$.