# 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$

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?

• Try proof by induction ? – Pixel Apr 8 '15 at 11:12
• What's the difference between the first two lines? – George Moore Apr 8 '15 at 11:15
• First two lines are identical, and there also seem to be missing some points in $\;3\cdot 4+\ldots+n(n-1)\;$ ... – Timbuc Apr 8 '15 at 11:17
• I just removed the identical two lines. – Paul Lo Apr 8 '15 at 12:21

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}

• Requires knowledge of sum of $k$ - tell the story about a young [bugger - I don't know it myself] who was given the question by a teacher to add all the numbers from 1 to 100 and did the "arrange the pairs, 1 with 99, 2 with 98 .... " - Gauss maybe? – Alec Teal Apr 8 '15 at 11:19
• @AlecTeal: You are right. And I now found "induction" tag... Anyway, I leave my answer in hoping that my answer helps 'future readers'. – mathlove Apr 8 '15 at 11:26
• @mathlove oh the answer isn't useless! Just there's a nice story about the inuition – Alec Teal Apr 9 '15 at 8:19
• I'm adding these two links for my personal note (as my edit wasn't get approved): math.stackexchange.com/questions/62171/… and math.stackexchange.com/questions/48080/… for calculating sum of powers (2 and 3) of positive integers. Thanks everybody again! – Paul Lo Apr 9 '15 at 15:01

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

• Thank you, I really appreciate your help. – Paul Lo Apr 8 '15 at 12:25

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}$$

• @PaulLo :You're welcome. $\binom nr$ refers to the binomial coefficient or combination function, and is sometimes written as $^nC_r$, and is defined as $$\binom nr=\frac{n!}{r!(n-r)!}=\frac{n(n-1)(n-2)\cdots (n-r+1)}{1\cdot 2\cdots r}$$. More info here en.wikipedia.org/wiki/Combination. – hypergeometric Apr 9 '15 at 16:16
• Thank you! It turns out to be standing for combination function which I have learned, now I can understand your answer thoroughly :p – Paul Lo Apr 9 '15 at 17:32

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*}$$

• Thanks, I really appreciate your help. – Paul Lo Apr 8 '15 at 12:25
• Did you mean ${n+2\choose 3}$ rather than ${n+2\choose 2}$? – hypergeometric Apr 8 '15 at 14:37
• @hypergeometric: yes, sure, now fixed. – Jack D'Aurizio Apr 8 '15 at 14:43