Problem 790

Let the $k^{\text{th}}$ level of the pyramid from the top be an equilateral triangle of size $n$. It therefore contains $T_{k}$ balls where $T_{k}$ corresponds to the $k^{\text{th}}$ triangular number. Thus, the total number of balls is:

$$\begin{aligned} \sum_{k=1}^{N} T_{k} & =\sum_{k=1}^{N} \frac{k(k+1)}{2} \\ & =\sum_{k=1}^{N}\binom{k+1}{2} \\ & =\sum_{k=2}^{N+1}\binom{k}{2} \end{aligned}$$

Let's prove by induction on $n \geq 2$ that $\sum_{k=2}^{n}\binom{k}{2}=\binom{n+1}{3}$:

Initialization: if $n=2$, then:

$$\sum_{k=2}^{2}\binom{k}{2}=1=\binom{2+1}{3}$$

The initialization is verified.

Hereditary: suppose that for a fixed $n$, we have $\sum_{k=2}^{n}\binom{k}{2}=\binom{n+1}{3}$ (induction hypothesis). In this case, we have:

$$\begin{aligned} \sum_{k=2}^{n+1}\binom{k}{2} & =\sum_{k=2}^{n}\binom{k}{2}+\binom{n+1}{2} \\ & =\binom{n+1}{3}+\binom{n+1}{2} \\ & =\binom{n+2}{3} \end{aligned}$$

The hereditary property is verified.

Finally, by induction, we can assert that $\sum_{k=2}^{N+1}\binom{k}{2}=\binom{N+2}{3}$. Therefore, the number of balls is $\binom{N+2}{3}$.

Inspired by the proof above for the hereditary property, we can show by induction on the dimension $d$ of the hypertetrahedron that the total number of balls is $\binom{N+d-1}{d}$.