Problem:
There exists a unique strictly increasing sequence of nonnegative integers a1​<a2​<⋯<ak​ such that
217+12289+1​=2a1​+2a2​+⋯+2ak​
What is k?
Answer Choices:
A. 117
B. 136
C. 137
D. 273
E. 306
Solution:
First, substitute 217 with x. Then, the given equation becomes
x+1x17+1​=x16−x15+x14…−x1+x0
by sum of powers factorization. Now consider only x16−x15. This equals
x15(x−1)=x15⋅(217−1)
Note that 217−1 equals 216+215+…+1, by difference of powers factorization (or by considering the expansion of 217=216+215+…+2+2). Thus, we can see that x16−x15 forms the sum of 17 different powers of 2. Applying the same method to each of
x14−x13,x12−x11,…,x2−x1
we can see that each of the pairs forms the sum of 17 different powers of 2. This gives us 17⋅8=136. But we must count also the x0 term. Thus, Our answer is 136+1=(C) 137​.
OR
Multiply both sides by 217+1 to get
2289+1=2a1​+2a2​+…+2ak​+2a1​+17+2a2​+17+…+2ak​+17
Notice that a1​=0, since there is a 1 on the LHS. However, now we have an extra term of 218 on the right from 2a1​+17. To cancel it, we let a2​=18. The two 218's now combine into a term of 219, so we let a3​=19. And so on, until we get to a18​=34. Now everything we don't want telescopes into 235.
We already have that term since we let
a2​=18⟹a2​+17=35
Everything from now on will automatically telescope to 252. So we let a19​ be 52.
As you can see, we will have to add 17an′​s at a time, then "wait" for the sum to automatically telescope for the next 17 numbers, etc, until we get to 2289. We only need to add an′​s between odd multiples of 17 and even multiples. The largest even multiple of 17 below 289 is 17⋅16, so we will have to add a total of 17⋅8an′​s. However, we must not forget we let a1​=0 at the beginning, so our answer is
17⋅8+1=(C) 137​
The problems on this page are the property of the MAA's American Mathematics Competitions