# Mock AIME 3 Pre 2005 Problems/Problem 13

## Problem

$13.$ Let $S$ denote the value of the sum

$\left(\frac{2}{3}\right)^{2005} \cdot \sum_{k=1}^{2005} \frac{k^2}{2^k} \cdot {2005 \choose k}$

Determine the remainder obtained when $S$ is divided by $1000$.

## Solution

Let $S = \sum_{k = 0}^{2005}\dfrac{k^2}{2^k}\cdot{2005 \choose k} = \sum_{k = 1}^{2005}\dfrac{k^2}{2^k}\cdot{2005 \choose k}$. Let $W = \left(\dfrac{2}{3}\right)^{2005}S$. Then note that $(x + 1)^{2005} = \sum_{k = 0}^{2005} {2005 \choose k}x^k$, so taking the derivative and multiplying by $x$ gives $2005x(x + 1)^{2004} = \sum_{k = 0}^{2005} k{2005 \choose k}x^k$. Taking the derivative and multiplying by $x$ again gives $f(x) = 2005x(x + 1)^{2004} + (2005)(2004)x^2(x + 1)^{2003} = \sum_{k = 0}^{2005} k^2{2005 \choose k}x^k$. Now note that $f\left(\dfrac{1}{2}\right) = S$. Then we get $W = \left(\dfrac{2}{3}\right)^{2005}S = \left(\dfrac{2}{3}\right)^{2005}\left(\dfrac{2005}{2}\left(\dfrac{3}{2}\right)^{2004} + (501)(2005)\left(\dfrac{3}{2}\right)^{2003}\right)$, so $W = \dfrac{2}{3}\cdot\dfrac{2005}{2} + \dfrac{668}{3}\cdot(2005) = 447115$, so $W \equiv \boxed{115} \pmod{1000}$.