4
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Would you consider Lucas' theorem elementary? It is essentially the generalization of your statement to arbitrary prime $p$. $\endgroup$
    – EuYu
    May 25 '16 at 14:01
  • $\begingroup$ @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. $\endgroup$
    – lattice
    May 25 '16 at 15:30
  • $\begingroup$ 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. $\endgroup$ Feb 24 '18 at 16:25
2
$\begingroup$

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}.$$

$\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.