Fractals with Moduli in Pascal's Triangle

Question

I'm working through a problem for my graduate math class and am hitting a wall. Here's the problem:

For the first 10 lines of Pascal's Triangle, replace the odd numbers by black squares and the even numbers by white squares. Conjecture a formula for which rows are all black. See if you can prove your formula.

I have found a formula that seems to yield the needed all black rows, which is $2^{n-1}$. However, I have no idea how to show this is true for all rows in Pascal's Triangle. I know the previous row must have an odd, even, odd, even, ..., odd pattern. I also know that a row will only be all black if every integer $n$ in that row has the congruence $n \equiv 1 \pmod 2$. I'm really not sure where to go from there though. Any thoughts?

Answer 1

You should know a few things: the entries of Pascals Triangle are exactly the binomial coefficients $\binom{n}{r}=\frac{n!}{r!(n-r)!}$ where $n$ is the row (counting from zero from top to bottom) and $r$ is the (diagonal) column (counting from zero from left to right).

$\begin{array}{ccccc} &&\binom{0}{0}\\&\binom{1}{0}&&\binom{1}{1}\\\binom{2}{0}&&\binom{2}{1}&&\binom{2}{2}\\\vdots&&\vdots&&\vdots\end{array}$

Lucas's Theorem tell us that:

$$\binom{n}{r}\equiv \prod\limits_{i=0}^k \binom{n_i}{r_i}\pmod{p}$$

for any integer $n,r$ and prime number $p$ where $n_i$ is the $i^{th}$ digit of $n$ when represented in base $p$ (counting from the right). I.e., where $n = n_kp^k+n_{k-1}p^{k-1}+\dots+n_1p+n_0$. Similarly for $r$.

This tells us that $\binom{n}{r}$ is divisible by $p$ if and only if at least one of the digits of $r$ in its base $p$ representation is greater than the corresponding digit in $n$.

For your specific question, you see that when $n=2^{k}-1=1\cdot 2^{k-1}+1\cdot 2^{k-2}+\dots+1\cdot 2+1$, it is impossible for any digit of $r$ to be larger than the corresponding digit in $n$.

Answer 2

An important quality of Pascal's triangle mod 2, is that it exhibits a type of self-similarity and it is possible to use this self-similarity to prove your conjecture. This avoids the use of Lucas's theorem, or any other number theoretic / combinatorial arguments.

Let's take a look at the first five lines of Pascal's triangle mod 2:

\begin{array}{ccccccccc} \text{} & \text{} & \text{} & \text{} & 1 & \text{} & \text{} & \text{} & \text{} \\ \text{} & \text{} & \text{} & 1 & \text{} & 1 & \text{} & \text{} & \text{} \\ \text{} & \text{} & 1 & \text{} & \color{#ccc}{0} & \text{} & 1 & \text{} & \text{} \\ \text{} & 1 & \text{} & 1 & \text{} & 1 & \text{} & 1 & \text{} \\ \color{red}{1} & \text{} & \color{#ccc}{0} & \text{} & \color{#ccc}{0} & \text{} & \color{#ccc}{0} & \text{} & \color{blue}{1} \\ \end{array}

The colors are for emphasis. The zeros are grayed out so that we can see the pattern formed by the ones more easily. The ones in the last row are colored differently to illustrate how the self-similarity arises in the next step.

Now, suppose that you continue past line $5=2^2+1$ to line $9=2^3+1$, performing your computations mod 2 as you go along. You then get an image that looks like so:

\begin{array}{ccccccccccccccccc} \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & 1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & 1 & \text{} & 1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & 1 & \text{} & \color{#ccc}{0} & \text{} & 1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ \text{} & \text{} & \text{} & \text{} & \text{} & 1 & \text{} & 1 & \text{} & 1 & \text{} & 1 & \text{} & \text{} & \text{} & \text{} & \text{} \\ \text{} & \text{} & \text{} & \text{} & \color{red}{1} & \text{} & \color{#ccc}{0} & \text{} & \color{#ccc}{0} & \text{} & \color{#ccc}{0} & \text{} & \color{blue}{1} & \text{} & \text{} & \text{} & \text{} \\ \text{} & \text{} & \text{} & \color{red}{1} & \text{} & \color{red}{1} & \text{} & \color{#ccc}{0} & \text{} & \color{#ccc}{0} & \text{} & \color{blue}{1} & \text{} & \color{blue}{1} & \text{} & \text{} & \text{} \\ \text{} & \text{} & \color{red}{1} & \text{} & \color{#ccc}{0} & \text{} & \color{red}{1} & \text{} & \color{#ccc}{0} & \text{} & \color{blue}{1} & \text{} & \color{#ccc}{0} & \text{} & \color{blue}{1} & \text{} & \text{} \\ \text{} & \color{red}{1} & \text{} & \color{red}{1} & \text{} & \color{red}{1} & \text{} & \color{red}{1} & \text{} & \color{blue}{1} & \text{} & \color{blue}{1} & \text{} & \color{blue}{1} & \text{} & \color{blue}{1} & \text{} \\ \color{red}{1} & \text{} & \color{#ccc}{0} & \text{} & \color{#ccc}{0} & \text{} & \color{#ccc}{0} & \text{} & \color{#ccc}{0} & \text{} & \color{#ccc}{0} & \text{} & \color{#ccc}{0} & \text{} & \color{#ccc}{0} & \text{} & \color{blue}{1} \\ \end{array}

Some observations now become clear. After a row of $2^n$ ones and no zeros, we will get a new row of $2^n-1$ zeros and with ones on the end. The self-similarity arises because the pattern will now repeat under the new ones at the ends of the last row. Taking the staggered grid into account, the distance of $2^{n}$ between these ones is exactly correct to allow the pattern to continue uninterrupted for another $2^n$ steps, at which point we get another row of $2^{n+1}$ ones.

Of course, this can all be formalized in an inductive proof.