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∑n​3(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