證明C(n,0)+C(n,1)+...+C(n,n)=2^n

Question

令C(n,m)代表從n個相異物品中取出m個的組合數。證明C(n,0)+C(n,1)+C(n,2)...+C(n,n)=2n但不要用「二項式定理(x+y)n=......，令x=y=1代入」這個方法。

Answer 1

n=1, C(1,0)+C(1,1)=1+1=2=21Let n=k, C(k,0)+C(k,1)+C(k,2)...+C(k,k)=2kthen n=k+1C(k+1,0)+C(k+1,1)+C(k+1,2)...+C(k+1,k+1)=1+C(k+1,1)+C(k+1,2)...+C(k+1,k)+1=C(k,0)+[C(k,0)+C(k,1)]+[C(k,1)+C(k,2)]+...+[C(k,k-1)+C(k,k)]+C(k,k)=2*[C(k,0)+C(k.1)+C(k.2)+...+C(k,k-1)+C(k,k)]=2*2k=2k+1by inductionfor all n , C(n,0)+C(n,1)+C(n,2)...+C(n,n)=2n

Answer 2

C(n,0)代表從n個相異物品中取出0個的組合數
C(n,1)代表從n個相異物品中取出1個的組合數
C(n,0)代表從n個相異物品中取出2個的組合數
...........................................................................
C(n.n)代表從n個相異物品中取出n個的組合數
C(n,0)+C(n,1)+C(n,3)+................................+C(n,n)表示從n個相異物品中取出物品的所有方法,每一種物品有可取與不取兩種情形,種共n個相異物品,故有2*2*2*..................*2,n個2相乘=2^n#

Answer 3

那個是 nCr 吧