# identity on Pascal's triangle modulo 2

Consider Pascal's triangle with entries modulo $2$, and let $(k,l)$ denote the $l$-th entry in the $k$-th row by $(k,l)$.

Show that, for all $n \in \mathbb{N}$, each entry of the triangle with vertices $(0,0)$, $(2^n-1,0)$, $(2^n-1,2^n-1)$ is mapped via the translation $(k,l) \mapsto (2^n+k,l)$ to an equal entry (modulo $2$), i.e. the translation preserves the triangle entries modulo $2$.

This explains the "nice pattern" of Pascal's triangle modulo $2$. Since Pascal's triangle simply shows the binomial coefficients, another way to state this is:

Let $k,l \in \{0,\dots,2^n-1\}$ such that $l \leq k$, and let $n \in \mathbb{N}$. Then it holds

$$\binom{k}{l} \equiv \binom{2^n+k}{l} \mod 2.$$

I am searching for an elementary proof for this (perhaps by induction, but I got stuck trying this).

• Would you consider Lucas' theorem elementary? It is essentially the generalization of your statement to arbitrary prime $p$.
– EuYu
May 25 '16 at 14:01
• @EuYu The proofs for Lucas' theorem on wikipedia are not very complicated I think, but use some notions of discrete mathematics. I found the question in the very first chapter of a textbook for an introduction of calculus which only deals with mathematical induction, so I was searching for a really elementary solution. May 25 '16 at 15:30
• For the sake of completeness: A completely elementary solution (yes, by induction) is available in UMN Math 4707 Spring 2018 homework set 1 (solution to Exercise 4). But yes, it's long (a lot of it being parallel cases) and relies on another exercise (Exercise 3) which also has a fairly long solution. I meant for this to be an exercise on induction, but it was too laborious for most students. Feb 24 '18 at 16:25

Note that $$\dbinom{2^n+k}{l} = \sum_{i=0}^l \dbinom{2^n}{i}\dbinom{k}{l-i}.$$ Now, since $i\le l \le 2^n-1<2^n$, it follows that if $i>0$ then $2\mid \binom{2^n}{i}$, so that modulo 2 we get $$\dbinom{2^n+k}{l} \equiv \dbinom{2^n}{0}\dbinom{k}{l} = \dbinom{k}{l}\mod{2}.$$