I know $\displaystyle\sum_{k=1}^n k^2$ equals $n/6+n^2/2+n^3/3$, but... why?
And I also know that $\displaystyle\sum_{k=1}^n k^3$ equals $n^2/4+n^3/2+n^4/4$, but... is there a pattern so I can easily get $\displaystyle\sum_{k=1}^n k^a$? And could you give me a proof if so?
On
In general, the formula for $$\sum_{k=1}^{n}k^a$$ (for $a\in\mathbb{N}$) will be a polynomial in $n$ of degree $a+1$. This polynomial will thus have $a+2$ coefficients, which you can solve for simultaneously by setting up a system of $a+2$ equations. For the case a=2:
$$\sum_{k=1}^nk^2=an^3+bn^2+cn+d$$
Now compute S, the sum, for 4 values of n: $$n=1\implies S_1=a+b+c+d=1 \\n=2\implies S_2=8a+4b+2c+d=5 \\n=3\implies S_3=27a+9b+3c+d=14 \\n=4\implies S_4=64a+16b+4c+d=30 $$
So the problem is reduced to solving a system of four linear equations in four unknowns. MATLAB gives $$[\frac13, \frac12,\frac16,0]^T$$ as the solution.
In fact, I just noticed that 'd' will always be 0 so you can do this with only 3 (a+1) equations instead of 4 (a+2).
Assuming that we know the expression of $$\sum_{k=1}^n k,\sum_{k=1}^n k^2,\ldots,\sum_{k=1}^n k^{p-1}$$ then since by telescoping $$\sum_{k=1}^n (k+1)^{p+1}-k^{p+1}=(n+1)^{p+1}-1$$ and $$(k+1)^{p+1}-k^{p+1}=\sum_{s=0}^{p}{p+1\choose s}k^s$$ hence we can find $$\sum_{k=1}^n k^{p}=\frac{1}{p+1}\left((n+1)^{p+1}-\sum_{s=0}^{p-1}{p+1\choose s}\sum_{k=1}^nk^s-1\right)$$