We have a collection of identical spheres that we stack to form a tetrahedron whose edges all have $n$ spheres. Calculate, in terms of $n$, the total number of tangency points (contacts) between the spheres in the pile.

## Solution.

## The problem in the plane.
Let's first analyze the problem in the plane. Let $A_{n}$ be the number of contacts of $n$ spheres arranged in a triangle with $n$ spheres on each side (right figure). Note that the total number of spheres is, obviously, $T_{n}=\frac{n(n+1)}{2}$.

We can proceed by induction. If there are $n=2$ rows, the number of contacts is 3; that is, $A_{2}=3$. Observe that this coincides with the number of balls in the triangle of two rows.

In a triangle of $n-1$ rows, there are $A_{n-1}$ contacts. Obviously, in a triangle of $n$ rows, there will be the contacts that were already in a triangle of $n-1$ rows, plus those that come from adding the last row, as indicated in the figure above. But it is clear that, by adding this last row, contacts of two types are produced:

- The ones between the balls of the $n$-th row, which are $n-1$.
- The ones between the balls of the $n$-th row and the previous one. They are $2(n-1)$.

Thus, $A_{n}=A_{n-1}+3(n-1)$, or, $A_{n}-A_{n-1}=3(n-1)$. Summing up, we get

$$
A_{n}=3((n-1)+(n-2)+\cdots+2+1)=3 \frac{n(n-1)}{2}=3 T_{n-1}
$$

## The problem in three-dimensional space.

Now we can analyze the case in space. Let $C_{n}$ be the number of contacts of a tetrahedral pile of spheres with edges of $n$ spheres. In the figure on the right, we have represented the spheres of the base in solid lines and those of the immediate upper floor in dashed lines, from a bird's-eye view. When we add the $n$-th floor, we add contacts of two types:

- The ones of the floor itself - a plane triangle of $n$ balls on a side.

- The ones that come from contacts between the $n-1$-th floor and the $n$-th floor.

The contacts of the first type are, as we have seen in the plane case, $A_{n}=3 T_{n-1}$.

The number of contacts between one floor and the previous one is $3 T_{n-1}$, since each ball of the $n-1$-th floor touches exactly three balls of the $n$-th floor. (See the figure.) In total, then, the number of contacts is $C_{n}-C_{n-1}=A_{n}+3 T_{n-1}=3 n(n-1)$. If we sum up, we get

$$
C_{n}-C_{2}=3 n(n-1)+\cdots+3 \cdot 3(3-1)=3\left(n^{2}+\cdots+3^{2}\right)-3(n+\cdots+3)
$$

or

$C_{n}=3\left(n^{2}+\cdots+2^{2}+1^{2}\right)-3(n+\cdots+2+1)=3 \frac{n(n+1)(2 n+1)}{6}-3 \frac{n(n+1)}{2}=n^{3}-n$.

Another approach. The recurrence $C_{n}=C_{n-1}+3 n(n-1)$ can be solved by writing $C_{n}$ as a cubic polynomial and calculating its coefficients from the recurrence and the initial condition $C_{1}=0$.

If we put $C_{n}=a n(n-1)(n-2)+b n(n-1)+c n+d$, the recurrence condition gives $a=1, b=3, c=0$, and the condition $C_{1}=0$ gives $d=0$. In summary,

$$
C_{n}=n(n-1)(n-2)+3 n(n-1)=n^{3}-n
$$

## C3.