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=128ak 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=1nak. Notice that ∑k=1n(ak+3−ak+2) telescopes to an+3−a3, and that ∑k=1n(ak+1+ak)=(Sna1+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