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

Question

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?

Answer 1

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}$$

Answer 2

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$$

Answer 3

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]$$

Answer 4

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$$