The order of sum of powers? 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

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$.
