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.
 A: Hint:
Exponent in base 2 $\to$ Number of odd coefficients:
$0\to2^0=1$
$1\to2^1=2$
$10\to2^1=2$
$11\to2^2=4$
$100\to2^1=2$
$101\to2^2=4$
Can you see it now?
A: If you want the conclusion,that is:
using Lucas's theorem,we cant get
$$
\left(\begin{array}{c}
n \\
m
\end{array}\right) \bmod 2=1 \Leftrightarrow n \& m=m
$$
where $\&$ means and-bitwise.
It following that,the number of odd coefficients in  $n$-th row,equals how many bitmasks the binary representation of $n$ can "cover".
The answer is $2^{\operatorname{popcount}(n)}$,where $\operatorname{popcount}(n)$ means how many "1" in binary representation of $n$.
For your question
2^DigitCount[1000, 2, 1]    (*64*)


I wrote a mathematica code to verify the answer
Clear["Global`*"];
(x + y)^1000 // Expand // CoefficientList[#, {x, y}] & // 
   Map[(Total@#)~Mod~2 &, #] & // Tally // AbsoluteTiming

{0.0453605, {{1, 64}, {0, 937}}}

Indeed,the Pascal Triangle number modulo 2,looks like  (Sierpiński triangle)
ArrayPlot[
 CellularAutomaton[{Total[#]~Mod~2 &, {}, 1/2}, {{1}, 0}, 100], 
 Mesh -> True, ColorFunction -> "Monochrome"]

By the way, If you are interested in these patterns, you'd be glad to vist Parity Triangles Bot, There are images based on the parity of sequences in the On-Line Encyclopedia of Integer Sequences (OEIS).

A: 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.
A: Let $p$ be a prime number. We can prove that $(x+y)^{p^n}\equiv x^{p^n}+y^{p^n}\pmod p$ by induction: $(x+y)^{p}\equiv x^{p}+y^{p}\pmod p$ is clearly true. Assume that $(x+y)^{p^{n-1}}\equiv x^{p^{n-1}}+y^{p^{n-1}}\pmod p$. Then
$$(x+y)^{p^n}\equiv((x+y)^{p^{n-1}})^p\equiv(x^{p^{n-1}}+y^{p^{n-1}})^p\equiv x^{p^n}+y^{p^n}\pmod p.$$
Then "CopyPasteit answer above": It gives the solution by setting $x=y=1$ in the latter polynomial below
$$(x+y)^{1000}\equiv(x^{512}+y^{512})(x^{256}+y^{256})(x^{128}+y^{128})(x^{64}+y^{64}(x^{32}+y^{32})(x^{8}+y^{8})\pmod 2,$$
because its coefficients are all $1$.
