# Finding $\sum\limits_{k=0}^n k^2$ using summation by parts

Sorry to bother you guys again, but I still have some doubts. I do think I'm making some progress, though.

So, again, the formula that I'm using for summation by parts is

$\sum\limits_{k=o}^n f(k)g(k) = g(n)(\sum\limits_{k=0}^n f(k)) - \sum\limits_{k=0}^{n-1} [\Delta g(k) \sum\limits_{i=0}^k f(i)]$

Using this, I'm trying to find $\sum\limits_{k=0}^n k^2$. I think I almost got it, but there are some problems that I still can't get around.

Plugging in $g(k) = k$ and $f(k)=k$, we end up with the following equations:

\begin{align} \sum\limits_{k=0}^n k^2 &= \sum\limits_{k=0}^n kk\\ \sum\limits_{k=0}^n k^2 &= n (\sum\limits_{k=0}^n k) - \sum\limits_{k=0}^{n-1}[\sum\limits_{i=0}^k i]\\ \sum\limits_{k=0}^n k^2 &= n(\frac{n(n+1)}{2}) - \sum\limits_{k=0}^{n-1}[\frac{k(k+1)}{2}]\\ \sum\limits_{k=0}^n k^2 &= \frac{n^3 + n^2}{2} - \frac{\sum\limits_{k=0}^{n-1} k^2+k}{2}\\ 2\sum\limits_{k=0}^n k^2 &= n^3 + n^2 - \sum\limits_{k=0}^{n-1} k^2+k\\ 2\sum\limits_{k=0}^n k^2 &= n^3 + n^2 - \sum\limits_{k=0}^{n-1} k^2+ \sum\limits_{k=0}^{n-1}k \end{align}

Anyway, my problem is, I need the upper indexes of the sums in the right hand side to be $n$, not $n-1$ (I've already checked that, if the indexes are $n$, then I can find the desired result). Is there any trick I'm missing to make those indexes go up by $1$? Or am I missing an obvious step?

• I'm not sure I can help you with this approach, but math.stackexchange.com/questions/1194072/… may interest you.
– Ian
Commented Jul 6, 2015 at 21:07
• You made a simple algebra error in the last step: $$n^3+n^2-\sum_{k=0}^{n-1}(k^2+k) = n^3+n^2-\sum_{k=0}^{n-1}k^2\color{red}{-} \sum_{k=0}^{n-1}k\;.$$ This is one reason I prefer to enclose the summand in parentheses when it has more than one term. Commented Jul 6, 2015 at 21:13
• If you need to add a extra value, just add it! $\sum_{k=0}^{n-1} k^2 = \sum_{k=0}^{n} k^2 - n^2$
– 3d0
Commented Jul 6, 2015 at 21:20
• @BrianM.Scott - Thanks, that did it. Adding $n^2$ to both sides then makes everything works out, right? Commented Jul 6, 2015 at 21:22
• @Nagase: It does indeed. Commented Jul 6, 2015 at 21:26

Other way to make this summation :

$$\int_k^{k+1} x^2\mathrm{d}x=k^2+k+\frac{1}{3}$$

Then use summation from $k=0$ to $n$ and you will find :

$$\frac{(n+1)^3}{3}=\int_0^{n+1} x^2\mathrm{d}x=\sum_{k=0}^n \left(k^2+k+\frac{1}{3}\right)$$

Then after some factorisation we have :

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

I dont want to be polemic but the formula you are using is a bit ugly... I like more this version

$$\sum f\Delta g=fg-\sum \Delta f\ \mathrm E g$$

Where delta is the difference operator, i.e. $\Delta f(n)=f(n+1)-f(n)$, and E is the shift operator, i.e. $\mathrm E f(n)=f(n+1)$.

I like to use too it recursive version when is possible, i.e., when you can represent an "analytic" difference or sum of a function

$$\sum f \Delta g=\sum_{k\ge 0}(-1)^k\ \Delta^k f\ \frac{\mathrm E^k}{\Delta^k}g$$

In your case using last formula I can write

$$f(n)=n \to \Delta f(n)=1 \to \Delta^k f(n)=0,\ k> 1\\ \Delta g(n)=n \to g(n)=\frac{n^\underline 2}{2} \to \frac{\mathrm E^k}{\Delta^k}g(n)=\frac{(n+k)^\underline {k+2}}{(k+2)!}$$

Where $n^\underline k$ is the falling factorial. You have 2 iteration because $\Delta^k f(n)=0,\ k> 1$. Then

$$\sum n^2 \delta n=n\frac{n^\underline 2}{2}-\frac{(n+1)^\underline 3}{6}$$

Taking limits you have

$$\sum_{n=0}^{N}n^2=\sum\nolimits_{0}^{N+1} n^2 \delta n=(N+1)\frac{(N+1)^\underline 2}{2}-\frac{(N+2)^\underline 3}{6}=\frac{1}{3}N^3+\frac{1}{2}N^2+\frac{1}{6}N$$

• I noticed that the first formula you gave is more widely used, and, indeed, most other online resources I searched before asking the question used it. Still, since I'm following that particular book, I decided to stick with it, as I'm beginning to get used to it. He explains other methods of finding sums of powers in the next section anyway (using Bernoulli numbers), so I thought it'd be best not to spend too much time understanding other formulas that I might not even use. Still, thanks for this answer, very elegant derivation! Commented Jul 6, 2015 at 23:24
• Yes, I understand... You are right... When you follow a book you follow a way... Well, I hope my contribution can be useful in some way... Many times seeing the same thing in different versions you can understand more easily the "ugly" ones :p
– user173262
Commented Jul 6, 2015 at 23:26

I would solve it like this: $p_3(n+1)^3 + p_2(n+1)^2 + p_1(n+1) + p_0 - (p_3n^3 + p_2n^2 + p_1n + p_0) = 1n^2$

Then treat the polynomial as a vector space, applying binomial theorem and writing on matrix form solving a linear equation system, we get:

$${\bf p} = \left[\begin{array}{r}p_3\\p_2\\p_1\\p_0\end{array}\right] = \left(\left[\begin{array}{cccc}1&0&0&0\\3&1&0&0\\3&2&1&0\\1&1&1&1\end{array}\right] - \left[\begin{array}{cccc}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{array}\right]\right)^{-1} \left[\begin{array}{c}0\\1\\0\\0\end{array}\right] = \left[\begin{array}{r}1/3\\-1/2\\1/6\\0\end{array}\right]$$

Now I "cheated" ( let octave solve this equation system for me ) so I'm sure it should be -1/2 on the square factor and not 1/2.

EDIT: It turns out that I calculated $n+1$ and not $n$. If I had started with $P(n) - P(n-1) = n^2$ instead of $P(n+1)-P(n) = n^2$ we would have gotten 1/2 for the second degree. To check that this is the case we have the perfect excuse to make another matrix exercise, this time using the binomial expansion of $(n-1)^k$:

$$\left[\begin{array}{rrrr} 1&0&0&0\\ -3&1&0&0\\ 3&-2&1&0\\ -1&1&-1&1 \end{array}\right]^{-1}\left[\begin{array}{r}1/3\\-1/2\\1/6\\0\end{array}\right] = \left[\begin{array}{r}1/3\\1/2\\1/6\\0\end{array}\right]$$

As you probably know: $$\sum_{k=0}^{n-1} k = \frac{(n-1)^2+(n-1)}{2} = \frac{n^2-2n+1+n-1}{2} = \frac{n^2-n}{2}$$ You also know: $$\sum_{k=0}^{n}k^2=n^2+\sum_{k=0}^{n-1}k^2 \rightarrow \sum_{k=0}^{n-1} k^2=\sum_{k=0}^{n} k^2 - n^2$$ So now you can substitute: $$2\sum_{k=0}^n k^2=n^3+n^2-\left(\sum_{k=0}^n k^2-n^2\right)-\frac{n^2-n}{2}$$ Pass this over and you are good to go! $$3\sum_{k=0}^n k^2=n^3+n^2+n^2-\frac{n^2-n}{2}$$ $$\sum_{k=0}^n k^2=\frac{n^3+\frac{3}{2}n^2-\frac{n}{2}}{3}=\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n$$

• But that's false, isn't it? The formula should be $\frac{2n^3 + 3n^2 + n}{6}$, right? Commented Jul 6, 2015 at 21:12
• Correct. I worked from what the OP gave me. Commented Jul 6, 2015 at 21:21
• Sorry about that, I should've made it clearer that I thought there was something wrong with my equations. Commented Jul 6, 2015 at 21:24
• Corrected the math error, and get the right answer. Commented Jul 6, 2015 at 21:24
• And this is where I hit 2000 reputation. :-) Commented Jul 7, 2015 at 1:55