# Toothpicks in the nth figure problem where the figures are "L" shaped triangles

#### charlieanne

##### New member
Hi, I did a search in the forums and found a similar problem, but nothing on this particular one. I have a problem asking for a procedure to find the number of toothpicks in any figure in a sequence, with an illustration that shows the first three figures of the sequence of triangles built with squares made up of toothpicks. The figures are "L" shaped meaning that the first "triangle" starts with a square and then has another square directly above and directly to the right of it with 1 shared toothpick for each new square (10 toothpicks total). The next is the same concept but with one square added into the middle of the two arms (18 toothpicks). I have drawn out the first 10 figures on graph paper but can't seem to find a pattern to figure out a procedure that will work no matter what tn I'm trying to find. #### earboth

##### Active member
Hi, I did a search in the forums and found a similar problem, but nothing on this particular one. I have a problem asking for a procedure to find the number of toothpicks in any figure in a sequence, with an illustration that shows the first three figures of the sequence of triangles built with squares made up of toothpicks. The figures are "L" shaped meaning that the first "triangle" starts with a square and then has another square directly above and directly to the right of it with 1 shared toothpick for each new square (10 toothpicks total). The next is the same concept but with one square added into the middle of the two arms (18 toothpicks). I have drawn out the first 10 figures on graph paper but can't seem to find a pattern to figure out a procedure that will work no matter what tn I'm trying to find.

View attachment 359
1. I've modified your sketch a little bit (see attachment). I assume that you have n toothpicks in the base row.

2. If you count the rows of toothpicks (green) you'll get:

n+n+(n-1)+(n-2) + ... + 1

3. If you count the columns of toothpicks (red) you'll get:

n+n+(n-1)+(n-2) + ... + 1

4. So in total you have:

2(n+n+(n-1)+(n-2) + ... + 1)

5. Use the sum formula of arithmetic sequences to simplify this term. Finally you should come out with
$$n^2+3n$$

#### Attachments

• 56.4 KB Views: 36

#### MarkFL

Staff member
I observed that for 0 squares there are 0 toothpicks, for 1 square there are 4 toothpicks, for 3 squares there are 10 toothpicks...

On the nth interation, there are $\displaystyle T_n$ squares, where $\displaystyle T_n$ denotes the nth triangular number.

If we notice that the second difference is constant at 2, then we know the number of toothpicks $\displaystyle t_n$ will be a quadratic function:

$\displaystyle t_n=k_1n^2+k_2n+k_3$

where:

$\displaystyle t_0=0$

$\displaystyle t_1=4$

$\displaystyle t_2=10$

giving rise to the system:

$\displaystyle k_3=0$

$\displaystyle k_1+k_2=4$

$\displaystyle 4k_1+2k_2=10$

from which we may determine:

$\displaystyle k_1=1,k_2=3$

Hence:

$\displaystyle t_n=n^2+3n$

#### soroban

##### Well-known member
Hello, charlieanne!

I have drawn out the first 10 figures on graph paper, but can't seem to find a pattern.
I'm surprised . . . Where were you looking?

I assume you counted the toothpicks in your 10 diagrams.

So you have: .$$4,10, 18, 28, 40, 54, 70, 88, 108, 130$$

We see that the numbers are getting bigger. .(duh!)

Okay, just how are they getting bigger?

Let's take a look . . .

$$\begin{array}{c|ccccccccc}\hline \text{Sequence}& 4 && 10 && 18 && 28 && 40 && \cdots \\ \hline \\ \text{Change} && +6 && +8 && +10 && +12 && \cdots \\ \hline \end{array}$$

Do you see a pattern now?

#### charlieanne

##### New member
Hello, charlieanne!

I assume you counted the toothpicks in your 10 diagrams.

So you have: .$$4,10, 18, 28, 40, 54, 70, 88, 108, 130$$

We see that the numbers are getting bigger. .(duh!)

Okay, just how are they getting bigger?

Let's take a look . . .

$$\begin{array}{c|ccccccccc}\hline \text{Sequence}& 4 && 10 && 18 && 28 && 40 && \cdots \\ \hline \\ \text{Change} && +6 && +8 && +10 && +12 && \cdots \\ \hline \end{array}$$

Do you see a pattern now?
Hi Soroban,

Sorry, I should have been more clear: I did see that pattern (and also that the # of 3s goes up by two, and that the 2s go up 4,5,6,7,8,etc). I'm trying to understand why the formula tn=n2+3n works...I see that it does, just not how it works. (Example: I know that the formula for volume is HxLxW, but I can also explain the concept.)

#### soroban

##### Well-known member
Hello again, charlieanne!

$$\text{I'm trying to understand why the formula }\,t_n \,=\,n^2+3n\text{ works.}$$
The "why" is tricky to explain.
I have some explanations, but they may not convince you.

We saw that the generating function is a quadratic, contains $$n^2.$$
Very well, let's test $$f(n) \,=\,n^2$$

$$\begin{array}{c|cccccccccc} n & 1&2&3&4&5&6&7 \\ \hline \text{Sequence} & 4&10 & 18 & 28 & 40 & 54 & 70 \\ \hline \text{Try }n^2 & 1 & 4 & 9 & 16 & 25 & 36 &49 \\ \hline \text{Error} & \text{-}3 & \text{-}6 & \text{-}9 & \text{-}12 & \text{-}15 & \text{-}18 & \text{-}21 \\ \hline \end{array}$$

We see that if we use $$f(n) \,=\,n^2$$, we are short by exactly $$3n.$$

Therefore, the function is: .$$f(n) \:=\:n^2+3n$$

Factor the numbers in the sequence
. . and look for a pattern.

. . . $$\begin{array}{ccc} n & t_n & \text{factors} \\ \hline 1 & 4 & 1\cdot4 \\ 2 & 10 & 2\cdot 5 \\ 3 & 18 & 3\cdot6 \\ 4 & 28 & 4\cdot7 \\ 5 & 40 & 5\cdot8 \\ 6 & 54 & 6\cdot9 \\ 7 & 70 & 7\cdot10 \\ \vdots & \vdots & \vdots \\ n & t_n & n(n+3) \end{array}$$

#### MarkFL

Staff member
Another method would be to express the relation recursively:

$\displaystyle t_{n}=t_{n-1}+2n+2$

$\displaystyle t_{n+1}=t_{n}+2(n+1)+2$

Subtracting the former from the latter:

$\displaystyle t_{n+1}=2t_{n}-t_{n-1}+2$

$\displaystyle t_{n+2}=2t_{n+1}-t_{n}+2$

Subtracting again:

$\displaystyle t_{n+2}=3t_{n+1}-3t_{n}+t_{n-1}$

We find the characteristic roots are 1 with multiplicity 3, hence the closed form will be quadratic, for which the parameters are determined by initial values.