# Mock AIME 3 Pre 2005 Problems/Problem 10

## Problem

$\{A_n\}_{n \ge 1}$ is a sequence of positive integers such that

$a_{n} = 2a_{n-1} + n^2$

for all integers $n > 1$. Compute the remainder obtained when $a_{2004}$ is divided by $1000$ if $a_1 = 1$.

## Solution

We can easily express $a_n$ as the following sum: $$a_n = \sum_{k=0}^{n-1} 2^k (n-k)^2$$

This can be broken down into three simpler sums: $$a_n = \underbrace{\sum_{k=0}^{n-1} n^2 2^k}_A - \underbrace{\sum_{k=0}^{n-1} 2kn 2^k}_B + \underbrace{\sum_{k=0}^{n-1} k^2 2^k}_C$$

Using finite calculus, one can easily derive the following classical sums: $$D = \sum_{k=0}^{n-1} 2^k = 2^n - 1$$ $$E = \sum_{k=0}^{n-1} k2^k = (n-2)2^n + 2$$ $$F = \sum_{k=0}^{n-1} k(k-1)2^k = (n^2-5n+8)2^n - 8$$

Using these, we can now compute: $$A = n^2\cdot \sum_{k=0}^{n-1} 2^k = n^2D = n^2 2^n - n^2$$ $$B = 2n\sum_{k=0}^{n-1} k2^k = 2nE = 2n(n-2)2^n + 4n$$ $$C = \sum_{k=0}^{n-1} k^2 2^k = E+F = (n^2-4n+6)2^n - 6$$

And hence we get the closed form for $a_n$:

$$a_n = A-B+C = 6\cdot 2^n - n^2 - 4n - 6$$

Now we can compute $a_n \bmod 1000$ as follows:

We know that $\phi(125)=100$ (where $\phi$ is the Euler's totient function), hence $2^{100}\equiv 1 \pmod{125}$, and thus $2^{2000}\equiv 1 \pmod{125}$. Thus there is an integer $k$ such that $2^{2000} = 125k + 1$. And then $2^{2004} = 2000k + 16$, hence $2^{2004} \equiv 16 \pmod{1000}$.

Therefore we have $a_n \equiv 6\cdot 16 - 4^2 - 4\cdot 4 - 6 = \boxed{058} \pmod{1000}$.