# How to convert sum into formula?

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.

• This is named "getting the closed form" of some expressions. For the case you show here you can apply different methods: algebraic manipulation of partial sums, the use of generating or the use of the rules of the beautiful finite calculus. Aug 22, 2016 at 0:27

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.

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.

• I have to admit, it never occured to me to related sums like this to integration, but of course there are similarities is integration is just sums over teeny intervals. This will save me lots of time in the future as I can never remember any sum but the single powers. Aug 22, 2016 at 0:23
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$$