Determine the number of odd binomial coefficients in the expansion of $(x+y)^{1000}$. 
Determine the number of odd binomial coefficients in the expansion of $(x+y)^{1000}$. Hint: The number of odd coefficients in any finite binomial expansion is a power of $2$.

Is there a way to prove this without using something like Lucas's theorem or any other non-trivial result? It's a problem from a problem solving book and they haven't introduced any theorems in it. They have just given that it should be a power of $2$, but nothing on how to go about finding it. Computing a few smaller terms shows that $(x+y)^0$ has $1$ odd coefficient, $(x+y)^1$ has $2$, $(x+y)^2$ has $2$, $(x+y)^3$ has $4$, $(x+y)^4$ has 2 and $(x+y)^5$ has $4$, but no pattern seems to emerge.

Hints:
Employing $\text{modulo 2}$ polynomial calculations we are pleased to find that
$$ 512 + 256 + 128 + 64 + 32 + 8 = 1000$$
and we don't have to expand
$$ (x^{512}+ y^{512}) (x^{256}+ y^{256}) (x^{128}+ y^{128}) (x^{64}+ y^{64}) (x^{32}+ y^{32}) (x^{8}+ y^{8})$$
since $1 \times 1 = 1$ and there is no need to collect like terms after combining/adding the exponents .
Now just set both $x$ and $y$ to $1$.
ANS: $64$

Note: If you start calculating
$\; (x+y)^1$
$\; (x+y)^2 \equiv x^2 + y^2$
$\; (x+y)^3 \equiv (x^2 + y^2)(x+y)$
$\; (x+y)^4 \equiv (x^4 + y^4)$
$\; (x+y)^5 \equiv (x^4 + y^4)(x+y)$
$\; (x+y)^6 \equiv (x^4 + y^4)(x^2+y^2)$
$\; (x+y)^7 \equiv (x^4 + y^4)(x^2+y^2)(x+y)$
$\; (x+y)^8 \equiv (x^8 + y^8)$
$\; (x+y)^9 \equiv (x^8 + y^8)(x+y)$
$\; \dots$
You will discover the pattern given in Oscar Lanzi's answer.
