Lesson 13

Now the Sierpiński triangle is no longer a mystery. Look at the first \(2^{r}\) rows of Pascal's triangle modulo \(2\) and call this picture \(P_{r}\). Now pass from the first \(2^{r}\) rows to the first \(2^{r+1}\) rows. Write \[n=a2^{r}+n',\qquad k=b2^{r}+k',\] where \(a,b\in\{0,1\}\) and \(0\le n',k'<2^{r}\). The digit \(a\) tells whether row \(n\) is in the top half or in the bottom half. The digit \(b\) tells whether \(k\) is in the left half or in the right half.

Lucas's theorem gives \[\binom{n}{k}\equiv \binom{a}{b}\binom{n'}{k'}\pmod 2.\] There are only four possibilities for the first factor: \[\begin{array}{c|cc} & b=0 & b=1\\ \hline a=0 & 1 & 0\\ a=1 & 1 & 1\end{array}\] So three blocks repeat the old picture \(P_{r}\), while the top-right block is zero.

So, if we write the triangular picture inside a rectangle and put zeros outside the triangle, the picture is \[P_{r+1}= \begin{pmatrix}P_r & 0\\ P_r & P_r\end{pmatrix}.\] Here we draw an odd coefficient as a dot and an even coefficient as an empty place.