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

2023-03-28 18:17:36 浏览数 (1)

文章目录

  • 一、组合恒等式 ( 变下项求和 ) 变系数求和 1
  • 二、组合恒等式 ( 变下项求和 ) 变系数求和 1 证明 ( 二项式定理 求导 )
  • 三、组合恒等式 ( 变下项求和 ) 变系数求和 2
  • 四、组合恒等式 ( 变下项求和 ) 变系数求和 2 证明 ( 使用已知恒等式证明 )

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

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

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

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

0

~

n

;

1. 证明方法 :

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

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

5

个组合恒等式 代入 ;

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

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

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

二项式定理 :

(x y)^n = sumlimits_{k=0}^n dbinom{n}{k}x^k y^{n-k}

1.

y = 1

时有该情况 :

(x 1)^n = sumlimits_{k=0}^n dbinom{n}{k}x^k

, 上述公式中 , 将常数项

k= 0

的情况单独计算出来 ,

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

, 计算过程如下 :

(x 1)^n = sumlimits_{k=0}^n dbinom{n}{k}x^k = dbinom{n}{0}x^0 sumlimits_{k=1}^n dbinom{n}{k}x^k = 1 sumlimits_{k=1}^n dbinom{n}{k}x^k

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

sumlimits_{k=1}^n dbinom{n}{k}x^k

中出现

k

变化数 , 需要对

x

进行求导 ;

这里直接对

(x 1)^n = 1 sumlimits_{k=1}^n dbinom{n}{k}x^k

等式两边进行求导 ;

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

(x 1)^n

导数为

n(x 1)^{n-1}

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

1 sumlimits_{k=1}^n dbinom{n}{k}x^k

导数为 ,

1

的导数 为

0

, 加上

sumlimits_{k=1}^n dbinom{n}{k}x^k

的导数

sumlimits_{k=1}^n k dbinom{n}{k}x^{k-1}

, 最终结果是

sumlimits_{k=1}^n k dbinom{n}{k}x^{k-1}

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

n(x 1)^{n-1} = sumlimits_{k=1}^n k dbinom{n}{k}x^{k-1}

幂函数求导 : ( 很重要 )

  • 原函数 :
y = x^n
  • 对应导数 :
y' = nx^{n-1}

/ 常数的导数是

0

; / 导数四则运算 :

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

/ 参考 : 导数 - 百度百科

3. 求导后的结果如下 :

n(x 1)^{n-1} = sumlimits_{k=1}^n k dbinom{n}{k}x^{k-1}

假设求导结果中的

x = 1

, 有如下结果 :

n2^{n-1} = sumlimits_{k=1}^n k dbinom{n}{k}

当

k = 0

时 , 有

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

,

因此加上

k=0

的情况 , 即

k

从

0

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

n2^{n-1} = sumlimits_{k=0}^n k dbinom{n}{k}

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

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

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

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

0

~

n

;

证明方法 :

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

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

5

个组合恒等式 代入 ;

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

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

sumlimits_{k=0}^{n} k^2 dbinom{n}{k} = n ( n 1 ) 2^{n-2}

1. 已知恒等式列举 :

  • ① 递推式
1

:

dbinom{n}{k} = dbinom{n}{n-k}
  • ② 递推式
2

:

dbinom{n}{k} = dfrac{n}{k} dbinom{n - 1}{k - 1}
  • ③ 递推式
3

帕斯卡 / 杨辉三角公式 :

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. 变下限 : 从

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

开始推导 ,

k=0

时 ,

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

, 可以忽略 , 这里可以从

1

开始累加 ;

sumlimits_{k=0}^{n} k^2 dbinom{n}{k} = sumlimits_{k=1}^{n} k^2 dbinom{n}{k}

使用

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

恒等式替换其中的

dbinom{n}{k}

:

= sumlimits_{k=1}^{n} k^2 dfrac{n}{k} dbinom{n - 1}{k - 1}

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

k

后 , 变成如下公式 :

=sumlimits_{k=1}^{n} k n dbinom{n - 1}{k - 1}

4. 常量外提 : 其中的

n

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

=nsumlimits_{k=1}^{n} k dbinom{n - 1}{k - 1}

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

dbinom{n - 1}{k - 1}

, 为了与

k-1

进行匹配 , 这里将

k

进行变形 ,

k = (k - 1) 1

, 可以凑出一个

k-1

来 ;

=nsumlimits_{k=1}^{n} [( k - 1 ) 1] dbinom{n - 1}{k - 1}

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

=nsumlimits_{k=1}^{n} ( k - 1 ) dbinom{n - 1}{k - 1} nsumlimits_{k=1}^{n} dbinom{n - 1}{k - 1}

6. 第一个组合式转换 :

nsumlimits_{k=1}^{n} ( k - 1 ) dbinom{n - 1}{k - 1}

求和 ,

k=1

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

k-1=0

, 将

k

作下限的变换 ,

k

取值是

1

~

n

, 则

k-1

取值是

0

~

(n-1)

,

相当于使用

k' = k-1

替代之前的

k

,

k'

取值范围

0

~

(n-1)

,

因此最终可以变为

nsumlimits_{k'=0}^{n-1} ( k' ) dbinom{n - 1}{k'}

使用

sumlimits_{k=0}^{n} k dbinom{n}{k} = n 2^{n-1}

组合恒等式 ,

上述

sumlimits_{k'=0}^{n-1} ( k' ) dbinom{n - 1}{k'}

的结果是

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

,

前面乘以

n

, 最终的

nsumlimits_{k'=0}^{n-1} ( k' ) dbinom{n - 1}{k'} = n(n-1)2^{n-2}

7. 第二个组合式转换 :

nsumlimits_{k=1}^{n} dbinom{n - 1}{k - 1}

该组合式中

k

取值是

1

~

n

, 将

k

变为从

0

开始 , 即使用

k' = k-1

替代

k

,

则有

nsumlimits_{k'=0}^{n-1} dbinom{n - 1}{k'}

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

使用 简单和 组合恒等式

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

,

sumlimits_{k'=0}^{n-1} dbinom{n - 1}{k'}

就是

2^{n-1}

, 前面乘以

n

,

nsumlimits_{k=1}^{n} dbinom{n - 1}{k - 1}

就是

n2^{n-1}
=nsumlimits_{k=1}^{n} ( k - 1 ) dbinom{n - 1}{k - 1} nsumlimits_{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' = k-1

替换

k

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

百度 技巧 数学

0 人点赞