500 Follower Problem

Note first that $\displaystyle\sum_{n=0}^{500} (x + 1)^{500} = \dfrac{(x + 1)^{501} - 1}{(x + 1) - 1}$ ,

and so $\displaystyle\sum_{n=1}^{500} (x + 1)^{500} = \dfrac{(x + 1)^{501} - 1}{x} - 1 = \dfrac{(x + 1)^{501} - x - 1}{x}$ .

The numerator will then be the same as the expansion of $(x + 1)^{501}$ but with a constant coefficient of $0$ and with the coefficient of $x$ being $500$ , (i.e., even), instead of $501$ .

Thus when this is divided by $x$ , the number of odd coefficients of powers of $x$ will be the number of odd coefficients in the expansion of $(1 + x)^{501}$ minus $2$ , i.e., minus the odd constant and the odd coefficient of $x$ .

Now the coefficients in the expansion of $(x + 1)^{501}$ are of the form $\binom{501}{k}$ with $k$ running from $0$ to $501$ . So the number of odd coefficients in this expansion will be

$\displaystyle\sum_{k=0}^{501} (\dbinom{501}{k}$ (mod $2)) = 128$ ,

and thus $M = 128 - 2 = 126$ , giving us the answer $2M = \boxed{252}$ .

Comment: The rationale behind the mod calculation is that each odd coefficient returns a value of $1$ when evaluated mod $2$ . The actual value was found here using WolframAlpha. I realize that, to some, this may not be a satisfactory approach, but I could not find a pattern when looking at the sequence of binomial coefficients and thus resorted to a bit of WA trickery. If anyone has a better approach it would be most welcome. :)

Great problem Madhav :)

As in Mr. Charlesworth's solution, we have that by the finite geometric series, our series is equivalent to:

$\frac{(x+1)^{501} - x - 1}{x} = (\binom{501}{1} - 1 ) + \binom{501}{2}x + ... + \binom{501}{501}x^{500}.$

Thus, we are looking for the number of odd coefficients of the form $\binom{501}{n}$ , where 2 $\le$ n $\le$ 501. The binary equivalent of 501 is $111110101_2$ , and by Lucas' Theorem, we just need to ensure that $n = xxxxx0x0x_2$ in binary, where x can be 0 or 1, for $\binom{501}{n}$ to be odd. This gives us $2^7$ = 128 possibilities; however, n = 0 and n = 1 in $\binom{501}{n}$ are not in our sum, so we have M = 128 - 2 = 126. Thus, 2M = $\boxed{252}$ , as desired.