Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME 3 Pre 2005 Problems/Problem 10"
(No difference)

Revision as of 09:25, 4 April 2012

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_3_Pre_2005_Problems/Problem_10&oldid=46068"