I am reading some combinatorics books. And here author first obtained a sum answer for a problem and then converted it to formula without explaining it. Just writing equality sign. This is that expression: $$2(2\sum_{k=1}^{n-1} k(k-1) + n(n-1)) = 2(\frac{1}{3}(n-1)n(2n-1)-n(n-1)+n(n-1)) = \frac{2}{3}n(n-1)(2n-1)$$
The main question is "How did he get this?". I often face with this problem where I need to convert such sums into formula. And additionally, I'll really appreciate if you show some technics to do this.
$\endgroup$ 13 Answers
$\begingroup$Discrete sums work just like integrals, but you have to replace powers by falling powers: $$ k^{\underline{n}} \equiv k\cdot (k-1) \cdot (k-2) \cdots (k-n+1) $$ with $n$ factors just like $k^n$, but they are falling. Thus for example $k^{\underline{k}} = k!$. When you have a sum of falling powers, the formula is $$ \sum_{k=0}^n k^{\underline{n}} = \frac{1}{n+1} k^{\underline{n+1}} $$ (see that is just like integrating $x^n$).
Using this tecnique, the problem you have becomes easy.
$\endgroup$ 3 $\begingroup$You should be familiar with Faulhaber's formula, not to memorize but to know it exists and where to look it up. Then $$\sum_{k=1}^{n-1}k(k-1)=\sum_{k=1}^{n-1}k^2-k\\=\frac 16(n-1)n(2n-1)-\frac 12(n-1)n$$
$\endgroup$ 1 $\begingroup$The basic formulas used here are
$\sum_{k=1}^n k = \dfrac{n(n+1)}{2} $
and $\sum_{k=1}^n k^2 = \dfrac{n(n+1)(2n+1)}{6} $.
There are similar formulas for higher powers.
$\endgroup$
