Prove $1\times 2+2\times 3+\ldots+(n-1)\times n = 2\binom {n+1}{3}$

Question

I tried to find a combinatorial proof of it and made some progress, but I am not sure whether my proof is correct. It is samiliar to this question but the answer are different.

From the RHS,

I consider an ordered triples $(x, y, z)$ of integers in the way of a similiar question answered by Mike Earnest.

• $0\leq x < z$
• $0 \leq y < z$
• $1 \leq z \leq n$
• $x \neq y$ (new added)

There are two cases for $(x, y)$ which are $x < y$ and $x > y$.
Suppose $x < y$, to form subset of $\{x, y, z\}$ of $\{1,...,n\}$ . There are $\binom {n+1}{3}$ ways.
(Update: The correct version should be $\{0,...,n\}$)
Suppose $x > y$, the number of ways to form $\{x, y, z\}$ is identical to the former one.
Therefore, it is total of 2$\binom {n+1}{3}$

From LHS,
Since, $1\times 2+2\times 3+\ldots+(n-1)\times(n) = {\sum_{i=2}^n} i(i-1)\tag*{}$

To apply the same principle as RHS.
When $z = 2$, there are two ways, $(0, 1, 2)$ and $(1, 0, 2)$ which satisfy $1\times 2$.
This looks like a pattern of placing two numbers to a space created by $z$, i.e. $\{0,..,z-1\}$, which is $z(z-1)$

Therefore, the total number of ways for z is ${\sum_{i=2}^n} i(i-1)$
Thanks for reading this question.

Answer 1

Your combinatorial argument for possible choices for $(x,y,z)$ works if cleaned up.

In particular you have to decide whether $0$ can be selected for $x$ or $y$.

If so, then you need to adjust your RHS argument to be $3$ from $\{0,1,2,\ldots, n\}$. Otherwise you need $z \le n+1$ so $3$ from $\{1,2,\ldots, n, n+1\}$. Either way, you get $2 {n+1 \choose 3}$ once you allow $x$ and $y$ to be in either order but both less than $z$.

Meanwhile your LHS might be better written as $\sum\limits_{z=3}^{n+1} (z-1)(z-2)$ or as $\sum\limits_{z=2}^{n} z(z-1)$, since your $i$ is in fact $z$ and you are counting how many ways to choose two distinct values smaller than each possible $z$. This then gives your $1\times 2+2\times 3+\cdots +(n-1)\times n$.

Answer 2

It is possible to prove this equation using the well-known mathematical induction as follows.

Step 1: Check whether the equation is valid for $k=2$. Obviously, it is valid.

Step 2: Assuming the equation is valid for $k = (n-1)$, check whether it is also valid for $k = n$. That is, for $k = n$, the left-hand side (LHS) of the equation is

$\qquad LHS=[1\times 2+2\times3+...+(n-2)\times(n-1)]+(n-1)\times n$.

By assuming the equation is valid for $k=(n-1)$, the summation in the square brackets equals $2\binom {n}{3}$. Thus,

$\qquad LHS=2\binom {n}{3}+(n-1)\times n=\frac{n(n-1)(n-2)}{3}+\frac{3n(n-1)}{3}=2\frac{(n+1)n(n-1)}{3\times 2}=2\binom {n+1}{3}$.

This completes the prove.

Answer 3

Your identity equates two ways of counting cyclic triples from $\{0,1,\dots,n\}$, that is, permutations $\sigma$ of $\{0,1,\dots,n\}$ whose cycle decomposition contains a single cycle of length $3$, all other elements being fixed.

Easy way: Choose one of the $\binom{n+1}3$ unordered triples from $\{0,1,\dots,n\}$ and then choose one of the $2$ cyclic permutations of the chosen triple; this can be done in $2\binom{n+1}3$ ways.

Hard way: If the largest number moved by $\sigma$ is $k$, then there are $k(k-1)$ possible choices for $\sigma$, as there are $k$ choices for $\sigma(k)$ and then $k-1$ choices for $\sigma(\sigma(k))$; so the number of possible choices for $\sigma$ is $\sum_{k=2}^nk(k-1)=1\cdot2+2\cdot3+\cdots+(n-1)\cdot n$.