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"
Line 7: Line 7:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
We can easily express <math>a_n</math> as the following sum:
 +
<cmath> a_n = \sum_{k=0}^{n-1} 2^k (n-k)^2 </cmath>
 +
 
 +
This can be broken down into three simpler sums:
 +
<cmath> 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 </cmath>
 +
 
 +
Using finite calculus, one can easily derive the following classical sums:
 +
<cmath> D = \sum_{k=0}^{n-1} 2^k = 2^n - 1 </cmath>
 +
<cmath> E = \sum_{k=0}^{n-1} k2^k = (n-2)2^n + 2 </cmath>
 +
<cmath> F = \sum_{k=0}^{n-1} k(k-1)2^k = (n^2-5n+8)2^n - 8 </cmath>
 +
 
 +
Using these, we can now compute:
 +
<cmath> A = n^2\cdot \sum_{k=0}^{n-1} 2^k = n^2D = n^2 2^n - n^2 </cmath>
 +
<cmath> B = 2n\sum_{k=0}^{n-1} k2^k = 2nE = 2n(n-2)2^n + 4n </cmath>
 +
<cmath> C = \sum_{k=0}^{n-1} k^2 2^k = E+F = (n^2-4n+6)2^n - 6 </cmath>
 +
 
 +
And hence we get the closed form for <math>a_n</math>:
 +
 
 +
<cmath> a_n = A-B+C = 6\cdot 2^n - n^2 - 4n - 6 </cmath>
 +
 
 +
Now we can compute <math>a_n \bmod 1000</math> as follows:
 +
 
 +
We know that <math>\phi(125)=100</math> (where <math>\phi</math> is the [[Euler's totient function]]), hence <math>2^{100}\equiv 1 \pmod{125}</math>, and thus <math>2^{2000}\equiv 1 \pmod{125}</math>. Thus there is an integer <math>k</math> such that <math>2^{2000} = 125k + 1</math>. And then <math>2^{2004} = 2000k + 16</math>, hence <math>2^{2004} \equiv 16 \pmod{1000}</math>.
 +
 
 +
Therefore we have <math>a_n \equiv 6\cdot 16 - 4^2 - 4\cdot 4 - 6 = \boxed{058} \pmod{1000}</math>.
  
 
==See also==
 
==See also==

Revision as of 23:48, 30 January 2009

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=29832"