<s>[INST] 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.
 [/INST] 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}$
</s>