(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} \).

Anyway, here’s the answer:

\(\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.

This entry was posted in Mathematics and tagged , , . Bookmark the permalink.

4 Responses to (How many) triangles in a triangle?

  1. Eric says:

    You really have far too much time on your hands… but thanks for the info :)

  2. Mr.Pauli says:

    beautiful solution! :D

  3. Josh says:

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

Leave a Reply