Results 1 to 4 of 4

Math Help - problem dealing with 1^k + 2^k + ... +n^k

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    55

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by minivan15 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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{<br />
\left\{ {\begin{array}{*{20}c}<br />
   m  \\<br />
   n  \\<br /> <br />
 \end{array} } \right\}<br />
} where <br />
\left\{ {\begin{array}{*{20}c}<br />
   m  \\<br />
   n  \\<br /> <br />
 \end{array} } \right\}<br />
is the stirling number of the second kind)

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

    Let <br />
A<br />
and <br />
B<br />
be sets such that <br />
\left| A \right| = m \wedge \left| B \right| = n<br />
. 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: <br />
\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}} <br />

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

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

    And that shows it's a polynomial of n.

    In fact from the formula we find that <br />
\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} }<br />
since s\left( {m,m} \right)=m!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A problem dealing with Vectors
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: August 26th 2011, 02:35 PM
  2. Problem dealing with Euclidean Algorithm/gcd
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 10th 2011, 07:56 PM
  3. Algebra problem dealing with lengths
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 5th 2011, 07:32 PM
  4. World Problem dealing with matrices
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 16th 2008, 05:09 PM
  5. Thermodynamics problem dealing with series
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: February 1st 2008, 09:48 AM

Search Tags


/mathhelpforum @mathhelpforum