Results 1 to 4 of 4

Thread: 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
    9
    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 $\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!$
    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: Aug 26th 2011, 02:35 PM
  2. Problem dealing with Euclidean Algorithm/gcd
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 10th 2011, 07:56 PM
  3. Algebra problem dealing with lengths
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jan 5th 2011, 07:32 PM
  4. World Problem dealing with matrices
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Nov 16th 2008, 05:09 PM
  5. Thermodynamics problem dealing with series
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: Feb 1st 2008, 09:48 AM

Search Tags


/mathhelpforum @mathhelpforum