0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

I suggest you make a large Pascal's triangle and color in all the even cells to see the structure. It is quite beautiful. A search for Pascal's triangle mod 2 will turn up examples.

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.