Problem:
A sequence is defined as follows: a1​=a2​=a3​=1, and, for all positive integers n, an+3​=an+2​+an+1​+an​. Given that a28​=6090307,a29​=11201821, and a30​=20603361, find the remainder when ∑k=128​ak​ is divided by 1000.
Solution:
Because ak+3​−ak+2​=ak+1​+ak​ for all positive integers k, conclude that
k=1∑n​(ak+3​−ak+2​)=k=1∑n​(ak+1​+ak​)
Let Sn​=∑k=1n​ak​. Notice that ∑k=1n​(ak+3​−ak+2​) telescopes to an+3​−a3​, and that ∑k=1n​(ak+1​+ak​)=(Sn​a1​+an+1​)+Sn​. Therefore an+3​−a3​=Sn​−a1​+an+1​+Sn​, so Sn​=(1/2)(an+3​−an+1​)=(1/2)(an+2​+an​), and in particular S28​=(1/2)(a30​+a28​). Thus the last three digits of the sum are the same as those of (1/2)(3361+0307), namely 834, and the requested remainder is 834.
The problems on this page are the property of the MAA's American Mathematics Competitions