induction proof with a constant Is there a number $a$, so that 
$$\sum_{k=1}^n (k^2-k) = a(n^3-n)$$
is valid for all integers $n\ge1$? Prove your statement. 
So I know that for $n=2, a=1/3,$ for $n=3, a=1/4,$ for $n=4, a=1/5$ etc. 
I can put $n=2$ for my base case, but how do I move on to my assumption when the value for the constant changes for each number?
 A: $$\sum_{k=1}^n(k^2 - k) = \sum_{k=1}^n k^2 - \sum_{k=1}^nk$$
$$= \frac{1}{6}n(n+1)(2n+1) - \frac{1}{2}n(n+1)$$
(you can prove the formulas above using induction)
Now, you can simplify and see whether things work out or not.
A: Hint $ $ Writing the equation as $\,S(n) = g(n)\,$ and taking the first difference of both sides
$$\begin{align}  \overbrace{n^2\!-\!n}^{\large S(n)\ -\ S(n-1)}\!\!\!\!\!\! &=\ \overbrace{a((n\!-\!1)n(n\!+\!1) - (n\!-\!2)(n\!-\!1)n)}^{\large\quad\ \ g(n)\ -\ g(n-1)}\\ 
&=\ an(n\!-\!1)(n\!+\!1 - n\!-\!2)\\ 
&=\ 3a(n^2\!-\!n)\end{align}$$
So with $a=1/3$ we have $f(n) := S(n)-g(n)$ satsifies $f(1) = 0,\ f(n\!+\!1) = f(n)\,$ so a trivial induction shows $\,f(n) = f(1) = 0\,$ for all $n$, i.e. $\,S(n) = g(n)\,$ for all $n$.
Remark $ $ The trivial induction essentially shows the uniqueness of the solutions of the recurrence $\,S(1) = 0,\ S(n) = S(n\!-\!1) + n^2-n,\,$ by using that the difference $f$ of any two solutions is constant $\,f(n\!+\!1) = f(n)$ with initial value $0$. This is the way sums $S(n)$ are rigorously defined - as the (necessarily) unique solution of the associated recurrence. So to verify that the RHS is a closed form for the sum it suffices to check  it satisfies the recurrence and has the same initial value.
A: You probably forgot to sum because for $n=3$ you have
$$(1^2-1)+(2^2-2)+(3^2-3)=8$$ for which $a=1/3$ fits and not $a=1/4$. Now what you probably did was that for $n=3$ you thought that $$\sum_{k=1}^3(k^2-k)=3^2-3=6$$ And in general that $$\sum_{k=1}^n(k^2-k)=n^2-n$$ but that is wrong.
