# 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 $\displaystyle 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 $\displaystyle s(m,n)=n!\cdot{ \left\{ {\begin{array}{*{20}c} m \\ n \\ \end{array} } \right\} }$ where $\displaystyle \left\{ {\begin{array}{*{20}c} m \\ n \\ \end{array} } \right\}$ is the stirling number of the second kind)

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

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

Thus: $\displaystyle \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 ) : $\displaystyle \sum_{j=0}^n\binom{j}{k}=\binom{n+1}{k+1}$

Thus we get: $\displaystyle \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 $\displaystyle n$.

In fact from the formula we find that $\displaystyle \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 $\displaystyle s\left( {m,m} \right)=m!$