AoPSWiki
Want to learn how to tackle those tough AMC/AIME/Olympiad counting and probability problems? Check out Art of Problem Solving's Intermediate Counting & Probability by David Patrick.
Personal tools

Mock AIME 3 Pre 2005/Problem 10

From AoPSWiki

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^...

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 "http://www.artofproblemsolving.com/Wiki/index.php/Mock_AIME_3_Pre_2005/Problem_10"
Want to learn how to tackle those tough AMC/AIME/Olympiad algebra problems? Check out Art of Problem Solving's Intermediate Algebra by Richard Rusczyk and Mathew Crawford. Over 1600 problems!
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us