Home > Quick Problems > Arithmetic

Note: this page uses MathJax for formatting, so may take a few seconds to load.

function showSolution() {
if (document.getElementById('divSolution').style.display == "none")
{ document.getElementById('divSolution').style.display = "block"; }
else
{ document.getElementById('divSolution').style.display = "none"; }
}
\[
S = 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdots + 100 \cdot 101
\]
Solution
document.getElementById('divSolution').style.display = "none";

Note: this page uses MathJax for formatting, so may take a few seconds to load.

What Is The Sum?

We use a multiplication trick. Multiply by $3$: \[ 3S= 1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 3 + 3 \cdot 4 \cdot 3 + \cdots + 100\cdot 101 \cdot 3. \] Write the last $3$ in each product (after the first) as a difference of two numbers: \[ 3S=1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot (4-1) + 3 \cdot 4 \cdot (5-2) + \cdots+ 100\cdot 101 \cdot (102-99). \] This results in a telescoping series: \[ 3S=1 \cdot 2 \cdot 3+2 \cdot 3 \cdot 4 - 1 \cdot 2 \cdot 3 +3 \cdot 4 \cdot 5 -2 \cdot 3 \cdot 4+ \cdots +100\cdot 101 \cdot 102-99 \cdot 100 \cdot 101. \] The telescoping series collapses to yield \[ 3S = 100 \cdot 101 \cdot 102, \] and hence \[ S = \frac{100 \cdot 101 \cdot 102}{3}=343{,}400. \]

Using the same ``multiply by $3$ trick,'' we can show that \[ 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdots + n (n+1) = \frac{n(n+1)(n+2)}{3}. \] Similarly, we can find a formula for \[ S= 1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + 3 \cdot 4 \cdot 5 + \cdots + n (n+1) (n+2). \] Simply multiply by $4$ and collapse the telescoping series: \[ S = \frac{n(n+1)(n+2)(n+3)}{4}. \]

Given any integer $t \geq 1$, this technique (via multiplication by $t+1$) shows that \[ \sum_{k=1}^n k(k+1)(k+2)\ldots(k+t-1) = \frac{n(n+1)(n+2)\ldots(n+t)}{t+1}. \] Here is a counting proof of this identity. Given a group of $n+t$ people, the number of ways to seat $t+1$ of the people around a circular table, where only the order of the people around the table matters, is \[ \frac{(n+t)(n+t-1)\ldots n}{t+1}. \] The reason is that there are $n+t$ choices for who sits at the "head" of the table, then $n+t-1$ choices for who sits to that person's right, and so on. Since there really is no head of a circular table, we divide by $t+1$ to eliminate rotations of seatings. The expression obtained is the right side of the identity. Suppose that the people are labeled from $1$ to $n+t$. Then the number of ways to seat the $t+1$ people if the seated person with the highest label is $k+t$, where $1 \leq k \leq n$, is \[ (k+t-1)(k+t-2)\ldots k. \] This is because there are $k+t-1$ choices for who sits to the right of the person with the highest label, $k+t-2$ choices for who sits to that person's right, etc. The sum of these terms is the left side of the identity, and that completes the proof.

Notice that the $t=1$ case of the identity is the well-known formula for the sum of the first $n$ integers: \[ \sum_{k=1}^nk= \frac{n(n+1)}{2}. \]