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 "2024 AMC 12A Problems/Problem 21"
m (→‎Solution 2)
Line 67: Line 67:
  
 
==Solution 2==
 
==Solution 2==
 +
According to the equation given,
 +
 
<cmath>\frac{a_n - 1}{n - 1} = \frac{a_{n - 1} + 1}{n}</cmath>
 
<cmath>\frac{a_n - 1}{n - 1} = \frac{a_{n - 1} + 1}{n}</cmath>
  
Line 73: Line 75:
 
<cmath>na_n - (n - 1)a_{n - 1} = 2n - 1</cmath>
 
<cmath>na_n - (n - 1)a_{n - 1} = 2n - 1</cmath>
  
−
Suppose <math>{b_n}</math>, <math>b_n = na_n</math>, then <math>b_n - b_{n - 1} = 2n - 1</math>, where <math>b_1 = 1 \cdot a_1 = 2</math>, then we obtain that
+
Suppose <math>\{b_n\}</math>, <math>b_n = na_n</math>, then <math>b_n - b_{n - 1} = 2n - 1</math>, where <math>b_1 = 1 \cdot a_1 = 2</math>, then we obtain that
  
 
<cmath>b_n = b_1 + (b_2 - b_1) + (b_3 - b_2) + \cdots + (b_n - b_{n - 1})</cmath>
 
<cmath>b_n = b_1 + (b_2 - b_1) + (b_3 - b_2) + \cdots + (b_n - b_{n - 1})</cmath>

Revision as of 21:59, 8 November 2024

Problem

Suppose that $a_1 = 2$ and the sequence $(a_n)$ satisfies the recurrence relation \[\frac{a_n -1}{n-1}=\frac{a_{n-1}+1}{(n-1)+1}\]for all $n \ge 2.$ What is the greatest integer less than or equal to \[\sum^{100}_{n=1} a_n^2?\]

$\textbf{(A) } 338{,}550 \qquad \textbf{(B) } 338{,}551 \qquad \textbf{(C) } 338{,}552 \qquad \textbf{(D) } 338{,}553 \qquad \textbf{(E) } 338{,}554$

Solution

Multiply both sides of the recurrence to find that $n(a_n-1)=(n-1)(a_{n-1}+1)=(n-1)(a_{n-1}-1)+(n-1)(2)$.

Let $b_n=n(a_n-1)$. Then the previous relation becomes \[b_n=b_{n-1}+2(n-1)\]

We can rewrite this relation for values of $n$ until $1$ and use telescoping to derive an explicit formula:

\[b_n=b_{n-1}+2(n-1)\] \[b_{n-1}=b_{n-2}+2(n-2)\] \[b_{n-2}=b_{n-3}+2(n-3)\] \[\cdot\] \[\cdot\] \[\cdot\] \[b_2=b_1+2(1)\]

Summing the equations yields:

\[b_n+b_{n-1}+\cdots+b_2=b_{n-1}+b_{n-2}+\cdots+b_1+2((n-1)+(n-2)+\cdots+1)\] \[b_n-b_1=2\cdot\frac{n(n-1)}{2}\] \[b_n-1=n(n-1)\] \[b_n=n(n-1)+1\]

Now we can substitute $a_n$ back into our equation:

\[n(a_n-1)=n(n-1)+1\] \[a_n-1=n-1+\frac{1}{n}\] \[a_n=n+\frac{1}{n}\] \[a_n^2=n^2+\frac{1}{n^2}+2\]

Thus the sum becomes

\[\sum^{100}_{n=1} a_n^2= \sum^{100}_{n=1} n^2+ \sum^{100}_{n=1} \frac{1}{n^2}+ \sum^{100}_{n=1} 2\]

We know that $\sum^{100}_{n=1} n^2=\frac{100\cdot101\cdot201}{6}=338350$, and we also know that $\sum^{100}_{n=1} 2=200$, so the requested sum is equivalent to $\sum^{100}_{n=1} \frac{1}{n^2}+338550$. All that remains is to calculate $\sum^{100}_{n=1} \frac{1}{n^2}$, and we know that this value lies between $1$ and $2$ (see the note below for a proof). Thus,

\[\sum^{100}_{n=1} a_n^2= \sum^{100}_{n=1} \frac{1}{n^2}+338550<2+338550=338552\] \[\sum^{100}_{n=1} a_n^2= \sum^{100}_{n=1} \frac{1}{n^2}+338550>1+338550=338551\]

so

\[\sum^{100}_{n=1} a_n^2\in(338551,338552)\]

and thus the answer is $\boxed{\textbf{(B) }338551}$.

~eevee9406

Note: $\sum^{100}_{n=1} \frac{1}{n^2}< \sum^{\infty}_{n=1} \frac{1}{n^2}=\frac{\pi^2}{6}<2$. It is obvious that the sum is greater than 1 (since it contains $\frac{1}{1^2}$ as one of its terms).

If you forget this and have to derive this on the exam, here is how:

\[\sum^{100}_{n=1} \frac{1}{n^2}<\sum^{\infty}_{n=1} \frac{1}{n^2}=\frac{1}{1^1}+\left(\frac{1}{2^2}+\frac{1}{3^2}\right)+\left(\frac{1}{4^2}+\frac{1}{5^2}+\frac{1}{6^2}+\frac{1}{7^2}\right)+\cdots\]

\[<1+\left(\frac{1}{2^2}+\frac{1}{2^2}\right)+\left(\frac{1}{4^2}+\frac{1}{4^2}+\frac{1}{4^2}+\frac{1}{4^2}\right)+\left(\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}+\frac{1}{8^2}\right)+\cdots\]

\[=1+\frac{2}{2^2}+\frac{4}{4^2}+\frac{8}{8^2}+\cdots\]

\[=1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots=2\]

and it is clear that $\sum^{100}_{n=1} \frac{1}{n^2}<2$. ~eevee9406


Solution 2

According to the equation given,

\[\frac{a_n - 1}{n - 1} = \frac{a_{n - 1} + 1}{n}\]

\[na_n - n = (n - 1)a_{n - 1} + n - 1\]

\[na_n - (n - 1)a_{n - 1} = 2n - 1\]

Suppose $\{b_n\}$, $b_n = na_n$, then $b_n - b_{n - 1} = 2n - 1$, where $b_1 = 1 \cdot a_1 = 2$, then we obtain that

\[b_n = b_1 + (b_2 - b_1) + (b_3 - b_2) + \cdots + (b_n - b_{n - 1})\]

\[b_n = 2 + 3 + 5 + \cdots + (2n - 1) = 1 + n^2\]

\[a_n = \frac{1 + n^2}{n} = n + \frac{1}{n}\]

Hence,

\begin{align*} \sum_{n = 1}^{100} a_n^2 &= \sum_{n = 1}^{100} \left(n + \frac{1}{n}\right)^2\\ &= \sum_{n = 1}^{100} (n^2 + 2 + \frac{1}{n^2})\\ &= \sum_{n = 1}^{100} n^2 + \sum_{n = 1}^{100} 2 + \sum_{n = 1}^{100}\frac{1}{n^2}\\ &= \frac{1}{6} \cdot 100 \cdot (100 + 1) \cdot (100 \cdot 2 + 1) + 100 \cdot 2 + \sum_{n = 1}^{100}\frac{1}{n^2}\\ &= 338350 + 200 + \sum_{n = 1}^{100}\frac{1}{n^2}\\ &= 338550 + \sum_{n = 1}^{100}\frac{1}{n^2} \end{align*}

Notice that, \[\sum_{n = 1}^{100}\frac{1}{n^2} = 1 + \sum_{n = 2}^{100}\frac{1}{n^2} > 1\] \[\sum_{n = 1}^{100}\frac{1}{n^2} < 1 + \sum_{n = 2}^{100}\frac{1}{n(n - 1)} = 1 + 1 - \frac{1}{100} < 2~~(\text{telescope})\]

so

\[\sum^{100}_{n=1} a_n^2\in(338551,338552)\]

and thus the answer is $\boxed{\textbf{(B) }338551}$.

~reda_mandymath

See also

2024 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 20 		Followed by
Problem 22
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_AMC_12A_Problems/Problem_21&oldid=232378"