Problem:
Suppose that a1​=2 and the sequence (an​) satisfies the recurrence relation
n−1an​−1​=(n−1)+1an−1​+1​
for all n≥2. What is the greatest integer less than or equal to
n=1∑100​an2​?
Answer Choices:
A. 338,550
B. 338,551
C. 338,552
D. 338,553
E. 338,554
Solution:
Computing the first few terms of this sequence gives a1​=2,a2​=25​,a3​=310​, and a4​=417​, so it appears that an​=n+n1​. Indeed, this is correct, because the recurrence relation is satisfied:
(n−1)+1an−1​+1​=nn−1+n−11​+1​=1+n(n−1)1​=n−1n−1​+n−1n1​​=n−1an​−1​.
Then
n=1∑100​an2​​=n=1∑100​(n2+2+n21​)=6100⋅101⋅201​+200+r=62030100+1200​+r=338,550+r,​
where r=∑n=1100​n21​. But by a telescoping sum argument,
1<r<1+n=2∑100​n(n−1)1​=2−1001​<2
Thus ∑n=1100​an2​ is between 338,551 and 338,552 , and the requested greatest integer is (B)338,551​.
Note: One could also estimate ∑n=1100​n21​ by using the fact that
n=1∑∞​n21​=6π2​≈1.645
as proved by Euler in the 18th century.
The problems on this page are the property of the MAA's American Mathematics Competitions