$\sum_{0\leq{k}<50}\binom{100}{2k+1}5^k \equiv r\pmod{ 2^{99}}$ where $0 \leq{r} < 2^{99}$, find $r$.

Question

$$\sum_{0\leq{k}<50}\binom{100}{2k+1}5^k \equiv r\pmod{ 2^{99}}$$ where $0 \leq{r} < 2^{99}$, find $r$.

This is a question that was posed in last year's LIMIT competition conducted by the Indian Statistical Institute. Full solutions would be greatly appreciated.

Answer 1

Note: The problem was subsequently edited from $ 0 < k < 50$ to $0 \leq k \leq 50$, and from $ 0 < r < 2^{99}$ to $ 0 \leq r < 2^{99}$.

Following the hinted solution below (which I'm too lazy to edit), the answer is $0$.

---

Hint: $$\sum_{k=0} ^ {100} \binom{100}{k}\sqrt{5}^kx^k = (1 + \sqrt{5}x)^{100} $$

Now set $ x = 1, -1$.
How can we get (close to) the expression in the question?
Note that you might be off by 1 term due to $ 0 < k < 50$ (Look at $ k = 0 $ closely).

The sum in the problem is thus

$\frac{ (1 + \sqrt{ 5} )^{100} - (1 - \sqrt{ 5} )^{100} } { \sqrt{5} } - 100$

Now, prove by induction that if $ ( 1 + \sqrt{5} ) ^ n = a_n + b_n \sqrt{5}$, then $ 2^{n-1} \mid a_n, 2^{n-1} \mid b_n$.
In particular, for $ n = 100$, both terms are multiples of $ 2^ {99}$.

Hence, the answer is

$2^{99} -100$

This agrees with Wolfram.