# (How many) triangles in a triangle?

I hope most of you will be familiar with the “how many triangles” puzzle. If you aren’t, here’s a nice demonstration for you.

Given any triangle, let’s call the number of base triangles $$n$$. So the above picture has $$n=7$$. We’ll call the total number of triangles $$c_n$$. The picture above has $$c_n=118$$. Now let’s try to find a formula for $$c_n$$.

### Normal triangles

We can break the problem up into two parts. Let $$a_n$$ be the number of “normal” triangles (those with an edge on the bottom) in a picture, and let $$b_n$$ be the number of inverted triangles (those pointing down). So we can start by considering a few small values of $$n$$ while only counting normal triangles:

From the above, we have $$a_1=1$$, $$a_2=4$$, $$a_3=10$$, and $$a_4=20$$. There doesn’t seem to be any simple pattern here, so let’s try to construct a recurrence relation. Note that the $$n=4$$ triangle contains two $$n=3$$ triangles:

It looks like we can write $$a_4=2a_3+\mathrm{something}$$. But we’ve counted the region shaded yellow twice, so we need to subtract all triangles contained within that region: $$a_4=2a_3-a_2+\mathrm{something}$$. Finally, notice that there are four new triangles we haven’t counted yet:

So $$a_4=2a_3-a_2+4$$. Let’s check if this works: $$a_4 = 2 \times 10 – 4 + 4 = 20$$. It does! With a bit of thinking, we can generalize this to arbitrary $$n$$: $$a_n = 2a_{n-1} – a_{n-2} + n$$. Now we just have to solve the recurrence relation. There are various ways of doing this, but let’s use generating functions. Here’s our setup:

$$a_1=1$$
$$a_2=4$$
$$a_n=2a_{n-1}-a_{n-2}+n$$

Multiplying both sides and summing on $$n$$:

$$\displaystyle \sum_{n\ge3} a_n x^n = 2\sum_{n\ge3} a_{n-1} x^n – \sum_{n\ge3} a_{n-2} x^n + \sum_{n\ge3} n x^n$$

Now we need to make the sums on the right look like the one on the left.

$$\displaystyle \sum_{n\ge3} a_n x^n = 2x\sum_{n\ge3} a_{n-1} x^{n-1} – x^2 \sum_{n\ge3} a_{n-2} x^{n-2} + x^3 \sum_{n\ge3} n x^{n-3}$$

$$\displaystyle = 2x\sum_{n\ge2} a_n x^n – x^2 \sum_{n\ge1} a_n x^n + x^3 \sum_{n\ge3} n x^{n-3}$$

$$\displaystyle = 2x\left( \sum_{n\ge3} a_n x^n + 4x^2 \right) – x^2\left( \sum_{n\ge3} a_n x^n + x + 4x^2 \right) + x^3 \sum_{n\ge0} n x^n + 3x^3 \sum_{n\ge0} x^n$$

$$\displaystyle (1-2x+x^2) \sum_{n\ge3} a_n x^n = 7x^3 – 4x^4 + x^3 \sum_{n\ge0} n x^n + 3x^3 \sum_{n\ge0} x^n$$

Using the standard formulas for $$\sum_{n\ge0} n x^n = \frac{x}{(1-x)^2}$$ and $$\sum_{n\ge0} x^n = \frac{1}{1-x}$$,

$$\displaystyle (1-x)^2 \sum_{n\ge3} a_n x^n = 7x^3 – 4x^4 + \frac{x^4}{(1-x)^2} + \frac{3x^3}{1-x}$$

$$\displaystyle \sum_{n\ge3} a_n x^n = \frac{x^4}{(1-x)^4} + \frac{(7x^3-4x^4)(1-x)+3x^3}{(1-x)^3}$$

$$\displaystyle = \frac{x^4}{(1-x)^4} + \frac{10x^3-11x^4+4x^5}{(1-x)^3}$$

$$\displaystyle = \sum_{n\ge0}\binom{n+3}{3} x^{n+4} + 10\sum_{n\ge0}\binom{n+2}{2} x^{n+3} – 11\sum_{n\ge0}\binom{n+2}{2} x^{n+4} + 4\sum_{n\ge0}\binom{n+2}{2} x^{n+5}$$

$$\displaystyle a_n = \binom{n-1}{3} + 10\binom{n-1}{2} – 11\binom{n-2}{2} + 4\binom{n-3}{2}$$

After a lot of simplifying, we get $$\displaystyle a_n = \frac{n(n+1)(n+2)}{6}$$. Awesome.

### Inverted triangles

Now for the other half of the problem: the number of inverted triangles, denoted by $$b_n$$. Again, let’s look at a few small cases:

We have $$b_1=0$$, $$b_2=1$$, $$b_3=3$$, and $$b_4=7$$. As with the normal triangles, there is no obvious pattern. However, the recurrence relation looks somewhat familiar:

Consider $$b_4$$. We can make a $$n=4$$ triangle by combining two $$n=3$$ triangles, subtracting a $$n=2$$ triangle, then adding on two new inverted triangles. So $$b_4=2b_3-b_2+2$$. Let’s check this: $$b_4 = 2 \times 3 – 1 + 2 = 7$$, which is correct. How about $$b_5$$? From the above picture, $$b_5=2b_4-b_3+2$$. Hmm, the constant at the end of the equation is still 2. But $$b_6=2b_5-b_4+3$$! Upon closer inspection it looks like whenever $$n$$ is even a large inverted triangle pops up in the middle (green in the picture). But when $$n$$ is odd, there isn’t enough space for a new triangle, so the constant stays the same. This means

$$b_1=0$$
$$b_2=1$$

$$\displaystyle b_n=2b_{n-1}-b_{n-2}+\left\lfloor\frac{n}{2}\right\rfloor$$

Solving this is an extremely tedious process, so I won’t bore you with it. If you want to try, you (may) want to note that

$$\displaystyle \left\lfloor\frac{n}{2}\right\rfloor = \frac{2n+(-1)^n-1}{4}$$.

$$\displaystyle b_n = \frac{1}{16} (-1)^n + \frac{5}{16} – \frac{1}{8}\left(n+1\right) + \frac{13}{4}\binom{n-1}{2} – 3\binom{n-2}{2} + \binom{n-3}{2} + \frac{1}{2}\binom{n-1}{3}$$

We can simplify it down to

$$\displaystyle b_n = \frac{1}{16} (-1)^n + \frac{(2n+1)(2n^2+2n-3)}{48}$$

### The solution

We’re almost done. $$c_n$$ is the total number of triangles, normal and inverted, so $$c_n=a_n+b_n$$. This simplifies to:

$$\displaystyle c_n = \frac{4n^3+10n^2+4n-1+(-1)^n}{16}$$

If $$n$$ is even, $$\displaystyle c_n = \frac{1}{8}n(n+2)(2n+1)$$. If $$n$$ is odd, $$\displaystyle c_n = \frac{1}{8}\left[n(n+2)(2n+1)-1\right]$$.

### One final note

One quick way of solving for $$a_n$$ is to note that the solution must be a cubic and then create an interpolating polynomial with the first four data points. This can also be done for $$b_n$$ except that the even/odd cases should be treated separately.

## 4 thoughts on “(How many) triangles in a triangle?”

1. Josh

I have pattern for a complete results. Without x.125 or x.875 is very similar but different.