# Thread: problem dealing with 1^k + 2^k + ... +n^k

1. ## problem dealing with 1^k + 2^k + ... +n^k

assume that 1^k + 2^k + ... +n^k is a polynomial of degree k+1 in n

i.e. 1^k + 2^k +... +n^k = an^(k+1) +bn^k +cn^(k-1) + ...

what can you say about the coefficients of this polynomial? try to determine them as completely as possible

I need help with this! I can see that they will always add up to 1 (take n = 1) and obviously you could create a bunch of equations and solve them for specific n and k, but what else is there?

2. Originally Posted by minivan15
assume that 1^k + 2^k + ... +n^k is a polynomial of degree k+1 in n

i.e. 1^k + 2^k +... +n^k = an^(k+1) +bn^k +cn^(k-1) + ...

what can you say about the coefficients of this polynomial? try to determine them as completely as possible

I need help with this! I can see that they will always add up to 1 (take n = 1) and obviously you could create a bunch of equations and solve them for specific n and k, but what else is there?
Read this: Sums of Consecutive Powers

3. Let $s(m,n)$ be the number of surjective functions from a set of m elements to a set of n elements. ( it's easy to see that $s(m,n)=n!\cdot{
\left\{ {\begin{array}{*{20}c}
m \\
n \\

\end{array} } \right\}
}$
where $
\left\{ {\begin{array}{*{20}c}
m \\
n \\

\end{array} } \right\}
$
is the stirling number of the second kind)

Note that $
n^m = \sum\limits_k {\binom{n}{k}\cdot s\left( {m,k} \right)}
$

Let $
A
$
and $
B
$
be sets such that $
\left| A \right| = m \wedge \left| B \right| = n
$
. The number of functions from A to B is: $n^m$. Now the number of functions $f:A\rightarrow{B}$ with $|f(A)|=k$ is $\binom{n}{k}\cdot s\left( {m,k} \right)$.

Thus: $
\sum_{j=0}^n{j^m} = \sum_{j=0}^n\sum\limits_k {\binom{j}{k}\cdot s\left( {m,k} \right)} =\sum\limits_k {s\left( {m,k} \right)\cdot \sum_{j=0}^n\binom{j}{k}}
$

But we have the following identity(see here ) : $\sum_{j=0}^n\binom{j}{k}=\binom{n+1}{k+1}$

Thus we get: $\boxed{
\sum_{j=0}^n{j^m} =\sum\limits_k {\binom{n+1}{k+1} \cdot s\left( {m,k} \right)}}
$

And that shows it's a polynomial of $n$.

In fact from the formula we find that $
\sum_{j=0}^n{j^m} \sim \binom{n+1}{m+1} \cdot s\left( {m,m} \right)\sim { \tfrac{n^{m+1}}{m+1} }
$
since $s\left( {m,m} \right)=m!$