# Difference Operator and the falling factorial power of k

• Oct 28th 2009, 07:12 PM
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.
• Oct 30th 2009, 10:27 AM
Media_Man
Induction
So far, all of your observations are correct. Note to self: learn latex (Wink)

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