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