Show that $\sum_{2}^{n} (k^2-k)=\frac{n^3-n}{3}$

Question

I am reading about Gaussian elimination, and the book gives the equation for the number of multiplications/divisions needed to solve a nXn matrix $$\sum_{2}^{n} (k^2-k)$$

The formula I can understand, but what confuses me is when the book says this:

"Through induction you can show that $$\sum_{2}^{n} (k^2-k)=\frac{n^3-n}{3}$$

Edit: Sorry, I was asking the wrong question. I can se that through induction it is true, but how did they come to $\frac{n^3-n}{3}$ without induction in the first place?

Answer 1

For any polynomial $P$ of degree $d+1$, $P(n)-P(n-1)$ is a polynomial of degree $d$. And if $P(n)$ is a sum up to $n$, then $P(n)-P(n-1)$ is the last term of the sum.

There are several ways to discover $P$. For instance by indeterminate coefficients.

With $$\sum_{k=2}^n(k^2-k)=an^3+bn^2+cn+d,$$

you solve

$$n^2-n=a(n^3-(n-1)^3)+b(n^2-(n-1)^2)+c(n-(n-1)).$$

Also see https://www.codeproject.com/Tips/792255/Faulhaber-made-easy, which can be adapted to any polynomial function.

Answer 2

HINT...They have used the formulas $$\sum_{r=1}^n r^2=\frac n6(n+1)(2n+1)$$ and $$\sum_{r=1}^n r=\frac n2(n+1)$$

Answer 3

Okay, your mean is how to calculate $\sum_{k=2}^n k^2$ right?, I assume that you know $\sum_{k=2}^n k$. First Let us : $$ S = \sum_{k=2}^n k^2 \\ P(n,k) = \sum_{i=2}^k i = \frac{(n+k)(n-k+1)}{2} = \frac{n^2 -k^2 + n +k}{2} \\ \text{especially: } P = \sum_{k=2}^n k $$

Now we expand $\sum_{k=2}^n k^2$, $$ \begin{align*} S=\sum_{k=2}^n k^2 &= 2^2 + 3^2 + 4^2 + 5^2 \cdots + n^2 \\ &= 2(2 + 3 +4 \cdots +n) + (3+2\cdot4+3\cdot5+\cdots+(n-2)\cdot n)\\ &=2(2 + 3 +4 \cdots +n) + (3 + 4 + \cdots + n) + \cdots + ((n-1) + n) + n \\ &=2P(n,2) + P(n,3) + P(n,4) + \cdots + P(n,n) \\ &\text{Using }P(n,k) \text{ 's formula, we have:} \\ &= P + \frac{(n-1)n}{2}+\frac{2+ \cdots +n}{2} + \frac{n^2(n-1)}{2} - \frac{S}{2} \\ &= \frac{3}{2}P + \frac{n^3-n}{2} - \frac{S}{2} \end{align*} $$

$\implies$ $$ \frac{3}{2}(S-P) = \frac{n^3-n}{n} \\ S-P = \frac{n^3-n}{3} \\ \sum_{k=2}^n(k^2-k)=S-P=\frac{n^3-n}{3} $$ done.

Answer 4

$$\begin{align*}\sum_{k = 2}^n (k-1)k & =2\times\sum_{k = 2}^n \frac {k!}{(k-2)!\times2!}\\ & = 2\times \sum_{k = 2}^n \binom{k}{2}\\ &= 2\times\binom{n+1}{3} = \frac {n^3-n}{3}\\ \end{align*}$$