2024 AMC 12A Problems/Problem 21

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

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

Page

Toolbox

Search

2024 AMC 12A Problems/Problem 21

Problem

Solution

See also