【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 + 求导 证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 )

一、组合恒等式 ( 变下项求和 ) 变系数求和 1

组合恒等式 ( 变下项求和 ) 变系数求和 :

∑ k = 0 n k ( n k ) = n 2 n − 1 \sum_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1} k=0∑n​k(kn​)=n2n−1

k k k 随着求和的项不断变化 , 变化范围 0 0 0 ~ n n n ;

1. 证明方法 :

• 二项式定理 : 使用 二项式定理 + 求导 可以证明该组合恒等式 ;
• 组合恒等式代入 : 使用 已知组合恒等式代入 , 消去变系数 ; 即使用之前的 3 3 3 个递推式 , 简单和 , 交错和 , 5 5 5 个组合恒等式 代入 ;

二、组合恒等式 ( 变下项求和 ) 变系数求和 1 证明 ( 二项式定理 + 求导 )

使用二项式定理 + 求导方法证明下面的恒等式 :

∑ k = 0 n k ( n k ) = n 2 n − 1 \sum_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1} k=0∑n​k(kn​)=n2n−1

二项式定理 : ( x + y ) n = ∑ k = 0 n ( n k ) x k y n − k (x + y)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k y^{n-k} (x+y)n=k=0∑n​(kn​)xkyn−k

1. y = 1 y = 1 y=1 时有该情况 : ( x + 1 ) n = ∑ k = 0 n ( n k ) x k (x +1)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k (x+1)n=k=0∑n​(kn​)xk , 上述公式中 , 将常数项 k = 0 k= 0 k=0 的情况单独计算出来 , ( n 0 ) x 0 = 1 \dbinom{n}{0}x^0 = 1 (0n​)x0=1 , 计算过程如下 :

( x + 1 ) n = ∑ k = 0 n ( n k ) x k = ( n 0 ) x 0 + ∑ k = 1 n ( n k ) x k = 1 + ∑ k = 1 n ( n k ) x k (x +1)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k = \dbinom{n}{0}x^0 + \sum\limits_{k=1}^n \dbinom{n}{k}x^k = 1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k (x+1)n=k=0∑n​(kn​)xk=(0n​)x0+k=1∑n​(kn​)xk=1+k=1∑n​(kn​)xk

2. 引入求导 : 要在加和式 ∑ k = 1 n ( n k ) x k \sum\limits_{k=1}^n \dbinom{n}{k}x^k k=1∑n​(kn​)xk 中出现 k k k 变化数 , 需要对 x x x 进行求导 ;

这里直接对 ( x + 1 ) n = 1 + ∑ k = 1 n ( n k ) x k (x +1)^n = 1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k (x+1)n=1+k=1∑n​(kn​)xk 等式两边进行求导 ;

( 1 ) 左边组合式 ( 根据下面的幂函数导数公式 计算 ) : ( x + 1 ) n (x +1)^n (x+1)n 导数为 n ( x + 1 ) n − 1 n(x+1)^{n-1} n(x+1)n−1

( 2 ) 右边组合式 ( 根据下面的 导数运算规则 和 幂函数导数公式 计算 ) : 1 + ∑ k = 1 n ( n k ) x k 1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k 1+k=1∑n​(kn​)xk 导数为 , 1 1 1 的导数 为 0 0 0 , 加上 ∑ k = 1 n ( n k ) x k \sum\limits_{k=1}^n \dbinom{n}{k}x^k k=1∑n​(kn​)xk 的导数 ∑ k = 1 n k ( n k ) x k − 1 \sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1} k=1∑n​k(kn​)xk−1 , 最终结果是 ∑ k = 1 n k ( n k ) x k − 1 \sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1} k=1∑n​k(kn​)xk−1

( 3 ) 左右两边的导数是相等的 :

n ( x + 1 ) n − 1 = ∑ k = 1 n k ( n k ) x k − 1 n(x+1)^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1} n(x+1)n−1=k=1∑n​k(kn​)xk−1

幂函数求导 : ( 很重要 )

• 原函数 : y = x n y = x^n y=xn
• 对应导数 : y ′ = n x n − 1 y' = nx^{n-1} y′=nxn−1\

/ 常数的导数是 0 0 0 ; / 导数四则运算 : ( u ± v ) ′ = u ′ ± v ′ (u \pm v)' = u' \pm v' (u±v)′=u′±v′ / 参考 : 导数 - 百度百科

3. 求导后的结果如下 :

n ( x + 1 ) n − 1 = ∑ k = 1 n k ( n k ) x k − 1 n(x+1)^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1} n(x+1)n−1=k=1∑n​k(kn​)xk−1

假设求导结果中的 x = 1 x = 1 x=1 , 有如下结果 :

n 2 n − 1 = ∑ k = 1 n k ( n k ) n2^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k} n2n−1=k=1∑n​k(kn​)

当 k = 0 k = 0 k=0 时 , 有 k ( n k ) = 0 × ( n 0 ) = 0 k \dbinom{n}{k} = 0 \times \dbinom{n}{0} = 0 k(kn​)=0×(0n​)=0 ,

因此加上 k = 0 k=0 k=0 的情况 , 即 k k k 从 0 0 0 开始累加 , 也不影响上述结果 :

n 2 n − 1 = ∑ k = 0 n k ( n k ) n2^{n-1} = \sum\limits_{k=0}^n k \dbinom{n}{k} n2n−1=k=0∑n​k(kn​)

三、组合恒等式 ( 变下项求和 ) 变系数求和 2

组合恒等式 ( 变下项求和 ) 变系数求和 :

∑ k = 0 n k 2 ( n k ) = n ( n + 1 ) 2 n − 2 \sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2} k=0∑n​k2(kn​)=n(n+1)2n−2

k k k 随着求和的项不断变化 , 变化范围 0 0 0 ~ n n n ;

证明方法 :

• 二项式定理 : 使用 二项式定理 + 求导 可以证明该组合恒等式 ;
• 组合恒等式代入 : 使用 已知组合恒等式代入 , 消去变系数 ; 即使用之前的 3 3 3 个递推式 , 简单和 , 交错和 , 5 5 5 个组合恒等式 代入 ;

四、组合恒等式 ( 变下项求和 ) 变系数求和 2 证明 ( 使用已知恒等式证明 )

使用 已知恒等式 证明下面的恒等式 :

∑ k = 0 n k 2 ( n k ) = n ( n + 1 ) 2 n − 2 \sum\limits_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2} k=0∑n​k2(kn​)=n(n+1)2n−2

1. 已知恒等式列举 :

• ① 递推式 1 1 1 : ( n k ) = ( n n − k ) \dbinom{n}{k} = \dbinom{n}{n-k} (kn​)=(n−kn​)
• ② 递推式 2 2 2 : ( n k ) = n k ( n − 1 k − 1 ) \dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1} (kn​)=kn​(k−1n−1​)
• ③ 递推式 3 3 3 帕斯卡 / 杨辉三角公式 : ( n k ) = ( n − 1 k ) + ( n − 1 k − 1 ) \dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1} (kn​)=(kn−1​)+(k−1n−1​)
• ④ 变下项求和 1 简单和 : ∑ k = 0 n ( n k ) = 2 n \sum_{k=0}^{n}\dbinom{n}{k} = 2^n k=0∑n​(kn​)=2n
• ⑤ 变下项求和 2 交错和 : ∑ k = 0 n ( − 1 ) k ( n k ) = 0 \sum_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0 k=0∑n​(−1)k(kn​)=0

2. 变下限 : 从 ∑ k = 0 n k 2 ( n k ) \sum\limits_{k=0}^{n} k^2 \dbinom{n}{k} k=0∑n​k2(kn​) 开始推导 , k = 0 k=0 k=0 时 , k 2 ( n k ) = 0 k^2 \dbinom{n}{k} = 0 k2(kn​)=0 , 可以忽略 , 这里可以从 1 1 1 开始累加 ;

∑ k = 0 n k 2 ( n k ) = ∑ k = 1 n k 2 ( n k ) \sum\limits_{k=0}^{n} k^2 \dbinom{n}{k} = \sum\limits_{k=1}^{n} k^2 \dbinom{n}{k} k=0∑n​k2(kn​)=k=1∑n​k2(kn​)

使用 ( n k ) = n k ( n − 1 k − 1 ) \dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1} (kn​)=kn​(k−1n−1​) 恒等式替换其中的 ( n k ) \dbinom{n}{k} (kn​) :

= ∑ k = 1 n k 2 n k ( n − 1 k − 1 ) = \sum\limits_{k=1}^{n} k^2 \dfrac{n}{k} \dbinom{n - 1}{k - 1} =k=1∑n​k2kn​(k−1n−1​)

3. 消去变系数 : 消去一个 k k k 后 , 变成如下公式 :

= ∑ k = 1 n k n ( n − 1 k − 1 ) =\sum\limits_{k=1}^{n} k n \dbinom{n - 1}{k - 1} =k=1∑n​kn(k−1n−1​)

4. 常量外提 : 其中的 n n n 相对于求和来说 , 是一个常量 , 可以提到求和符号之外 :

= n ∑ k = 1 n k ( n − 1 k − 1 ) =n\sum\limits_{k=1}^{n} k \dbinom{n - 1}{k - 1} =nk=1∑n​k(k−1n−1​)

5. 变形及拆解 : 在组合数中有 ( n − 1 k − 1 ) \dbinom{n - 1}{k - 1} (k−1n−1​) , 为了与 k − 1 k-1 k−1 进行匹配 , 这里将 k k k 进行变形 , k = ( k − 1 ) + 1 k = (k - 1) + 1 k=(k−1)+1 , 可以凑出一个 k − 1 k-1 k−1 来 ;

= n ∑ k = 1 n [ ( k − 1 ) + 1 ] ( n − 1 k − 1 ) =n\sum\limits_{k=1}^{n} [( k - 1 ) +1] \dbinom{n - 1}{k - 1} =nk=1∑n​[(k−1)+1](k−1n−1​)

利用求和公式 , 将上述式子拆解成两个和式 ,

= n ∑ k = 1 n ( k − 1 ) ( n − 1 k − 1 ) + n ∑ k = 1 n ( n − 1 k − 1 ) =n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1} + n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1} =nk=1∑n​(k−1)(k−1n−1​)+nk=1∑n​(k−1n−1​)

6. 第一个组合式转换 : n ∑ k = 1 n ( k − 1 ) ( n − 1 k − 1 ) n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1} nk=1∑n​(k−1)(k−1n−1​) 求和 ,

k = 1 k=1 k=1 时 , 组合数的下项 , 加和式中的系数 k − 1 = 0 k-1=0 k−1=0 , 将 k k k 作下限的变换 , k k k 取值是 1 1 1 ~ n n n , 则 k − 1 k-1 k−1 取值是 0 0 0 ~ ( n − 1 ) (n-1) (n−1) ,

相当于使用 k ′ = k − 1 k' = k-1 k′=k−1 替代之前的 k k k , k ′ k' k′ 取值范围 0 0 0 ~ ( n − 1 ) (n-1) (n−1) ,

因此最终可以变为 n ∑ k ′ = 0 n − 1 ( k ′ ) ( n − 1 k ′ ) n\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'} nk′=0∑n−1​(k′)(k′n−1​)

使用 ∑ k = 0 n k ( n k ) = n 2 n − 1 \sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1} k=0∑n​k(kn​)=n2n−1 组合恒等式 ,

上述 ∑ k ′ = 0 n − 1 ( k ′ ) ( n − 1 k ′ ) \sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'} k′=0∑n−1​(k′)(k′n−1​) 的结果是 ( n − 1 ) 2 n − 2 (n-1)2^{n-2} (n−1)2n−2 ,

前面乘以 n n n , 最终的 n ∑ k ′ = 0 n − 1 ( k ′ ) ( n − 1 k ′ ) = n ( n − 1 ) 2 n − 2 n\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'} = n(n-1)2^{n-2} nk′=0∑n−1​(k′)(k′n−1​)=n(n−1)2n−2

7. 第二个组合式转换 : n ∑ k = 1 n ( n − 1 k − 1 ) n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1} nk=1∑n​(k−1n−1​) 该组合式中 k k k 取值是 1 1 1 ~ n n n , 将 k k k 变为从 0 0 0 开始 , 即使用 k ′ = k − 1 k' = k-1 k′=k−1 替代 k k k ,

则有 n ∑ k ′ = 0 n − 1 ( n − 1 k ′ ) n\sum\limits_{k'=0}^{n-1} \dbinom{n - 1}{k'} nk′=0∑n−1​(k′n−1​) , 该求和可以转变成基本求和 ,

使用 简单和 组合恒等式 ∑ k = 0 n ( n k ) = 2 n \sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n k=0∑n​(kn​)=2n ,

∑ k ′ = 0 n − 1 ( n − 1 k ′ ) \sum\limits_{k'=0}^{n-1} \dbinom{n - 1}{k'} k′=0∑n−1​(k′n−1​) 就是 2 n − 1 2^{n-1} 2n−1 , 前面乘以 n n n , n ∑ k = 1 n ( n − 1 k − 1 ) n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1} nk=1∑n​(k−1n−1​) 就是 n 2 n − 1 n2^{n-1} n2n−1

= n ∑ k = 1 n ( k − 1 ) ( n − 1 k − 1 ) + n ∑ k = 1 n ( n − 1 k − 1 ) =n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1} + n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1} =nk=1∑n​(k−1)(k−1n−1​)+nk=1∑n​(k−1n−1​)

= n ( n − 1 ) 2 n − 2 + n 2 n − 1 =n(n-1)2^{n-2} + n2^{n-1} =n(n−1)2n−2+n2n−1

= n ( n − 1 ) 2 n − 2 + n 2 × 2 n − 2 =n(n-1)2^{n-2} + n 2 \times2^{n-2} =n(n−1)2n−2+n2×2n−2

= n ( n + 1 ) 2 n − 2 =n(n+1)2^{n-2} =n(n+1)2n−2

总结 : 先利用 递推式 , 消掉变系数 k k k , 将求和的每个式子凑成基本求和公式 , 或 已知求和公式 , 然后进行求和变限 , 即使用 k ′ = k − 1 k' = k-1 k′=k−1 替换 k k k , 通过上述技巧 , 完成证明 ;