Return to Answer

1 [made Community Wiki]

This is profoundly less interesting to me than the other two answers already posted, but I think when I was in high school it would have been otherwise. Especially after having seen a bit of calculus.

I recall being amazed that there were formulas --- polynomial formulas! --- for sums like $$s(n) := \sum_{i=1}^n i^k.$$ The first values, $k=0,1$ made sense. For $k=2$, things seemed a bit lucky, and for higher $k$ miraculous indeed. Here's the proof/formula I have in mind.

First, define $\Delta f(x) := f(x+1)-f(x)$ and the falling factorial $x^{\underline 0} := 1, x^{\underline n} := (x-n+1) x^{\underline{n-1}}$. Then $\Delta x^{\underline n} = n x^{\underline{n-1}}$ (for $n\geq 1$). Next, prove that if $\Delta^{k+1} f(x) = 0$ and $\Delta^{k+1} g(x) =0$, then $f(x)-g(x)= c$, and from this get that if $\Delta^{k+1} f(x)=0$, then $f(x)$ is a degree $k$ polynomial. Finally, we can get the formula by using only $s(0),s(1),s(2),\dots,s(k),s(k+1)$ and Lagrange Interpolation: $$s(n) = \sum_{i=0}^{k+1} s(i) \frac{n(n-1)(n-2)\cdots (n-k-1)}{n-i} \cdot \frac{i-i}{i(i-1)(i-2)\cdots (i-k-1)}$$ with the need to cancel before multiplying.

That's ugly enough that I hesitate to press the "Post Your Answer" button, but it has so very many ingredients that would have rocked my world in high school. And the final formula is easy enough to remember.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 14, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.965505063533783, "perplexity_flag": "middle"}