Problem:
Find the remainder when
(2(23))+(2(24))+⋯+(2(240))
is divided by 1000.
Solution:
Because
(2k)−1=2k(k−1)−2=2(k−2)(k+1)
it follows that
(2k)=2(2k)⋅((2k)−1)=8(k+1)k(k−1)(k−2)=3(4k+1)
By the Hockey-stick Identity,
k=3∑n3(4k+1)=3(5n+2)
Then the given sum equals
3(542)=1203⋅42⋅41⋅40⋅39⋅38=(42⋅38)⋅(41⋅39)≡596⋅599≡(−404)(−401)≡4(mod1000)
The requested remainder is 4 .
OR
Note that (2(2k)) is the number of ways of choosing two distinct sets of two integers from 1 to k. The two sets chosen can have either 0 or 1 element in common. Choose two sets with no elements in common by choosing 4 elements and then separating those 4 elements into two sets of 2 , and this can be done in 3(4k) ways. Choose two sets with one element in common by choosing the common element and then choosing two elements to pair with it, and this can be done in k(2k−1) ways. This shows that
(2(2k))=3(4k)+k(2k−1)=3(4k)+3(3k)=3(4k+1)
Then the solution continues as above.
The problems on this page are the property of the MAA's American Mathematics Competitions