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}$.

See Also

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