求解演算法導論中的一個數學證明？

01-07

竟然沒有人提這個方法。。。

$(1+x)^n=sum_{k=0}^n inom{n}{k}x^k$

兩邊求導

$n(1+x)^{n-1}=sum_{k=1}^n inom{n}{k}kx^{k-1}$

取 $x=1$ 即得

接下來還有

$n(n-1)2^{n-2}=sum_{k=2}^ninom{n}{k}k(k-1)$

等等等

Concrete Mathematics 書里有很多這類技巧

$sum_{k=0}^{n}{n!/left( k!cdot left( n-k ight)! ight)cdot k } =ncdot sum_{k=0}^{n}{left( n-1 ight)!/left( left( k-1 ight)!cdot left( n-k ight)! ight) } =ncdot left( 1+1 ight) ^{n-1}= ncdot 2^{n-1}$

$k{n choose k} = n {n-1 choose k-1}$ 用這個就行了

我說我的思路吧。

首先想物理意義。假設有n個球，每個球都有獨立的一半概率被選取，一半概率不被選。那總共n個球有k個球被選的概率就是 $C_n^k / 2^n$ 。選取球的數目的期望就是 $frac{1}{2^n}sum_{k=0}^n C_n^k cdot k$ 。從另一個角度想，期望顯然是n/2。得證。

然後把物理意義翻譯成證明。

選球個數的分布的z變換是：

$frac{1}{2^n} sum_{k=0}^n C_n^k z^k = frac{1}{2^n}(z+1)^n$

如果不用多項式展開得到這個等式，也可以把選一個球作為一個事件，其z變換顯然為 $frac{z+1}{2}$ 。n個獨立同分布的變數相加相當於z變換的n次方。這樣也可以得到上面那個等式。

然後個數的期望就是z變換求導再令z=1。最終的證明過程如 @npbool的答案所示。

提一種直觀理解的證法：

等式兩邊的值等同於「有N個盒子，其中一個盒子放兩個球，剩下的盒子最多放一個球」的放置方法數。

左邊的計算方法是：先選好哪些盒子放球，然後再從這些盒子中選擇一個再添加一個球。

右邊的計算方法是：先決定哪個盒子放兩個球，然後在剩下的n-1個盒子中選擇放一個還是不放。

兩種方法得到的結果應該是一樣的。

新人輕拍..

原式等於

$1/2sum_{0}^{n}{(kleft( k,n ight) +(n-k)left(n-k,n ight)) } =n/2sum_{0}^{n}{left( k,n ight) }$

由組合數性質立得

貌似是我們高中的數學證明題啊。樓主學演算法之前學過組合數學嗎？