首页 > 其他分享 >几则组合求和式的积分解法

几则组合求和式的积分解法

时间:2023-08-30 21:22:17浏览次数:45  
标签:right mathrm 求和 sum int choose 几则 解法 left

记号约定:本文中默认 \(n\in\mathbb{N}\),\(k\in\mathbb Z\),隐去范围的求和指标取一切使求和对象有意义且非零的值.


【例 1】

\[\sum_k{n\choose k}\dfrac1{k+1}. \]

【解】注意到 \(\displaystyle\int x^k\mathrm{d}x=\dfrac1{k+1}x^{k+1}+C\),于是

\[\begin{aligned} \sum_k{n\choose k}\dfrac1{k+1}&=\sum_k{n\choose k}\int_0^1x^k\mathrm{d}x \\&=\int_0^1\sum_k{n\choose k}x^k\mathrm{d}x \\&=\int_0^1(x+1)^n\mathrm{d}x&\text{(二项式定理)} \\&=\left.\dfrac{(x+1)^{n+1}}{n+1}\right|_0^1 \\&=\dfrac{2^{n+1}-1}{n+1}. \end{aligned} \]

当然,本例过于简单,以至于有更简单的初等解法:

\[\begin{aligned} \sum_k{n\choose k}\dfrac1{k+1}&=\sum_{k\ne-1}{n+1\choose k+1}\dfrac1{n+1}&\text{(吸收恒等式)} \\&=\dfrac{(1+1)^{n+1}-1}{n+1}&\text{(二项式定理)} \\&=\dfrac{2^{n+1}-1}{n+1}. \end{aligned} \]

注意:使用吸收恒等式的条件是 \(k+1\ne0\). 小心不要掉进陷阱里,否则会多算一项.

将本例的求和改为求交错和,得到一个对应的问题:


【例 2】

\[\sum_k{n\choose k}(-1)^{k}\dfrac1{k+1}. \]

【解】方法类似.

\[\begin{aligned} \sum_k{n\choose k}(-1)^{k}\dfrac1{k+1}&=\sum_k{n\choose k}(-1)^{k}\int_0^1x^k\mathrm{d}x \\&=\int_0^1\sum_k{n\choose k}(-x)^k\mathrm{d}x \\&=\int_0^1(1-x)^n\mathrm{d}x&\text{(二项式定理)} \\&=\int_0^1x^n\mathrm{d}x \\&=\left.\dfrac{x^{n+1}}{n+1}\right|_0^1 \\&=\dfrac1{n+1}. \end{aligned} \]

可以看到,交错和的结果更加简单一些. 事实上,下面几例交错和问题,去掉符号就做不了了. 这可能是因为交错和往往蕴含着一些容斥意义(笔者臆测).

本例也有与上例类似的初等解法. 然而,在面对更复杂的问题时,几个基本组合恒等式就显得不够用了.


【例 3】

\[\sum_k{n\choose k}(-1)^k\dfrac1{2k+1}. \]

本例及下述解法来自 https://math.stackexchange.com/questions/4742691/. 也有初等解法,但不易想到,且更为复杂.

【解】采用类似的处理方法.

\[\begin{aligned} \sum_k{n\choose k}(-1)^k\dfrac1{2k+1}&=\sum_k{n\choose k}(-1)^k\int_0^1x^{2k}\mathrm{d}x \\&=\int_0^1\sum_k{n\choose k}(-1)^kx^{2k}\mathrm{d}x \\&=\int_0^1\left(1-x^2\right)^n\mathrm{d}x&\text{(二项式定理)} \end{aligned} \]

设所求为 \(I_n:=\displaystyle\int_0^1\left(1-x^2\right)^n\mathrm{d}x\),有 \(I_0=1\). 对 \(n>0\),

\[\begin{aligned} I_n&=\left(x\left(1-x^2\right)^n\right)_0^1-\int_0^1 x\cdot\mathrm{d}\left(1-x^2\right)^{n} \\&=0-\int_0^1 x\cdot (-2x)n\left(1-x^2\right)^{n-1} \\&=2n\int_0^1 x^2\left(1-x^2\right)^{n-1} \\&=2n\left(\int_0^1 1\cdot\left(1-x^2\right)^{n-1}-\int_0^1 (1-x^2)\left(1-x^2\right)^{n-1}\right) \\&=2n(I_{n-1}-I_n). \end{aligned} \]

于是 \(I_n=\dfrac{2n}{2n+1}I_{n-1}\),解得 \(I_n=\dfrac{(2n)!!}{(2n+1)!!}\).


【例 4】

\[\sum_k{n\choose k}(-1)^k\dfrac1k. \]

本例截取自某考研数学题的某一步骤,原题来源已不可考.

【解】初看与【例 1】没什么两样. 一个很明显的差别是 \(k\) 变成从 \(1\) 开始,仔细分析会发现分母的变化导致组合恒等式完全用不了. 然而,正如前三例中所见,对指标在分母上的情况,积分法尤为有效.

\[\begin{aligned} \sum_k{n\choose k}(-1)^k\dfrac1k&=\sum_{k\ne0}{n\choose k}(-1)^k\int_0^1x^{k-1}\mathrm{d}x \\&=\int_0^1\sum_{k\ne0}{n\choose k}(-1)^kx^{k-1}\mathrm{d}x \\&=\int_0^1\dfrac{\left(1-x\right)^n-1}x\mathrm{d}x&\text{(二项式定理)} \\&=\int_0^1\dfrac{((1-x)-1)\sum_{i=0}^{n-1}(1-x)^i}x\mathrm{d}x&\text{(因式分解)} \\&=-\int_0^1\sum_{i=0}^{n-1}(1-x)^i\mathrm{d}x \\&=-\sum_{i=0}^{n-1}\int_0^1(1-x)^i\mathrm{d}x \\&=-\sum_{i=0}^{n-1}\left.\dfrac{x^{i+1}}{i+1}\right|_0^1 \\&=-\sum_{i=1}^{n}\dfrac1i=-H_n. \end{aligned} \]

看第六个等号后的那个积分,是不是有点熟悉?在【例 2】中我们刚见过它. 这启发我们,用初等方法将本例转化为【例 2】是可能的,留做习题.

前面几例中求和指标都在分母. 事实上,对于指标与组合数直接相乘的情况,可以用类似的方法求解,这通常比初等方法步骤更少.(不过可能就不算“积分法”了,因为这次是转化成导数.)


【例 5】

\[\sum_k{n\choose k}k^2. \]

【解】

\[\begin{aligned} \sum_k{n\choose k}k^2&=\left.\sum_k{n\choose k}\left(\left(x^k\right)''+\left(x^k\right)'\right)\right|_{x=1} \\&=\left.\left(\sum_k{n\choose k}x^k\right)''+\left(\sum_k{n\choose k}x^k\right)'\right|_{x=1} \\&=\left.\left((x+1)^n\right)''+\left((x+1)^n\right)'\right|_{x=1} \\&=n(n-1)2^{n-2}+n\cdot2^{n-1} \\&=n(n+1)2^{n-2}. \end{aligned} \]

这样做其实是先把 \(k^2\) 从普通幂转成下降幂,再运用导数把下降幂换回 \(x\) 的普通幂(以便使用二项式定理). 这种做法应当可推广到任意次幂的情形,留做习题.


更多例题待续.


后注:以上所有题目应当都可以用生成函数求解,有空的话补充.

生成函数的一个重要技巧是 \(k^n=n![x^n]\mathrm{e}^{kx}\). 这可以解决最后的【例 5】,以几乎同样少的步骤.

标签:right,mathrm,求和,sum,int,choose,几则,解法,left
From: https://www.cnblogs.com/abcc/p/equiv.html

相关文章

  • FIFO求和实验
    第44章、FIFO求和实验【理论】【注】数据矩:5行(m)4列(n)),对3行(x)求和原数据矩阵m*n,m表示行数,n表示每行数据个数fifo深度要大于每行个数(显然)fifo个数为n-1个求和后形成的结果矩阵p(行)*q(列),q=n,p=m-x+1(每个fifo要存储行的次数)要完成3行数据的SUM求和,需要调用2个FIFOIP核......
  • leetcode 题库994——bfs典型解法(队列+递归实现)
     classSolution:deforangesRotting(self,grid:list[list[int]])->int:m,n=len(grid),len(grid[0])queue,good=[],[]defbfs(queue,good,m,n,grid):times=0directions=[(-1,0),(1,0),(0,1),(0,-1)]......
  • LeetCode题库77.组合——dfs典型解法,递归+回溯+剪枝
     classSolution:defcombine(self,n:int,k:int):nums=[x+1forxinrange(n)]res,ans=[],[]defdfs(nums:list[int]):iflen(ans)==k:ans_copy=ans.copy()#复制,避免ans数组改变使res跟着改变......
  • 求和 题解
    求和题目大意给定\(n,p\),求:\[\left(\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)^{i+j}\right)\bmodp\]多组数据。思路分析老规矩,先化式子:\[\begin{aligned}\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)^{i+j}&=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^nd^{\,i+j}\,[\gcd(i,j)=d]\......
  • P8772 [蓝桥杯 2022 省 A] 求和 题解
    蒟蒻第一次发题解qwq$S=a_1\timesa_2+a_1\timesa_3+a1\timesa_n+a_2\timesa_3+···+a_n-2\timesa_n-1+a_n-1\timesa_n$从样例来看41369这道题就是要求$1\times3+1\times6+1\times9+3\times6+3\times9+6\times9$我们可以把这个算式分成几个部分$(1\t......
  • Luogu P3369 【模板】普通平衡树 01Tire树解法
    题目传送门闲话:Luogu总共105篇题解中只有4篇01Tire树解法,虽说是非正解但未免也太少了些(貌似也不少?)……总之01Tire树的效率并不低,这道题用01Tire是很轻松的。Q:这题为什么可以用01Tire树解?能否解决一个问题,无非于三个点:可行性,空间,时间。本题要求维护一个有序数集,能进行元素修改......
  • C语言编程的结构化要求和正确性与容错性要求
    一、结构化要求(1)禁止出现两条等价的支路。(2)禁止使用GOTO跳转语句。(3)用IF语句来强调只执行两组语句中的一组。禁止ELSEGOTO和ELSERETURN。(4)用CASE实现多路分支。(5)避免从循环引出多个出口。(6)3.6函数只有一个出口。(7)不使用条件赋值语句。(8)避免不必要的分支。(9)不要轻易用条件......
  • 【LeetCode173. 最多连胜的次数】MySQL用户变量编程解法
    目录题目地址题目描述代码题目地址https://leetcode.cn/problems/longest-winning-streak/description/题目描述选手的 连胜数是指连续获胜的次数,且没有被平局或输球中断。编写解决方案来计算每个参赛选手最多的连胜数。结果可以以任何顺序返回。代码WITHt1AS(......
  • java stream分组之后求和
    javastream分组之后求和癞蛤蟆吃了小天鹅于2022-08-2609:37:42发布6023收藏4文章标签:java版权注:elementComponentDtos.stream().mapToDouble(ElementComponentDto::getAmount).sum();为求和可以根据返回类型的不同去改变相对应的求和函数(mapToDouble)注BigDecimal为了保......
  • 求和为target的数字组合
    题目:现给定⼀个整数数组(数组⻓度⼤于等于5)nums和⼀个整数⽬标值target,请你在该数组中找出和为⽬标值target的那n(n<nums.length)个整数,并返回它们的数组(如果有多个下标组合都满⾜,则返回下标和最⼩的那⼀组)的下标。注意:数组中同⼀个元素在答案⾥不能重复出现。⽐如输⼊:nums=......