Solution
Odd Entries in Pascal
Show the problem again
How many of the entries $\binom{n}{k}$ with $0 \le k \le n \le 63$ (rows 0 through 63 of Pascal's triangle) are odd? Give an integer.
Worked solution
The answer is 729. By Lucas's theorem, $\binom{n}{k}$ is odd exactly when every binary digit of $k$ is at most the corresponding digit of $n$, i.e. the 1-bits of $k$ are a subset of the 1-bits of $n$. So row $n$ has $2^{s(n)}$ odd entries, where $s(n)$ is the number of 1s in binary. Summing over all six-bit $n$: each of the 6 bit positions independently contributes a factor of $1$ (bit 0) or $2$ (bit 1), so the total is $(1 + 2)^6 = 3^6 = 729$. This is why the odd entries form the Sierpinski triangle: doubling the rows triples the count.
Source: Classic consequence of Lucas's theorem, in wide circulation. Statement written for AxiomIQ.