For example, the sum of n is n(n+1)/2, the dominating term is n square(let say this is order 2). For the sum of n^2, the order is 3. Then for the sum of n^k, is the order k+1?
I been searching Faulhaber's formula and Bernoulli numbers, I'm not sure what is the order of it. It's much more complicated than i think.
Any ideas? Thanks in advance
On
You are correct. Let the function $F_k$ be defined as $$ F_k(n) = \sum_{i = 1}^n i^k $$ and assume that $F_k(n)$ is a polynomial of some degree, say $$ F_k(n) = a_0 + a_1n + \cdots + a_ln^l $$ Then the function $f_k(n) = F(n) - F(n-1) = n^k$ is a polyniomial of order $k$. But that means that we must have $l = k+1$ (and $a_l = a_{k+1} = 1/(k+1)$).
Of course, what's left is to show that $F_k(n)$ is indeed a polynomial for all $k$.
By the definition of Riemann integral, $\frac1n \sum_{k=1}^n (\frac{k}{n})^\alpha \rightarrow \int_0^1 t^\alpha dt=\frac1{\alpha+1}$.
Then $\sum_{k=1}^n k^\alpha \sim \frac{n^{\alpha+1}}{\alpha+1}$