5
$\begingroup$

It is well-known that if you isolate the even from the odd terms in Pascal's triangle, you obtain an 'approximation' of Sierpinski’s triangle. Better stated, from user Glorfindel in an answer to this post (edits for correctness):

Pascal's triangle

If one takes Pascal's triangle with $2^n$ rows and colors the even numbers white, and the odd numbers black, the result is an approximation to the Sierpinski triangle. More precisely, the limit as n approaches infinity of this parity-colored $2^n$-row Pascal triangle is the Sierpinski triangle.

My question: what is the analytic/formal proof that this is the case? I can find many resources saying that this happens, but none explain why.

I presume the explanation is because every certain number of rows, the binomial coefficient run through every value is odd, and It follows from Pascal’s identity that even numbers would then appear in a descending pattern resulting in triangles; however, I don’t think this fully explains it.

$\endgroup$
2
  • 2
    $\begingroup$ Note it should be $2^n$, not $2n$ (it was copied wrongly from wikipedia). After you fix that, look at Lucas's theorem for $p=2$ (or really any $p$ for a more complex-looking triangle) $\endgroup$ Commented Mar 5, 2020 at 2:34
  • $\begingroup$ I recommend to see math.stackexchange.com/questions/233269/… $\endgroup$
    – N.S.
    Commented Jun 11, 2022 at 7:33

1 Answer 1

2
$\begingroup$

The following argument is not a proof, but it may be converted to a proof. We will write $0,1$ for the binomial coefficients taken modulo $2$, use tautologically these two colors, $0,1$ to color the coefficients.

The coefficients are considered as elements of the field $\Bbb F_2$. Most of the time we use only its additive structure, i.e. the underlying abelian group structure $\Bbb Z/2$, but at some point i want to use the Frobenius morphism in characteristic two.

The line number zero in the Pascal triangle is simply $$1$$ but it may be useful to think it as $$ \dots\ 0\ 0\ 0\ 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ \dots $$ or as $$ \dots\ 0\ 0\ 0\ 0\ 0\ 0\ \color{red}{\blacktriangle}\ 0\ 0\ 0\ 0\ 0\ 0\ \dots $$ It corresponds to $(1+x)^0$.

For $n=2$, $N=2^2$, we build the Pascal triangle over the field $\Bbb F_2$ up to row number $2^n-1=N-1=3$:

        1
      1   1
    1   0   1
  1   1   1   1

The last line is a line of ones, since the next line, line number $N=2^n$, is corresponding to the (coefficients in the) binomial expansion of $(1+x)^{2^n}=1^{2^n}+x^{2^n}$, so there survive only two extremal $1$ values, all other coefficients are zero. This works for a general $n$. Knowing line $N$, we have only one chance for the line $N-1$, it is a line of ones.

Now put a white $\nabla$ over the $0$ entry, some $\blacktriangle$ over the ones, so that the above may look like $$\blacktriangle\\ \blacktriangle\nabla\blacktriangle $$ and compare with the second triangle in

Sierpinski triangle evolution

In the computation of the next row, row number $2^2$, we have the line $1,0,0,0,1$, as already mentioned. Here is a picture:

          1
        1   1
      1   0   1
    1   1   1   1
  1   0   0   0   1 

And it is useful to think about it like: $$ \color{red}{\blacktriangle}\\ 1\ 1\\ 1\ 0\ 1\\ 1\ 1\ 1\ 1\\ \color{red}{\blacktriangle}\ 0\ 0\ 0\ \color{red}{\blacktriangle} $$ Now we play again the "game of life", where a one bit gives life to the diagonally placed entries in the next row. Then the game works for the two $\color{red}{\blacktriangle}$ entries in the last row, as it worked for the upper $\color{red}{\blacktriangle}$, of course till they "interfere". We know exactly where is the interference, one step before the usage of the next Frobenius power, $(1+x)^8=1+x^8$, well, $(1+x)^7=\frac{1+x^8}{1+x}=\frac{1-x^8}{1-x} =1+x+x^2+\dots+x^7$.

We have the following situation:

              1
            1   1
          1   0   1
        1   1   1   1
      1   0   0   0   1 
    1   1   0   0   1   1
  1   0   1   0   1   0   1
1   1   1   1   1   1   1   1

Now place a white $\nabla$ on the zero entries in the middle, so that the upper bar of $\nabla$ corresponds to the zero entries in the row $1\ 0\ 0\ 0\ 1$, and compare with the next picture in loc. cit. - we have reached the next stage. The next line is again a $1\ 0\ 0\ \dots\ 0\ 0\ 1$ line, and its picture is: $$ \color{red}{\blacktriangle}\\ 1\ 1\\ 1\ 0\ 1\\ 1\ 1\ 1\ 1\\ 1\ 0\ 0\ 0\ 1\\ 1\ 1\ 0\ 0\ 1\ 1\\ 1\ 0\ 1\ 0\ 1\ 0\ 1\\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\\ \color{red}{\blacktriangle}\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ \color{red}{\blacktriangle} $$ The extremal $1$ values in the last row will suffer now the same copy+paste operation from the upper vertex, and we get a bigger $\nabla$ in the middle, we see the upper line of the white $\nabla$ in the last row, and the copy+paste game goes on...


The above inductive construction shows a self-similarity of the "picture" from one step ($N=2^n$) to the next one ($2N=2^{n+1}$), and it is natural to expect a self-similarity in the limit. (After a rigorous definition of the limit.) Note that the above construction goes parallelly to the construction of the Sierpinsky triangle.)


If it is really needed for a special purpose, i may try to become analytic, and establish an analytic formula for points, using their $2$-adic coordinates in the barycentric coordinates of the points inside the Sierpinski triangle - in the level $N$ and in the limit. (It is hard to write it down, and the proof of the convergence will not be intuitive.)

$\endgroup$
5
  • $\begingroup$ Comprehensive answer, but it was not analytic as it was asked. $\endgroup$
    – N.S.
    Commented Jun 11, 2022 at 7:24
  • $\begingroup$ The question was... "what is the analytic/formal proof that this is the case?" It does not define the Pascal triangle, the Sierpinski triangle, and there is no sense given to the "approximation". The above is not a proof, but can be converted into one. But it gives a constructive argument showing how to get an approximation. The argument is formal and precise. It comes with an intuitive support. It shows an inductive step. What is or what would be strictly speaking "analytic" in the given context? I'm open for a critical discussion, but please be more detailed. OP accepted the answer. $\endgroup$
    – dan_fulea
    Commented Jun 12, 2022 at 23:22
  • $\begingroup$ You described in the last paragraph how it should be modified. I had a similar question to that of OP's and found reference to Lucas' theorem and its special case in a question I recommended in a comment above. $\endgroup$
    – N.S.
    Commented Jun 15, 2022 at 8:45
  • $\begingroup$ @N.S. I really do not understand which is the issue. So i am usually asking what i am not understanding, in such a case the discussion makes sense only if answers will show up. (1) In the above comment, which is the "last paragraph" and what is that "it" that should be modified. (2) The similar question linked above, math.stackexchange.com/questions/233269/…, was asked in 2012 by George Krasilnikov, it is not really similar. Both questions are only sharing the same setting. This is not really helpful. (3) Lucas theorem is ... $\endgroup$
    – dan_fulea
    Commented Jun 15, 2022 at 14:06
  • $\begingroup$ ... only dealing with the information in each "cell" of the Pascal triangle. It gives a too explicit information which is not really useful in that granularity for the purpose of the question here. It is ok to comment to the question, and it is ok to comment to my answer, but please leave a message with a clear subject and clear objects. It is hard to understand if the above comments are critical or just adds, and if they are critical - then to what point in the answer at all. (And how should be the answer improved - i would do that - to address the missing points.) $\endgroup$
    – dan_fulea
    Commented Jun 15, 2022 at 14:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .