I'm curious as to how Wolfram|Alpha manages to derive a direct formula for summations of powers, such as the classic $\sum\limits_{k=0}^n k^2$, or more difficult ones such as $\sum\limits_{k=10}^{n} k^{50}$ (for which it gives this monstrous equation).
There seems to be some kind of pattern there but I haven't been able to figure out what it is.
I've seen proofs and derivations for sums of $k^2$ and $k^3$ but not for the larger ones. Is there a general formula for $\displaystyle\sum\limits_{k=m}^n k^h$ (with $m$, $n$ and $h$ all natural)?
I've come across a formula based on the differences between each consecutive element in a series recursively until you get a series that's all zeroes (not sure how to better explain that). For example, for $k^3$ it would go as follows:
- $a_k=k^3 \rightarrow a_0=0, a_1=1, a_2=8, a_3=27, a_4=64, a_5=125, ...$
- $b_k=a_{k+1}-a_k \rightarrow b_0=1, b_1=7, b_2=19, b_3=37, b_4=61, ...$
- $c_k=b_{k+1}-b_k \rightarrow c_0=6, c_1=12, c_2=18, c_3=24, ...$
- $d_k=c_{k+1}-c_k \rightarrow d_0=6, d_1=6, d_2=6, ...$
- $e_k=d_{k+1}-d_k \rightarrow e_0=0, e_1=0, ...$
A direct formula for the sum could then be constructed by taking the first term of the $m$th series and multiplying it by $\binom{n+1}{m}$ (and doing this for all of them), thus leading to:
$\displaystyle\sum\limits_{k=0}^{n-1} k^3=0\binom{n}{2}+6\binom{n}{3}+6\binom{n}{4}$
Sadly, I've never been able to find a proof for this "trick", but since after extensive derivation/simplification it will eventually lead to formulas such as $\frac{n(n+1)(2n+1)}{6}$ I figured perhaps Wolfram|Alpha would be using something similar to this?
Thanks in advance!
I am no expert and I do not know for sure how Wolfram|Alpha derive formulas. But as the comments have pointed out, the "trick" you have shown is called Faulhaber's Formula.
Wolfram|Alpha may or may not use this formula, but my guess is that it analyses finite differences and uses the properties of finite differences to derive a formula for any input.