# Pascal Triangle Proof

Prove that the number of odd coefficients in each row of Pascal’s triangle is a power of 2 .

I don't know where to begin. I'm not necessarily asking anyone to do the entire proof for me, but if anyone is kind enough to give me any hints or something to consider.

You can use Legendre's formula to find the power of $2$ dividing each factorial. From that, you can show that rows $2^n$ of Pascal's triangle consist of $1$, all even numbers, and the final $1$ because the numerator is $(2^n)!$ and it will have a factor $2^n$ that the denominator cannot match. The triangle below each of the $1$s when reduced $\bmod 2$ is just like the triangle above that row. It follows that the row $2^n+k$ has twice as many odd entries as row $k$ if $k \lt 2^n$. Now strong induction says all the rows have a power of $2$ odd entries. There are certainly other approaches.
Here is a generating function approach. Let $m$ be a positive integer. The binomial coefficients ${m\choose 0}, {m\choose1},\ldots{m\choose m}$ are the coefficients of the generating function $(1+x)^m$. By consulting the base $2$ expansion of $m$, find a set $E$ integers $\ge0$ such that $m=\sum_{e\in E}2^e$. Then $$\sum_{k=0}^m{m\choose k}x^k=(1+x)^m=(1+x)^{\sum_{e\in E}2^e}=\prod_{e\in E}\tag1(1+x)^{2^e}.$$ Argue that, modulo $2$, $(1+x)^{2^e}=1+x^{2^e}$; that is, all the other coefficients in the expansion of $(1+x)^{2^e}$ are even. It follows that, mod $2$, $$\sum_{k=0}^m{m\choose k}x^k=\prod_{e\in E}(1+x^{2^e}).\tag2$$ The RHS of (2) is a polynomial of all odd coefficients. How many terms does it have?