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

韩曙亮

发布于 2023-03-28 18:17:36

9060

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

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

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

\sum_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}

随着求和的项不断变化 , 变化范围

;

1. 证明方法 :

二项式定理 : 使用二项式定理 + 求导可以证明该组合恒等式 ;
组合恒等式代入 : 使用已知组合恒等式代入 , 消去变系数 ; 即使用之前的

个递推式 , 简单和 , 交错和 ,

个组合恒等式代入 ;

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

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

\sum_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}

二项式定理 :

(x + y)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k y^{n-k}

y = 1

时有该情况 :

(x +1)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k

, 上述公式中 , 将常数项

k= 0

的情况单独计算出来 ,

\dbinom{n}{0}x^0 = 1

, 计算过程如下 :

(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

2. 引入求导 : 要在加和式

\sum\limits_{k=1}^n \dbinom{n}{k}x^k

中出现

变化数 , 需要对

进行求导 ;

这里直接对

(x +1)^n = 1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k

等式两边进行求导 ;

( 1 ) 左边组合式 ( 根据下面的幂函数导数公式计算 ) :

(x +1)^n

导数为

n(x+1)^{n-1}

( 2 ) 右边组合式 ( 根据下面的导数运算规则和幂函数导数公式计算 ) :

1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k

导数为 ,

的导数为

, 加上

\sum\limits_{k=1}^n \dbinom{n}{k}x^k

的导数

\sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}

, 最终结果是

\sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}

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

n(x+1)^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}

幂函数求导 : ( 很重要 )

原函数 :

y = x^n

对应导数 :

y' = nx^{n-1}

/ 常数的导数是

; / 导数四则运算 :

(u \pm v)' = u' \pm v'

/ 参考 : 导数 - 百度百科

3. 求导后的结果如下 :

n(x+1)^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}

假设求导结果中的

x = 1

, 有如下结果 :

n2^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}

当

k = 0

时 , 有

k \dbinom{n}{k} = 0 \times \dbinom{n}{0} = 0

因此加上

k=0

的情况 , 即

从

开始累加 , 也不影响上述结果 :

n2^{n-1} = \sum\limits_{k=0}^n k \dbinom{n}{k}

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

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

\sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}

随着求和的项不断变化 , 变化范围

;

证明方法 :

二项式定理 : 使用二项式定理 + 求导可以证明该组合恒等式 ;
组合恒等式代入 : 使用已知组合恒等式代入 , 消去变系数 ; 即使用之前的

个递推式 , 简单和 , 交错和 ,

个组合恒等式代入 ;

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

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

\sum\limits_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}

1. 已知恒等式列举 :

① 递推式

\dbinom{n}{k} = \dbinom{n}{n-k}

② 递推式

\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}

③ 递推式

帕斯卡 / 杨辉三角公式 :

\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}

④ 变下项求和 1 简单和 :

\sum_{k=0}^{n}\dbinom{n}{k} = 2^n

⑤ 变下项求和 2 交错和 :

\sum_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0

2. 变下限 : 从

\sum\limits_{k=0}^{n} k^2 \dbinom{n}{k}

开始推导 ,

k=0

时 ,

k^2 \dbinom{n}{k} = 0

, 可以忽略 , 这里可以从

开始累加 ;

\sum\limits_{k=0}^{n} k^2 \dbinom{n}{k} = \sum\limits_{k=1}^{n} k^2 \dbinom{n}{k}

使用

\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}

恒等式替换其中的

\dbinom{n}{k}

= \sum\limits_{k=1}^{n} k^2 \dfrac{n}{k} \dbinom{n - 1}{k - 1}

3. 消去变系数 : 消去一个

后 , 变成如下公式 :

=\sum\limits_{k=1}^{n} k n \dbinom{n - 1}{k - 1}

4. 常量外提 : 其中的

相对于求和来说 , 是一个常量 , 可以提到求和符号之外 :

=n\sum\limits_{k=1}^{n} k \dbinom{n - 1}{k - 1}

5. 变形及拆解 : 在组合数中有

\dbinom{n - 1}{k - 1}

, 为了与

k-1

进行匹配 , 这里将

进行变形 ,

k = (k - 1) + 1

, 可以凑出一个

k-1

来 ;

=n\sum\limits_{k=1}^{n} [( k - 1 ) +1] \dbinom{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}

6. 第一个组合式转换 :

n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1}

求和 ,

k=1

时 , 组合数的下项 , 加和式中的系数

k-1=0

, 将

作下限的变换 ,

取值是

, 则

k-1

取值是

(n-1)

相当于使用

k' = k-1

替代之前的

取值范围

(n-1)

因此最终可以变为

n\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'}

使用

\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}

组合恒等式 ,

上述

\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'}

的结果是

(n-1)2^{n-2}

前面乘以

, 最终的

n\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'} = n(n-1)2^{n-2}

7. 第二个组合式转换 :

n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1}

该组合式中

取值是

, 将

变为从

开始 , 即使用

k' = k-1

替代

则有

n\sum\limits_{k'=0}^{n-1} \dbinom{n - 1}{k'}

, 该求和可以转变成基本求和 ,

使用简单和组合恒等式

\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n

\sum\limits_{k'=0}^{n-1} \dbinom{n - 1}{k'}

就是

2^{n-1}

, 前面乘以

n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1}

就是

n2^{n-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}

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

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

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

总结 : 先利用递推式 , 消掉变系数

, 将求和的每个式子凑成基本求和公式 , 或已知求和公式 , 然后进行求和变限 , 即使用

k' = k-1

替换

, 通过上述技巧 , 完成证明 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-20，如有侵权请联系 cloudcommunity@tencent.com 删除

百度

技巧

数学

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

百度

技巧

数学

登录后参与评论

0 条评论

热度