Find closed formula without using induction for $\sum_{k=0}^n k^3$

Question

I'm studying for my exam in discrete mathematics and found the following problem on last years exam:

Find a closed formula without using induction for $\sum_{k=0}^n k^3$.

I tried it by finding the Generating Function first:

$F(x) = F_0 + \sum_{k=1}^nF_nx^n = \sum_{k=1}^n (F_{n-1}+n^3)x^n = \sum_{k=1}^n F_{n-1}x^n + n^3x^n = \sum_{k=0}^n F_n x^{n+1} + \sum_{k=1}^n n^3x^n = xF(x) + \sum_{k=1}^nn^3x^n$

The problem seems to be, that I lack an actual recursive definition of $\sum_{k=0}^n k^3$ which is, as far as I know, needed to find a generating function. Above, I pretty much used, that $X_n = X_{n-1}+n^3$, but obviously, that`s not enough. Because a recursive definition was always given in our lectures, I don't now other possibilities to solve this, except for finding the Generating Function with help of recursive definitions.

Answer 1

If you'll grant me that $f(n)=\sum_{k=0}^n k^3=an^4+bn^3+cn^2+dn+e,$

then we have this system to solve:

$$ f(0)=0=e\\ f(1)=1=a+b+c+d+e\\ f(2)=9=16a+8b+4c+2d+e\\ f(3)=36=81a+27b+9c+3d+e \\ f(4)=100=256a+64b+16c+4d+e. $$

From this it follows that $e=0$ and $$9-2\times1=7=14a+6b+2c\\ 36-3\times1=33=78a+24b+6c\\ 100-4\times1=96=252a+60b+12c$$

Now can you solve that $a=\dfrac14, b=\dfrac12, c=\dfrac14,$ and $d=0$?

Answer 2

With a telescoping sum: note that $$(k+1)^4-k^4= 4k^3+6k^2+4k+1.$$ Write this equation for $k=1, 2,\dots, n$ and add them. You'll need to know the sums $1+2+\dots +n$ and $1^2+2^2+\dots +n^2$, which are standard.

Answer 3

Let $S_n^{(r)}=\sum_{k=1}^n k^r$. Note that $$(k+1)^4-k^4=4k^3+6k^2+4k+1$$ and after summing for $k=1,\dots,n$, (the sum on the left is telescopic) we get $$(n+1)^4-1=4 S_n^{(3)}+6S_n^{(2)}+4S_n^{(1)}+n.$$ In a similar way, $$(k+1)^3-k^3=3k^2+3k+1\implies (n+1)^3-1=3S_n^{(2)}+3S_n^{(1)}+n$$ and $$(k+1)^2-k^2=2k+1\implies (n+1)^2-1=2S_n^{(1)}+n.$$ Now starting from the last one and going back we can obtain $S_n^{(1)}$, $S_n^{(2)}$, and finally $S_n^{(3)}$.

Answer 4

There are several methods. There's the linear algebra method of finding difference formulas for $k^m$, treating a difference formula for a particular $m$ as a vector, then finding $\sum k^m$ in terms of those vectors. For instance, for $m=1$, we have $k^m-(k-1)^m = 1$. For $m=2$, we have $k^m-(k-1)^m = 2k-1$. If we call those $v_1$ and $v_2$ respectively, we have $k= \frac {v_2+v_1}2$. Thus, to find $\sum k$, we can take $\sum \frac {v_2+v_1}2$. Since $v_2$ is, by definition, the difference formula for $k^m$, $\sum v_2$ is just $n^2$. That is, $\sum_{k=0}^n v_2 = n^2$. Similarly $\sum v_1 = n$. So $\sum k = \frac {n^2+n}2$. A similar, albeit more tedious, method works for finding $\sum k^3$: find $c_m$ such that $k^3=\sum_{m=1}^4c_mv_m$, and $\sum k^3$ will be $\sum_{m=1}^4c_m n^m$

Answer 5

$$\sum_{k=0}^0 k^3=0, \\\sum_{k=0}^1 k^3=1, \\\sum_{k=0}^2 k^3=9, \\\sum_{k=0}^3 k^3=36, \\\sum_{k=0}^4 k^3=100. $$

The requested formula must be a quartic polynomial, because the difference $P(n)-P(n-1)=n^3$ is a cubic polynomial. This polynomial is uniquely determined as the Lagrangian interpolation polynomial by the five above points.

https://www.wolframalpha.com/input/?i=interpolate+%7B%7B0,+0%7D,+%7B1,1%7D,+%7B2,9%7D,+%7B3,36%7D,%7B4,100%7D%7D

Answer 6

To use a generating function to solve this, it helps to know that the ordinary generating function for the sequence $\{n^m\}_{n=0}^\infty$ is $\left(x\frac d{dx}\right)^m\frac1{1-x}$: differentiation multiplies the coefficient of $x^n$ by $n$ and shifts the sequence down, and multiplying by $x$ shifts back up and sets the constant term to $0$, so the net effect is to multiply the $x^n$ term by $n$.

Following the recipe for finding an ordinary generation function, we start with the recurrence $$a_n = a_{n-1}+n^3, n\gt0, a_0=0.$$ Multiply both sides by $x^n$ and sum over valid values of $n$: $$\sum_{n=1}^\infty a_n x^n = \sum_{n=1}^\infty a_{n-1}x^n + \sum_{n=1}^\infty n^3x^n \\ \sum_{n=0}^\infty a_n x^n = x\sum_{n=0}^\infty a_nx^n + \sum_{n=0}^\infty n^3x^n \\ g(x) = x g(x) + \left(x \frac d{dx}\right)^3 \frac1{1-x} \\ g(x) = {x+4x^2+x^3 \over (1-x)^5}.$$

You could’ve instead arrived at this directly with an operator-based approach. As explained above, the “multiply by $n$” operator is $x\frac d{dx}$, while if $f(x)$ is the o.g.f. for a sequence, then $f(x)/(1-x)$ is the o.g.f. for the sequence of its partial sums. Starting from the o.g.f. for the sequence of all $1$s, $1/(1-x)$, the o.g.f. for the sequence of sums of the first $n$ cubes is therefore $$g(x) = \frac1{1-x}\left(x\frac d{dx}\right)^3\frac1{1-x}.$$

I’ll leave extracting the coefficient of $x^n$ from this to you.