# How to reach $\dfrac{(n-1)n(2n-1)}{6n^3}$ [duplicate]

I am trying to refresh my Maths after a lot of years without studying them, and I am finding a lot of difficulties (which is actually nice). So, my question:

I don't understand the next equality. How to reach $\frac{(n-1)n(2n-1)}{6n^3}$ from $$\frac{1^2+ 2^2+...+ (n-1)^2}{n^3}$$?

Thank you very much (and sorry if I make mistakes; my English is also rusty :))

• See e.g. this question. – Clement C. Jul 8 '15 at 6:43
• Haros, the answer will be different depending on whether 1) you would accept a proof by induction of the formula (which can only work if the formula is already known, or has at least been guessed); or 2) you would like a proof that finds the formula without initially presuming that it has been guessed. – Keith Jul 8 '15 at 6:55
• For what I am seeing, the question is more difficult than I though! What I am searching for is 1). Although I have not get the answer to my question yet, @ClementC. has given me good clues posting a link to another question. I will try to find an answer for myself from there. Thank you very much! – haros Jul 8 '15 at 7:01
• I believe you meant what I edited since your original is not correct. I'll give you two answers that allow you to derive the formula without knowing it in advance. – user21820 Jul 8 '15 at 7:08
• For alternatives to induction, this question has an answer that provides a combinatorial proof that $1^2+\cdots+(n-1)^2=\frac16(n-1)n(2n-1)$. And this question has a link in it to a geometric proof. – alex.jordan Jul 8 '15 at 7:10

Here is a possible approach.

You need to compute the sum of squares

$$S(n)=\sum_{k=0}^{n-1}k^2.$$

The difference $S(n+1)-S(n)$ is just the general term, $n^2$, which is a polynomial of the second degree in $n$. For this reason, $S(n)$ must be a polynomial of the third degree in $n$.

To compute it, you can perform Lagrangian interpolation on four points, such as $(1,0),(2,1),(3,1+4)$ and $(4,1+4+9)$.

$$S(n)=1\frac{(n-1)(n-3)(n-4)}{(2-1)(2-3)(2-4)}+5\frac{(n-1)(n-2)(n-4)}{(3-1)(3-2)(3-4)}+14\frac{(n-1)(n-2)(n-3)}{(4-1)(4-2)(4-3)}\\ =\frac{n-1}6\left(3(n^2-7n+12)-15(n^2-6n+8)+14(n^3-5n+6)\right)\\ =\frac{n-1}6(2n^2-n).$$

• Wow! I've never seen this approach before. This answer was worth the duplicate question! – user139000 Jul 8 '15 at 7:16
• Thank you very much for your answer!! That was great and helpful!! – haros Jul 8 '15 at 7:25
• I agree with your claim that $S(n)$ must be a third-degree polynomial, however it is not clear to me if you are saying that this is obvious, or if you're referring to a particular theorem to this effect. – Keith Jul 8 '15 at 7:27
• Yep, Lagrangian interpolation is a good friend. Anyway the computation is rather "heavy" (see my comment to the answer of user21820). You can ease it by using the point $(0,0)$ instead of $(4,14)$ - this requires some "faith" to extrapolate the sum to "$-1$" terms. Neville's scheme can also help a little. – Yves Daoust Jul 8 '15 at 7:27
• @Keith: My answer gives an easy way to see why the sum of $p$-powers should be a degree-$(p+1)$ polynomial, which is equivalent to Yves's comment that the indefinite summation of a degree-$k$ polynomial is a degree-$(k+1)$ polynomial. – user21820 Jul 8 '15 at 7:30

Method 1 $\def\zz{\mathbb{Z}}$

$k^3 - (k-1)^3 = 3k^2 - 3k + 1$ for any $k \in \zz$.

Thus $\sum_{k=1}^n ( k^3 - (k-1)^3 ) = \sum_{k=1}^n ( 3k^2 - 3k + 1)$.

Thus $n^3 - 0^3 = 3 \sum_{k=1}^n k^2 - 3 \sum_{k=1}^n k + \sum_{k=1}^n 1$.

Thus $\sum_{k=1}^n k^2 = \frac{1}{3} \left( n^3 + 3 \sum_{k=1}^n k - \sum_{k=1}^n 1 \right)$.

Notes

This method allows computing $\sum_{k=1}^n k^p$ for any natural number $p$, using all the results for smaller $p$. However it is rather inefficient to do by hand for large $p$.

• On the opposite, I guess this is the most efficient approach to compute the summation formulas. It amounts to solving a triangular system of equations where the coefficients are as subset of Pascal's triangle. See codeproject.com/Tips/792255/Faulhaber-made-easy – Yves Daoust Jul 8 '15 at 7:17
• @YvesDaoust: I'm not sure what you mean by "most efficient" since my second answer that I'm writing is even more efficient, and yet far more general than this method. – user21820 Jul 8 '15 at 7:28
• In the sense of computing the cofficients by hand. – Yves Daoust Jul 8 '15 at 7:50
• @YvesDaoust: Did you see my other method? Why on earth would anyone downvote it since it is superior to this one? – user21820 Jul 8 '15 at 7:50
• Can you make it simpler than the resolution of a triangular system with binomial coefficients ? – Yves Daoust Jul 8 '15 at 7:56

Method 2 $\def\nn{\mathbb{N}}$ $\def\zz{\mathbb{Z}}$ $n^2$ is a degree-$2$ polynomial on $n$, so we write down the sequence $(n^2)_{n\in\nn}$ and find the differences between consecutive terms, which give rise to another sequence. Repeating this $3$ times will produce a sequence of only zeros because $3 > 2$, as we shall prove later.

0,1,4,9,...
1,3,5,...
2,2,...
0,...


Then we look at the $0$-th term in each sequence and just multiply each with the corresponding binomial coefficient to get:

$n^2 = 0 \binom{n}{0} + 1 \binom{n}{1} + 2 \binom{n}{2}$.

Again, why this is true will be proven later.

Now if we want the sum of the first $(n-1)$ squares, we just shift the coefficients to the right as follows:

$\sum_{k=0}^{n-1} = 0 \binom{n}{1} + 1 \binom{n}{2} + 2 \binom{n}{3} = \frac{1}{6}(n-1)n(2n-1)$.

Such a wonderful property of binomial coefficients is not accidental, as we shall see below.

Proof

Define the forward difference operator:

$D = ( \text{function$f$on$\zz$} \mapsto ( \text{int$n$} \mapsto f(n+1) - f(n) ) )$

Namely for any function $f$ on $\zz$ and $n \in \zz$, $D(f)(n) = f(n+1) - f(n)$.

If you think of the functions as sequences (infinite in both directions), then taking the forward difference means replacing each term with the value of the next term minus itself. For example the following shows what happens when you repeatedly take the forward difference of the sequence of cubes:

...,-27,-8,-1, 0, 1, 8,27,...
..., 19, 7, 1, 1, 7,19,37,...
...,-12,-6, 0, 6,12,18,24,...
...,  6, 6, 6, 6, 6, 6, 6,...
...,  0, 0, 0, 0, 0, 0, 0,...
...,  0, 0, 0, 0, 0, 0, 0,...


Then we have:

$D\left( \text{int$n$} \mapsto \binom{n}{k+1} \right) = \left( \text{int$n$} \mapsto \binom{n}{k} \right)$ for any $k \in \zz$.

This is to be expected because it follows directly from Pascal's triangle, especially if we define $\binom{n}{k}$ using the triangle.

This means that if we have any function $f$ on $\zz$ such that $f(n) = \sum_{k=0}^\infty a_k \binom{n}{k}$ for any $n \in \zz$, then we get:

$D(f)(n) = \sum_{k=0}^\infty a_{k+1} \binom{n}{k}$ for any $n \in \zz$.

From a high-level perspective, this is the discrete version of the Taylor series, and indeed for such a function we easily see that $f(n) = \sum_{k=0}^\infty D^k(f)(0) \binom{n}{k}$ for any $n \in \zz$, because $\binom{0}{0} = 1$ while $\binom{0}{k} = 0$ for any $k \in \nn^+$.

This works for any polynomial function $f$ on $\zz$, since $D^k(f)$ is the zero function once $k$ is larger than the degree of $f$, so we can use it to immediately find the series for $(\text{int n} \mapsto n^3)$, and then just take the anti-difference by shifting the coefficients of the series the other way. The undetermined constant that appears will drop out once we perform a definite sum like if we want the sum of the first $m$ cubes.

Notes

This is far more efficient that my other method in a certain sense because the series using binomial coefficients is easy to manipulate and easy to compute. Strangely, it seems that people do not appreciate methods that are better...

Also, for a wide class of non-polynomial functions, we can still compute the indefinite sum without using the series, by using the discrete analogue to integration by parts, here called summation by parts.

To derive it, simply check that $D(f \times g)(n) = f(n+1) g(n+1) - f(n) g(n) = f(n+1) D(g)(n) - D(f)(n) g(n)$ and so we get the product rule:

$D(f \times g) = R(f) \times D(g) + D(f) \times g$

where $R$ is the right-shift operator defined as:

$R = ( \text{function$f$on$\zz$} \mapsto ( \text{int$n$} \mapsto f(n+1) ) )$

Namely for any function $f$ on $\zz$ and $n \in Z$, $R(f)(n) = f(n+1)$.

For convenience we also define the summation operator:

$S = ( \text{function$f$on$\zz$} \mapsto ( \text{int$n$} \mapsto \sum_{k=0}^{n-1} f(k) ) )$

Then we have the important property that $DS(f) = f$ for any function $f$ on $\zz$, analogous to the fundamental theorem of calculus.

Now by substituting $f$ with $S(f)$ into the product rule and taking summation on both sides we get summation by parts:

$S( f \times g ) = S(f) \times g - S( R(S(f)) \times D(g) ) + c$ for some constant function $c$ on $\zz$.

Using this we can easily compute things like $\sum_{k=1}^n 3^k k^3$ by applying it three times, each time reducing the degree of the polynomial part.

• Despite the meaningless downvote, I'm going to add further detail for the reader who is actually interested in learning this powerful technique that has deep ties with recurrence relations and differential equations. – user21820 Jul 8 '15 at 8:13
• I would phrase this argument as follows. For $k = 0, 1, 2, \dots$, write $f_k(x) = \binom{x}{k}$, a polynomial of degree $k$. Look at the space $V_{r+1}$ of polynomials of degree $\leq r + 1$. Then the operator $D$ from your answer takes a particularly simple form when expressed in the basis $f_0, f_1, \dots, f_{r + 1}$. Thus the problem to be solved amounts to writing the polynomial $x^r$ in this basis. – Keith Jul 8 '15 at 8:30
• @Keith: That is correct for polynomials, but I chose to express the ideas using operators because if you look at the notes it works even outside that vector space of polynomials that you are referring to. And if you think my answer is useful, do upvote it. – user21820 Jul 8 '15 at 8:34