Sunday 15 March 2015

summation - How to show that $sum_{k=1}^n k(n+1-k)=binom{n+2}3$?



While thinking about another question I found out that this equality might be useful there:
$$n\cdot 1 + (n-1)\cdot 2 + \dots + 2\cdot (n-1) + 1\cdot n = \frac{n(n+1)(n+2)}6$$
To rewrite it in a more compact way:

$$\sum_{k=1}^n k(n+1-k)=\frac{n(n+1)(n+2)}6.$$



This equality is relatively easy to prove:
$$\sum_{k=1}^n k(n+1-k)=
(n+1)\sum_{k=1}^n k - \sum_{k=1}^n k^2 =
(n+1) \frac{n(n+1)}2 - \frac{n(n+1)(2n+1)}6 = n(n+1) \left(\frac{n+1}2-\frac{2n+1}6\right) = n(n+1)\frac{3(n+1)-(2n+1)}6 =
\frac{n(n+1)(n+2)}6.$$
(We only used the known formulas for the
sum of the first $n$ squares and the
sum of the first $n$ numbers.)




Are there some other nice proofs of this equality? (Induction, combinatorial arguments, visual proofs, ...)






EDIT: Now I found another question which asks about the same identity: Combinatorial interpretation of a sum identity: $\sum_{k=1}^n(k-1)(n-k)=\binom{n}{3}$ (I have tried to search before posting. But the answers posted here so far gave me some new ideas for good keywords to search which lead me to finding that question.) The questions are, in my opinion, not exact duplicates since the other question asks specifically about combinatorial proofs and my question does not have that restriction. But I agree that this is a very minor distinction. In any case, if you think that one of them should be closed as a duplicate, then you can vote to close. I will refrain from voting to close/reopen on this question. (If one of the two questions is voted to be a duplicate of the other one, they probably cannot be merged, since the summation variables are off by one.)


Answer



Let us choose three numbers from $\{0,1,2,\ldots, n+1\}$, beginning with the middle one, which has to be some $k\in \{1,\ldots,n\}$. We then have $k$ choices for the smallest and $n+1-k$ choices for the largest of the three. It follows that
$${n+2\choose3}=\sum_{k=1}^n k(n+1-k)\ .$$


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...