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).
Answer
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}.$$
No comments:
Post a Comment