A CHARACTERIZATION OF THE ODD BINOMIAL COEFFICIENTS

ANDERS CLAESSON

The aim of this short paper is to analyse Pascal’s triangle modulo 2. Here follows an illustration of the first 16 rows of this triangle ( ■:=1, □:=0) :

\begin{matrix}0 & ■ & 0 \\ 1 & ■ ■ & 1 \\ 2 & ■ □ ■ & 2 \\ 3 & ■ ■ ■ ■ & 3 \\ 4 & ■ □ □ □ ■ & 4 \\ 5 & ■ ■ □ □ ■ ■ & 5 \\ 6 & ■ □ ■ □ ■ □ ■ & 6 \\ 7 & ■ ■ ■ ■ ■ ■ ■ ■ & 7 \\ 8 & ■ □ □ □ □ □ □ □ ■ & 8 \\ 9 & ■ ■ □ □ □ □ □ □ ■ ■ & 9 \\ 10 & ■ □ ■ □ □ □ □ □ ■ □ ■ & 10 \\ 11 & ■ ■ ■ ■ □ □ □ □ ■ ■ ■ ■ & 11 \\ 12 & ■ □ □ □ ■ □ □ □ ■ □ □ □ ■ & 12 \\ 13 & ■ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ & 13 \\ 14 & ■ □ ■ □ ■ □ ■ □ ■ □ ■ □ ■ □ ■ & 14 \\ 15 & ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ & 15 \end{matrix}

Take any n ∈ ℕ and let n = ∑_{i} b_{i}2^{i}, b_{i} ∈ {0, 1}, be its binary expansion. Then we define C_{n} = {2^{i} : b_{i} = 1}, e.g. 13 = 1+4+8 and hence C_{13} = {1, 4, 8}. Moreover we define w(n) as the number of i’s such that b_{i} = 1, e.g. w(13) = w(1101_{2}) = 3.

Proposition. If 0 ≤ k ≤ n then \binom{n}{k} is odd if and only if C_{k} ⊆ C_{n}.

Proof. By an easy induction argument we see that (1+x)^{2^{m}} ≡ 1+x^{2^{m}} (mod 2) for every m ∈ ℕ. Now fix an n ∈ ℕ, by the binomial theorem (1 + x)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k} and hence \binom{n}{k} is odd if and only if x^{k} is a term in (1 + x)^{n} when counting modulo two. Moreover

(1 + x)^{n} = ∏_{c∈C_{n}}(1 + x)^{c} ≡ ∏_{c∈C_{n}}(1 + x^{c}) = ∑_{k:C_{k}⊆C_{n}}x^{k} ( mod 2 )

which concludes the proof.

Corollary. There are exactly 2^{w(n)} odd entries in row n of Pascal’s triangle.

Proof. The polynomial ∑_{k:C_{k}⊆C_{n}}x^{k} contains |P(C_{n})| = 2^{|C_{n}|} = 2^{w(n)} terms.

Department of Mathematics, Chalmers University of Technology and Göteborg University, S-412 96 Göteborg, Sweden

   E-mail address: claesson@math.chalmers.se

Date: July 26, 2000.