Finding formula for sum $S_n = \sum_{i=1}^n i(i-1)$ How do I find the formula for this sum
$S_n = \sum_{i=1}^n i(i-1)$
Wolfram alpha gives me the correct formula which is $ \frac{1}{3} (n-1)n(n+1)$, but I'm interested in how I get to that and how I can approach this kind of problem in general.
 A: We have that
$$
S_n=\sum_{i=1}^n[i(i-1)]=\sum_{i=1}^n[i^2-i]=\sum_{i=1}^ni^2-\sum_{i=1}^ni.
$$
Also,
$$
\sum_{i=1}^ni=\frac{n(1+n)}2
$$
and
$$
\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}6
$$
(see, for example, this question).
Hence,
$$
S_n=\frac{n(n+1)(2n+1)}6-\frac{n(1+n)}2=\frac{n(n+1)(n-1)}3=\frac{n(n^2-1)}{3}.
$$
A: $$\sum_{i=0}^n i(i-1)=2\sum_{i=0}^n\binom i2=2\binom {n+1}3=\frac {(n-1)n(n+1)}3\quad\blacksquare  $$

NB: the above solution makes use of the fact that
$$\sum_{i=0}^n\binom im=\sum_{i=m}^n\binom im=\sum_{i=m}^n\binom {i+1}{m+1}-\binom i{m+1}=\binom {n+1}{m+1}$$
with the summation result arrived at by telescoping and noting that $\binom {m-1}{m+1}=0$.
A: A systematic approach was discovered about 1690 by one of the Bernoulli's. For a sum with n terms, where each term is the same polynomial in the index variable,  assume that the sum will be a polynomial in n, and the order will be one greater.
Then fit coefficients and factor the resultant polynomial to get the formula.  I discovered this in high school on my own; I was inspired by the story of the young Gauss as given by E.T. Bell in "Men of Mathematics". The geometric methods given above are also neat.
A: If perhaps you forget the summation formulas, or can't derive them for some reason. There is a trick we can do. Notice that:
$$s_{n}-s_{n-1}=n(n-1)=n^2-n$$
This is what we call a recurrence relation. Notice that $s_{n}-s_{n-1}=\frac{s_n-s_{n-1}}{n-(n-1)}$ resembles the definition of the derivative of $s$, and in fact should be somewhat close to the derivative. So we can make an educated guess that if $s_{n}-s_{n-1}$ is a quadratic, then $s_{n}$ is an integral of some quadratic (a $3$rd degree polynomial):
$$s_n=an^3+bn^2+cn+d$$
Now what you can do is find:
$$s_n-s_{n-1}$$
This is:
$$s_n-s_{n-1}=a(3n^2-3n+1)+b(2n-1)+c=n^2-n$$
Now equate coefficients:
$$3a=1$$
$$-3a+2b=-1$$
$$a-b+c=0$$
To get:
$$a=\frac{1}{3}$$
$$b=0$$
$$c=\frac{-1}{3}$$
And with our base case $s_1=1^2-1=0$ we can find that $d=0$. 
In conclusion:
$$s_n=\frac{n^3-n}{3}$$
A: This is much simpler. Let's use the notation $x^{\underline{k}} = x (x - 1) \dotsm (x - k + 1)$ for arbitrary $x$ and $k \in \mathbb{N}_0$.
Prove by induction on $n$ that:
$\begin{align}
   \sum_{0 \le k < n} k^{\underline{m}} = \frac{n^{\underline{m + 1}}}{m + 1}
\end{align}$
Base: For $n = 0$, this is true, the left hand side is an empty sum and the right hand side is zero.
Induction: Asume it is true for $n$, check $n + 1$:
$\begin{align}
   \sum_{0 \le k < n + 1} k^{\underline{m}}
     &= \sum_{0 \le k < n} k^{\underline{m}} + n^{\underline{m}} \\
     &= \frac{n^{\underline{m + 1}}}{m + 1} + n^{\underline{m}} \\
     &= \frac{n^{\underline{m}} \cdot (n - m)
               + n^{\underline{m}} \cdot (m + 1)}
             {m + 1} \\
     &= \frac{n^{\underline{m}} (n + 1)}{m + 1} \\
     &= \frac{(n + 1)^{\underline{m + 1}}}{m + 1}
\end{align}$
For your specific case:
$\begin{align}
  \sum_{1 \le i \le n} i (i - 1)
    &= \sum_{0 \le i < n + 1} i^{\underline{2}} \\
    &= \frac{(n + 1)^{\underline{3}}}{3} \\
    &= \frac{(n + 1) n (n - 1)}{3} \\
    &= \frac{n^3 - n}{3}
\end{align}$
