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

Page

Toolbox

Search

Mock AIME 3 Pre 2005 Problems/Problem 10

Problem

Solution

See also