Re: [其他] 一題組合級數

看板Math作者Dawsen (好友名單不見了啦...)時間12年前 (2012/04/11 12:20)推噓1(1推 0噓 2→)

留言3則, 1人參與討論串3/3 (看更多)

提供一個不用數歸的証法考慮 S={1,2,..., 2n+1} 的子集合個數共有2^(2n+1)個其中元素個數>=(n+1)的子集共占了一半=2^(2n)個對子集 A ={a_1,a_2,...,a_m} in S, a_1<a_2<...<a_m, |A|>=n+1，按照a_{n+1}分類，設其為n+k+1, (k=0,1,...,n) 可能的排列組合數為 C(n+k,n) * 2^(n-k) ^^^^^^ 1,2,...,n+k 共有n個在A中 ^^^^^^{n+k+2,...,2n+1}的子集個數 n 故2^(2n) = Σ C(n+k,n)2^(n-k) k=0 整理可得所求等式 ※ 引述《realtemper (精彩不亮麗)》之銘言： : 這可以數歸啊～跟一般作法沒什麼不同 : 一樣是在 n=N+1 的求和式裡面，把 n=N 的部份(已知)硬拆出來，剩下再硬算.... : pf: : n (n+k)! n : 假設 Σ ──── = 2 n! 在 n=N 時成立 (當然 n=0,1 時顯然成立) : k=0 k : 2 k! : 則 n = N+1 時 : N+1 (N+1+k)! N+1 (N+k)! : Σ ───── = Σ ──── (N+1+k) : k=0 k k=0 k : 2 k! 2 k! : N (N+k)! N (N+k)! (2N+2)! : = (N+1) Σ ──── + Σ ──── k + ────── : k=0 k k=0 k N+1 : 2 k! 2 k! 2 (N+1)! : ^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^ : (1) (2) (3) : 級數的已知部份級數隨k變動的部份多出來的一項 : N N : (1) = (N+1) 2 N! = 2 (N+1)! (by n=N 成立之假設) : N (N+k)! 1 N-1 (N+1+k)! : (2) = Σ ──── = ─ Σ ───── : k=1 k 2 k=0 k : 2 (k-1)! 2 k! : 1 N+1 (N+1+k)! (2N+1)! (2N+2)! : = ─ [ Σ ───── - ───── - ────── ] : 2 k=0 k N N+1 : 2 k! 2 N! 2 (N+1)! : ^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^ : 此即欲求之級數和,記為 x 把第N與N+1項扣回來 : (因為還不知道 n=N+1 是否成立) : 1 (2N+1)! : = ─ x - ──── : 2 N : 2 N! : 故 : N 1 (2N+1)! (2N+2)! : x = (1) + (2) + (3) = 2 (N+1)! + ─ x - ──── + ────── : 2 N N+1 : 2 N! 2 (N+1)! : 1 N : ─ x = 2 (N+1)! : 2 : N+1 : x = 2 (N+1)! by 數學歸納法 QED -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 18.111.105.50 ※ 編輯: Dawsen 來自: 18.111.105.50 (04/11 12:21)

推

realtemper

04/12 02:30, , 1^F

04/12 02:30, 1^F

→

realtemper

04/12 02:31, , 2^F

04/12 02:31, 2^F

→

realtemper

04/13 18:43, , 3^F

04/13 18:43, 3^F