On the Number of Triangles in the Sierpinski Triangle.

This is the ever-famous Sierpinski triangle, a relatively simple triangle generated by dividing a starting triangle into 4 equal smaller triangles, then ignoring the centre triangle and performing the same process on the others.

While this was brought up in class, the person sitting beside me brought up an interesting problem: "How many triangles are present in any particular depth of generation?" Which I found very interesting! So here is how we (mostly he) solved it together.

If we think of the triangle as being generated by "Removing" the centre triangle each time, the problem is relatively simple. If we think of the single triangle as generation 0, we have the number of triangles being T_n = 3^n where n is the amount of generations.

The problem gets a bit more complicated when you take the centres into account. In this case we can think of it as 1 when n=0, and then since we are generating but ignoring the centres, we can think of those as the amount of triangles in generation n-1 starting at generation 1, giving us T_n=3^n+T_n-1. However maybe it is possible to get an explicit statement of the equation? Well, let us think about what the equation is for each of the n's and see if we can get a pattern. So:
T_1 = 3^1+3^0
T_2 = 3^2+T_1=3^2+3^1+3^0
T_3 = 3^3+3^2+3^1+3^0...

T_n = sum from 0 to n of 3^n

Can we go further though?

Well:
T_n = 3^0+3^1+...+3^n
3T_n = 3^1+3^2+...+3^(n+1)
3T_n = 3^1+3^2+...+3^(n+1)+3^0-3^0
3T_n = T_n+3^(n+1)-1
2T_n = 3^(n+1)-1
T_n = [3^(n+1)-1]/2

Which gives us an explicit answer that doesn't require knowing T_(n-1) :-)