4
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Alec Teal Apr 8 '15 at 11:19
  • $\begingroup$ @AlecTeal: You are right. And I now found "induction" tag... Anyway, I leave my answer in hoping that my answer helps 'future readers'. $\endgroup$ – mathlove Apr 8 '15 at 11:26
  • $\begingroup$ @mathlove oh the answer isn't useless! Just there's a nice story about the inuition $\endgroup$ – Alec Teal Apr 9 '15 at 8:19
  • $\begingroup$ 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! $\endgroup$ – Paul Lo Apr 9 '15 at 15:01
3
$\begingroup$

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

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

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

$\endgroup$
  • 1
    $\begingroup$ @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. $\endgroup$ – hypergeometric Apr 9 '15 at 16:16
  • $\begingroup$ Thank you! It turns out to be standing for combination function which I have learned, now I can understand your answer thoroughly :p $\endgroup$ – Paul Lo Apr 9 '15 at 17:32
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.