How to deduce that $1\cdot 1 + 2\cdot 1 + 2\cdot 2 + 3\cdot 1+3\cdot 2+3\cdot 3 +...+(n\cdot n) = n(n+1)(n+2)(3n+1)/24$

Question

I know how to reason $$1\cdot2 + 2\cdot3 + 3\cdot4 + n(n-1) = \frac{1}{3}n(n-1)(n+1)$$

However, I'm stuck on proving $$1\cdot1 + (2\cdot1 + 2\cdot2) + (3\cdot1+3\cdot2+3\cdot3) + \cdots +(n\cdot 1+...+n\cdot n) = \frac{1}{24}n(n+1)(n+2)(3n+1).$$ Could somebody shed some light on me?

Answer 1

You can do as the following :$$\begin{align}\sum_{k=1}^{n}k(1+2+\cdots+k)&=\sum_{k=1}^{n}k\cdot\frac{k(k+1)}{2}\\&=\frac 12\sum_{k=1}^{n}k^3+\frac 12\sum_{k=1}^{n}k^2\\&=\frac 12\left(\frac{n(n+1)}{2}\right)^2+\frac 12\cdot\frac{n(n+1)(2n+1)}{6}.\end{align}$$

Answer 2

Base case:

Prove true for n=1

$ 1 * 1 = \frac{1(1 + 1)(1 + 2)(3(1) + 1)}{24} $

Inductive step:

Assume for n = k, prove for n = k+1. If we let the property be equal to P(n)

$ P(k+1) = P(k) + ((k+1) * 1 + ... +(k+1)*(k+1)) $

$ P(k+1) = \frac{k(k + 1)(k + 2)(3k + 1)}{24} + ((k+1) * 1 + ... +(k+1)*(k+1)) $

From here you should be able to do the rest, ask if you have any more issues

Answer 3

The combinatorial identity: $$ \sum_{k=0}^{K}\binom{n+k}{n}=\binom{n+K+1}{n+1}\tag{1}$$ can be easily proved by induction. It gives: $$\sum_{j=1}^{n-1}j(j+1) = 2\sum_{j=1}^{n-1}\binom{j+1}{2} = 2\binom{n+1}{3} = \frac{(n+1)n(n-1)}{2}\tag{2}$$ as well as: $$\begin{eqnarray*} \sum_{k=1}^{n}k(1+2+\ldots+k) &=& 2\sum_{k=1}^{n}k\binom{k+1}{2}=2\sum_{k=1}^{n}\binom{k+1}{2}+6\sum_{k=1}^{n}\binom{k+1}{3}\\&=&2\binom{n+2}{3}+6\binom{n+2}{4}.\tag{3}\end{eqnarray*}$$

Answer 4

A similar but slightly different variation of Jack's proof above.

$$\begin{align} &1\cdot (1)\\ +&2\cdot(1+2)\\ +&3\cdot(1+2+3)\\ +&4\cdot(1+2+3+4)\\ +&\vdots\qquad\vdots \; \quad\ddots\quad \ddots\\ +&n\cdot(1+2+3+\cdots+n)\\ &=\sum_{i=1}^ni\sum_{j=1}^i j=\sum_{i=1}^ni\sum_{j=1}^i {j\choose 1}\\ &=\sum_{i=1}^ni{i+1\choose 2}\\ &=\sum_{i=1}^n\left[(i+2){i+1\choose 2}-2{i+1\choose 2}\right]\\ &=\sum_{i=1}^n\left[3{i+2\choose 3}-2{i+1\choose 2}\right]\\ &=3{n+3\choose 4}-2{n+2\choose 3}\\ &={n+2\choose 3}\left[3\left(\frac{n+3}4\right)-2\right] \qquad\qquad\text{using }{n+3\choose 4}=\frac{n+3}4{n+2\choose 3}\\ &=\frac{(n+2)(n+1)n}{1\cdot 2\cdot 3}\cdot \left[ \frac{3n+1}4\right]\\ &=\frac1{24}n(n+1)(n+2)(3n+1)\qquad\blacksquare \end{align}$$

---

NB - the above makes use of the identity $$\sum_{i=1}^n{i+m\choose m+1}={n+1+m\choose m+2}$$