Results 1 to 2 of 2

Math Help - Difference Operator and the falling factorial power of k

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    4

    Difference Operator and the falling factorial power of k

    I have been able to show by algebraic manipulations that the when one applies the difference operator to "x to the n falling" one finds equality with n times x to the (n-1) falling.

    I know that I have to use this now, but no matter how I try to manipulate the following expression, I can't get the result.

    Prove that the sum from k=0 to (m-1) of k to the n falling is equal to m to the (n+1) falling all divided by (n+1)

    I've realized that values where n is greater than or equal to m results in a sum of zero, and when n < m, the first n terms of the sum are zero. However, I can't seem to find where to best use the first statement or where I should be focusing my attention.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Induction

    So far, all of your observations are correct. Note to self: learn latex

    To start, here are a few lemmas you will need, some of which you have already observed, others can be easily verified from the definition.

    Def: (k)_n=x(x-1)(x-2)...(x-(n-1))
    Lemma 1: (k)_n=0 if k<n
    Lemma 2: (n)_n=n!
    Lemma 3: (m)_{n+1}=(m-n)(m)_n
    Lemma 4: (m+1)(m)_n=(m+1)_{n+1}

    By lemma 1, \sum_{k=0}^{m-1}(k)_n=\sum_{k=n}^{m-1}(k)_n, and therefore m\geq n+1

    Base case: Let m=n+1. Then the LHS is \sum_{k=0}^{m-1}(k)_n=\sum_{k=n}^{m-1}(k)_n=\sum_n^n(k)_n=(n)_n=n!.

    The RHS is \frac{(m)_{n+1}}{n+1}=\frac{(n+1)_{n+1}}{n+1}=\fra  c{(n+1)!}{n+1}=n!. So LHS=RHS for our base case.

    Inductive assumption: Suppose \sum_{k=0}^{m-1}(k)_n=\frac{(m)_{n+1}}{n+1} for some m\geq n+1

    Inductive leap: We want to show that \sum_{k=0}^m(k)_n=\frac{(m+1)_{n+1}}{n+1}...

    \sum_{k=0}^m (k)_n= (m)_n+\sum_{k=0}^{m-1}(k)_n= (m)_n+\frac{(m)_{n+1}}{n+1}= (inductive assumption)
    \frac{(n+1)(m)_n+(m)_{n+1}}{n+1}= \frac{(n+1)(m)_n+(m-n)(m)_n}{n+1}= (lemma 3)
    \frac{(m+1)(m)_n}{n+1}= \frac{(m+1)_n}{n+1} (lemma 4)

    QED
    Last edited by Media_Man; October 30th 2009 at 11:43 AM. Reason: cleaning up latex
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Even power of cosine and double factorial
    Posted in the Peer Math Review Forum
    Replies: 3
    Last Post: March 17th 2011, 10:26 PM
  2. Difference Quotient, fifth power
    Posted in the Pre-Calculus Forum
    Replies: 9
    Last Post: December 5th 2009, 05:38 PM
  3. Power Series w/ factorial
    Posted in the Calculus Forum
    Replies: 7
    Last Post: April 8th 2009, 09:45 PM
  4. Need help on difference operator
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: September 2nd 2008, 12:03 AM
  5. Falling object
    Posted in the Math Topics Forum
    Replies: 6
    Last Post: July 12th 2007, 12:52 PM

Search Tags


/mathhelpforum @mathhelpforum