Difference Operator and the falling factorial power of k

waddlyeli · #1 $Old$ October 28th, 2009, 09:12 PM

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.

Media_Man · #2 $Old$ October 30th, 2009, 12:27 PM

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}=\frac{(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