1
$\begingroup$

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.

Images of S0. S1. S2 enter image description here

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.

My answer:

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 enter image description here enter image description here I know the final answer is supposed to be $${3n^2+3n+2 \over2}$$

$\endgroup$
2
  • $\begingroup$ 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$ $\endgroup$
    – Daniel Mathias
    Feb 7, 2019 at 17:11
  • $\begingroup$ @DanielMathias yea youre right. It should be 20 triangles. So my entire formula is wrong $\endgroup$
    – Omer Khan
    Feb 7, 2019 at 17:34

1 Answer 1

Reset to default
0
$\begingroup$

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$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.