Proof - Summation

1. 預備公式:
F(k)= n^k-C(n,1)(n-1)^k+C(n,2)(n-2)^k+....+(-1)^(n-1)C(n,n-1)1^k
= { 0 if 0<= k < n
{ n! if n=k
pf.
考慮k個相異物, 分給n個人(1號~n號), 每人均不缺的可能分配數
= 任意分配－(1號缺 or 2號缺 or ... or n號缺)
= n^k - C(n,1)(n-1)^k+C(n,2)(n-2)^k+...+(-1)^(n-1) C(n,n-1)*1^k
= { n! , if n=k (即n相異物排列)
{ 0 , if 0<= k < n (k<n, k物分給n人, 不可能都不缺)
得證
2.
f(x)=Σ[m=0~n] (-1)^m C(n,m) (x-m)^n 展開得 n 次多項式
= A(0)x^n + A(1)x^(n-1)+...+A(k)x^(n-k)+...+A(n-1)x+A(n)
A(k)=Σ[m=0~n] (-1)^m C(n,m) (-m)^k
= (-1)^kΣ[m=0~n] (-1)^m C(n,m) m^k (changes index m~> n-m)
= (-1)^kΣ[m=0~n] (-1)^(n-m) C(n, m) (n-m)^k
= (-1)^(n+k)Σ[m=0~n] (-1)^m C(n,m) (n-m)^k
= (-1)^(n+k) [n^k-C(n,1)(n-1)^k+...-(-1)^n C(n,n-1) 1^k ]
= (-1)^(n+k) F(k)
={ 0 if 0<= k < n
{ n! if k= n
故 f(x)=A(0)x^n+A(1)x^(n-1)+...+A(n-1)x+A(n)
= 0x^n+0x^(n-1)+....+0x + n!
= n!
得證

Express Sum(m=0,n)(-1)^m(nCm)(x-m)^n as B(n)+B(n-1)x+B(n-2)x^2+B(n-3)x^3+…+B(0)x^n …(0)
where B(k) = Sum(m=0,n)(-1)^m(nCm)(nCn-k)(-m)^k

Let f(x) = (1 – x)^n
Let f(k) be the kth derivative of f(x)
f1=n(1-x)^(n-1)(-1)
f2=n(n-1)(1-x)^(n-2)(-1)^2
f3=n(n-1)(n-2)(1-x)^(n-3)(-1)^3
…
fn=n!(-1)^n and f1(1)=f2(1)=f3(1)=fn-1(1)=0; fn(1)=n!(-1)^n

f(x) = (1 – x)^n = Sum(m=0,n)(-1)^m(nCm)x^m (Binomial theorem)

f1=Sum(m=1,n)(-1)^m(nCm)(m^1)x^(m-1)
=Sum(m=0,n)(-1)^m(nCm)(m^1)x^(m-1)… (1)
since when m=0 the term = 0

Proposition P(h) :
For 0<=h<n
Sum(m=0,n)(-1)^m(nCm)[m^(h+1)]x^(m-1) can be expressed as
Sum(i=0,h)A(h,i)(x^i)f(i+1) and that A(h,h)=1…(2)
(where A(h,i) is constant, f(i+1) is the i+1 derivative of f(x)

Obviously P(0) is true from (1)

Now assume P(k) is true where 0<=k<n-1
Sum(m=0,n)(-1)^m(nCm)[m^(k+1)]x^(m-1) = Sum(i=0,k)A(k,i)(x^i)f(i+1)
and A(k,k)=1
Multiply x on both sides,
Sum(m=0,n)(-1)^m(nCm)[m^(k+1)]x^(m) = Sum(i=0,k)A(k,i)(x^i+1)fi+1

Differentiate both sides with respect to x
Sum(m=0,n)(-1)^m(nCm)[m^(k+2)]x^(m-1) =
Sum(i=0,k)A(k,i)(i+1)(x^i)f(i+1) + Sum(i=0,k)A(k,i)(x^i+1)f(i+2)

Changing index on second term, using j=i+1
=Sum(i=0,k)A(k,i)(i+1)(x^i)f(i+1) + Sum(j=1,k+1)A(k,j-1)(x^j)f(j+1)
=Sum(i=0,k)A(k,i)(i+1)(x^i)f(i+1) + Sum(i=1,k+1)A(k,i-1)(x^i)f(i+1)
=Sum(i=0,k+1)A(k+1,i)(x^i)f(i+1)

Where A(k+1,0)=A(k,0)(0+1)=A(k,0)
A(k+1,i)=A(k,i)(i+1)+A(k,i-1) for 0<i<k+1
A(k+1,k+1)=A(k,k)=1

Therefore P(k+1) is true, so P(h) is true for 0<=h<n

2009-06-04 12:07:39 補充：
Since P(h-1) is true, therefore by putting x=1,
Sum(m=0,n)(-1)^m(nCm)[m^(h)] = Sum(i=0,h-1)A(h-1,i)(1^i)f(i+1)(1)
When h

2009-06-04 12:08:07 補充：
When h





2009-06-04 12:08:50 補充：
When h

2009-06-04 12:09:27 補充：
When h=n
Sum(m=0,n)(-1)^m(nCm)(m^n) = Sum(i=0,n-1)A(n-1,i)(1^i)fi+1(1)
The only term that is non-zero is A(n-1,n-1)fn(1)=n!(-1)^n … (4)
Since A(n-1,n-1)=1 and fn(1)=n!(-1)^n

2009-06-04 12:10:02 補充：
When h is less than n, fh(1)=0, so Sum(m=0,n)(-1)^m(nCm)[m^(h)] = 0 …(3)

2009-06-04 12:10:17 補充：
Now Sum(m=0,n)(-1)^m(nCm)(x-m)^n = B(n)+B(n-1)x+B(n-2)x^2+B(n-3)x^3+…+B(0)x^n

And B(n)=Sum(m=0,n)(-1)^m(nCm)(-m)^n=(-1)^n x n!(-1)^n from (4)
=n!

For k





2009-06-04 12:10:41 補充：
For k is less than n,
B(k) = Sum(m=0,n)(-1)^m(nCm)(nCn-k)(-m)^k
=(nCn-k)(-1)^k Sum(m=0,n)(-1)^m(nCm)m^k = 0 from (3)

So Sum(m=0,n)(-1)^m(nCm)(x-m)^n = n!

your question has some problem ,

"mCn" , where m=0,1,2,3,...n

is m must be greater than n , so the only possible value within ( 0,n) is n....