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

Printable View

January 17th 2009, 02:50 PM
minivan15

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?
January 17th 2009, 02:53 PM
mr fantastic

Quote:

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
January 18th 2009, 10:54 AM
chiph588@

Check this out too.

http://www.mathhelpforum.com/math-he...116-post7.html
January 19th 2009, 06:56 AM
PaulRS

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