Find closed formula without using induction for $\sum_{k=0}^n k^3$ 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.
 A: 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.
A: 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)}$.
A: 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$?
A: 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.
A: 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$
A: $$\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
