Fractals are self-similar. The Sierpinski Triangle is an interesting fractal pattern. You can build one like this:
- 1. Start with an “upright” equilateral triangle (as seen in stage zero)
- 2. Place an upside-down triangle in the center of any upright triangle
- 3. Repeat Step 2 infinitely
Write a recursive formula that can model how many similar triangles you can count in the figure in a given stage. The figure above will be helpful in finding the pattern.
Extra Challenge: Turn that recursive formula into an explicit formula (i.e. find S(n), where n is the “stage” and S(n) is the number of triangles)
Click for Solutions!
S(0) = 1
S(n) = 3S(n-1) + 2
Base case is 1 because there is only 1 triangle in Stage 0.
Look at the jump from stage 0 to 1. When you add the white triangle, you essentially have 3 smaller versions of Stage 0, along with the central triangle and the entire triangle. That’s 3*1+1+1.
Stage 1 to 2 follows the same pattern. 3(4) + 1 + 1.
Generalize the pattern to obtain your recursive step, S(n) = 3S(n-1) + 2.
—
In order to make an explicit formula, try expanding the recursive step.
S(n) = 3S(n-1) + 2
Replace S(n-1)
S(n) = 3( 3S(n-2) + 2 ) + 2
Replace S(n-2)
S(n) = 3( 3( 3S(n-3) + 2) + 2 ) + 2
Simplify to make the pattern more clear.
S(n) = 3^3 * S(n-3) + 18 + 6 + 2
If you keep on replacing k times you find the pattern:
S(n) = 3^k * S(n-k) + 2 + 6 + 18 + … 2*3k-1
We can get rid of S(n-k) by using our base case of S(0). When k=n, S(n-k) is 0. Thus…
S(n) = 3^n * S(0) + 2 + 6 + 18 + … 2*3n-1
Final Answer:
S(n) =3^n + ( 2+6 + 18 + … 2*3^(n-1) )
Or more formally, using sigma notation:
