Solving a recurrence relation in series of triangles.

Given an equilateral triangle as shown in figure (a), if we draw one line parallel to each side such that the 3 lines divide each side into 2 segments of equal length, then we will get the figure as shown in figure (b). Let us call the triangle in (a) S0, the figure in (b) S1. Similarly, we can draw k lines parallel to each side such that the 3k lines divide each side into (k+1) segments of equal length. Let us call the figure Sk. As an example, figure (c) shows the figure S2.

Now, we wish to count how many upright triangles are contained in Sk. A triangle is called upright if the base is at the lower side. In figure (b), the triangle abc in S1 is not an upright triangle because the line (a, b) is at the upper side of node c. Thus, S1 contains 4 upright triangles, including 3 smaller ones plus efg. It is not difficult to see that S2 contains 10 upright triangles. Let a be the number of upright triangles that Sn contains. Find a recurrence relation for an and solve it.

I made a relationship of the number of parallel lines to the number of upright triangles. This gave me the following open formula equation. I used that equation to recursively solve for a closed formula. But my final equation falls off and does not match the sequence for some of the numbers. Pic#1, Pic#2 I know the final answer is supposed to be $${3n^2+3n+2 \over2}$$
• You have miscounted the number of upright triangles in $S_3$. The correct count is $a_3=20$. Going further: $a_4=35$, $a_5=56$ Feb 7, 2019 at 17:11
Removing the bottom row from $$S_n$$ leaves a figure identical to $$S_{n-1}$$. Therefore, $$a_n-a_{n-1}$$ is the number of upright triangles in $$S_n$$ which are not contained in this upper $$S_{n-1}$$. In other words, $$a_n-a_{n-1}$$ counts the number of triangles which lie flat on the bottom of $$S_n$$. Such a triangle is uniquely specified by its upper vertex; given the upper vertex, you can recover the triangle by drawing sides downwards at $$60^\circ$$ slopes. Since there are $$1+2+\dots+(n-1)=\binom{n}2$$ possibilities for this upper vertex, you get $$a_n=a_{n-1}+\binom{n}2$$ This is a non-homogeneous linear recurrence. Can you solve this for $$a_n$$?