# Sierpinksi like triangle construction. How to find the number of triangles in each iteration?

So here is the question: If we look at the Sierpinski triangle (left column of attached image) and think about how many triangle's it takes to make the shape at each iteration we can get the sequence $\frac{3^n -1}{2}$ for $n \in N$. If we look at another shape that we'll call the Inverted Sierpinski triangle (right column of attached image) where we take the center most triangle and turn it into 4 triangles we can find a sequence to give use the number of triangles as $3n+1$ for $n \in N$. Both sequences diverge to infinity. But do they go to the same infinity? e.g. Which shape has more triangles after an infinite number of iterations?

Now I think that they go to different infinity's here is my reasoning. If I look at the sequence $\{(\frac{3^n -1}{2})- (3n+1)\}= \{0,0,6,30,108...\}$ this seems to suggest to me that after the second iteration of drawing the shapes I can take the triangles in the Inverted Sierpinski triangle and match them 1-1 with some of the triangles in the Sierpinski triangle but I'll have left overs after every iteration. Is it enough to claim that because this series $\{(\frac{3^n -1}{2})- (3n+1)\}$ diverges that the two shapes contain a different infinity of triangles? If not how would one show this?

PS: If the second shape has an actual name can someone point that out as well?

PPS: I didn't name the second shape it comes from the classmate who got us started in thinking about the problem.

-
This might interest you: en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel – Aryabhata Feb 16 '12 at 18:07
When would you consider two infinities "different," OP? Normally we don't use asymptotic analysis but rather bijections to talk about cardinalities of sets. – anon Feb 16 '12 at 19:10
Try making a bijection from each of the sequences to the integers. – Pedro Tamaroff Feb 17 '12 at 3:21

## 2 Answers

Both pictures contain the same number of triangles. The same as the cardinality of the integers. It is true that at every finite iteration the diagram on the left will have more triangles than the one on the right. But you can define a bijection between the two sets of triangles. The triangles on the right you can easily think of being labeled 1, 2, 3, ..., likewise I can label all of the triangles on the left with the natural numbers. This clearly gives a bijection between the two sets, they must contain the same number of elements.

As in the comments you should have a look at the Hilbert Hotel paradox, as this really is the same problem. You are just showing that $\mathbb{N}$ has the same cardinality as $\mathbb{3N}$.

-
The number of triangles in the two go as $3^n$ and $n$, but your statement that they have the same number of elements in the limit is correct. I would state it that you have shown that $\{n\in \mathbb N\}$ has the same cardinality as $\{3^n | n \in \mathbb N \}$ – Ross Millikan Apr 23 '12 at 2:42

Imagine some axes, so we're in the $xy$-plane and can talk about the co-ordinates of points. The points with both co-ordinates rational are dense in the plane, so every triangle contains one (in fact, contains infinitely many, but one will do). The number of points in the plane with both co-ordinates rational is a countable infinity, so the number of triangles is countable - that goes for both of your triangle constructions. But there is only one countable infinity, so, in the limit, both constructions yield the same number of triangles.

The above presupposes that you know something about cardinalities of infinite sets. If not, there are any number of books (intro set theory textbooks, or popularizations that have a chapter on infinity) and web sites that will fill you in.

-