The number of triangles in the fractal, which is formed from a square by the additional construction of isosceles right triangles

Question

There is an algorithm for constructing a fractal:

1. Take a square with a side of size 1;
2. An isosceles right triangle is completed on each side;
3. GOTO step 2.

There is an example of that shape:

How can I find the number of triangles in the i-th iteration of the algorithm? Initially, I thought it was just a power of 2, but the construction of the 5th and 6th generations showed that this was not the case. (Since the figure tends to the octagon and at some iterations it becomes one).

Answer 1

Often, we expect the rate of growth of these types of geometric constructions to obey a recurrence relation. That is, if we let $a_n$ denote the number of triangles that are produced at the $n^{th}$ stage, then we expect $a_n$ to be a linear combination of a few of the previous terms. For a third level recurrence (as it turns out we have here), we would expect that $$a_n = A a_{n-1} + B a_{n-2} + Ca_{n-3}.$$ Here are two approaches to finding this recurrence: one experimental that's not too hard on a computer and one theoretical that justifies the experimental approach.

Experimental

The experimental approach is to simply generate the triangles on a computer and remove the overlapping triangles programmatically.

Keeping track of how many were produced at each step, we find the following sequence:

4, 8, 16, 24, 40, 56, 88, 120, 184, 248, 376, 504, 760

Assuming that the sequence obeys the third order recurrence described above, we would find that

$$\begin{aligned} 24 &= 16A + 8B + 4C \\ 40 &= 24A + 16B + 8C \\ 56 &= 40A + 24B + 8C \end{aligned}$$

We could then solve for $A$, $B$, and $C$ to find that $$ a_n = a_{n-1} + 2a_{n-2} - 2a_{n-3}. $$ That, together with the initial conditions that $$a_0 = 4, \: a_1 = 8, \text{ and } \, a_2 = 16$$ uniquely determine the sequence. You can check that this sequence generates the terms above. There's even a closed form for $a_n$:

$$ a_n = 3\ 2^{\frac{n}{2}+1}+3 (-1)^n 2^{\frac{n}{2}+1}+2^{\frac{n}{2}+\frac{5}{2}}-(-1)^n 2^{\frac{n}{2}+\frac{5}{2}}-8. $$

Analysis by type

If you look at the picture for while you might notice four types of triangles, classified by their geometric relationship to their neighbors, as illustrated here:

The subscripts indicate the angles (in multiples of $\pi/4$) that you see between the left and right legs of the red triangle and the gray triangle that shares the left or right vertex of the red triangle.

Each of these 4 types produces new triangles at the next level that is again one of those types. Those reproduction rules obey the following formulae:

$$\begin{aligned} T_{4,4} &\to 2T_{2,4} \\ T_{2,4} &\to T_{2,4} + T_{0,4} \\ T_{0,4} &\to T_{2,2} \\ T_{2,2} &\to 2T_{0,4} \end{aligned}$$

We could summarize these reproduction rules with a matrix:

$$M = \begin{pmatrix} 0 & 2 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 2 & 0 \end{pmatrix}$$

Note that if we have a vector $\vec{x} = \langle x_1,x_2,x_3,x_4 \rangle$ where $x_i$ tells us how many configurations of type $i$ lie in the outer layer of the picture, then the vector $M\vec{x}$ will tell us how many of each type are produced at the next level.

Furthermore, there is a well established relationship between this matrix and the recursive approach. In particular, the characteristic polynomial of the matrix is $$ \lambda ^4-\lambda ^3-2 \lambda ^2+2 \lambda $$ If we set that equal to zero and solve for $\lambda^4$, we get $$ \lambda ^4=\lambda ^3 + 2 \lambda ^2 - 2 \lambda $$ and you can read the coefficients of the recursion formula right off the right hand side.