Vertices of a Serpinski Triangle

When I'm out to eat I like to flip the place-mat over and doodle. Most of these doodles are mathematical in nature, and the other day I was drawing a Sierpinski Triangle. When dinner came, I spilled my corn all over my picture (this is fairly typical of me). Some of the kernels landed on the vertices, and that got me thinking: how many corn kernels would it take to cover a Sierpinski triangle? Alternatively, how many vertices are there on a Sierpinski Triangle? [footnote 1]

The first thing I did was draw some triangles and count their vertices:

(You might notice that my picture is hastily drawn, and not especially fantastic. This is not because I'm incapable producing a good picture [footnote 2], but because I want to illustrate a point: you don't have to have advanced equipment to do math. You don't need expensive books and graphing calculators, just a pencil and paper.)

Next I looked at the number of vertices on each triangle and tried to find a pattern. One of the first things I noticed was the number of vertices increases by a power of three each time (3,9,27...). That meant that all I had to do to find the number of vertices on the next triangle was add the appropriate power of three to the current number of vertices. That lead me to this formula:



This is good, but not great. This is what's called a recursive formula, the next term in the sequence relies on the one before it. So if I want to find out how many vertices the 100th Sierpinski triangle has, I have to first find out how many the 99th has. But to find that out, I have to find out how many the 98th has. And so on. That's too much work, what I really want is a formula that just tells me how many vertices the the 100th triangle has without having to compute all the others.

So I tried making some other observations. I thought about how the next triangle in the sequence was generated:

This gave me an interesting perspective: Each new triangle is just three of the previous triangles put together, with just three overlapping points (circled in black). So each triangle has triple the vertices of the previous triangle, minus the three overlaps:



This is better than the last one (easier to compute), but it's still recursive. But here's where the magic happens. Both equations describe the same thing (the next term in the sequence), so that means both equations must be equal:



Now all that needs to be done is solve for :



And I have my explicit formula. Notice that what I wanted (the explicit formula) came from two things I didn't want (my recursive formulas). This happens all the time in math: partial or "incorrect" results can lead you to what you were looking for in a way you didn't expect.

-Nick

[1] A vertex is any place two or more edges (lines) meet. So, basically any corner.
[2] In fact, here's a picture I made with Processing in about 15 minutes: