# 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

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.