Results 1 to 2 of 2

Thread: 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: $\displaystyle (k)_n=x(x-1)(x-2)...(x-(n-1))$
    Lemma 1: $\displaystyle (k)_n=0$ if $\displaystyle k<n$
    Lemma 2: $\displaystyle (n)_n=n!$
    Lemma 3: $\displaystyle (m)_{n+1}=(m-n)(m)_n$
    Lemma 4: $\displaystyle (m+1)(m)_n=(m+1)_{n+1}$

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

    Base case: Let $\displaystyle m=n+1$. Then the LHS is $\displaystyle \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 $\displaystyle \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 $\displaystyle \sum_{k=0}^{m-1}(k)_n=\frac{(m)_{n+1}}{n+1}$ for some $\displaystyle m\geq n+1$

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

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

    QED
    Last edited by Media_Man; Oct 30th 2009 at 10: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: Mar 17th 2011, 09:26 PM
  2. Difference Quotient, fifth power
    Posted in the Pre-Calculus Forum
    Replies: 9
    Last Post: Dec 5th 2009, 04:38 PM
  3. Power Series w/ factorial
    Posted in the Calculus Forum
    Replies: 7
    Last Post: Apr 8th 2009, 08:45 PM
  4. Need help on difference operator
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: Sep 1st 2008, 11:03 PM
  5. Falling object
    Posted in the Math Topics Forum
    Replies: 6
    Last Post: Jul 12th 2007, 11:52 AM

Search Tags


/mathhelpforum @mathhelpforum