热搜: 数分高代概率统计

博士家园 › huppid › 日志

huppid

这里不讨论理论物理，剩下的就是饭后品。

组合恒等式——高斯型镶嵌

热度 3已有 615 次阅读2009-10-29 16:06 |

$Question:\sum_{k=0}^n{2k\choose k}{2n-2k\choose n-k}=4^n$

第一部曲：平静海湾，遥不及岸

对此运用数学归纳法：

1.当n=1时，显然成立；

2.当n=n时，假设成立；

3.当n=n+1时，

$\sum_{k=0}^{n+1}{2k\choose k}{2n-2k+2\choose n-k+1}={2n+2\choose n+1}+\sum_{k`=0}^{n}{2(k`+1)\choose k`+1}{2n-2k`\choose n-k`}={2n+2\choose n+1}+4^{n+1}-\sum_{k`=0}^{n}\frac{2}{k`+1}{2k`\choose k`}{2n-2k`\choose n-k`}$

这里k`=k-1,由上式可知等价于证明：

${2n+2\choose n+1}=\sum_{k`=0}^{n}\frac{2}{k`+1}{2k`\choose k`}{2n-2k`\choose n-k`}=\sum_{k=1}^{n+1}\frac{2}{k}{2(k-1)\choose k-1}{2(n+1)-2k\choose (n+1)-k}$

这相当于证明对任意n上式均成立

第二部曲：万象合一，形神相似

经过巧妙的处理得：

${2n\choose n}=\sum_{k=1}^{n}\frac{n+1}{(n-k+1)k}{2(k-1)\choose k-1}{2(n-k)\choose n-k}$

稍微改动一下有：

$\frac{1}{n+1}{2n\choose n}=\sum_{k=1}^{n}\frac{1}{k}{2(k-1)\choose k-1}\frac{1}{n-k+1}{2(n-k)\choose n-k}$

不妨设：

$h_k=\frac{1}{k}{2(k-1)\choose k-1}$

即得

$h_{n+1}=\sum_{k=1}^{n}h_{k}h_{n-k+1}$

第三部曲：上下颠倒，互转乾坤

解决以上问题相当于证明一下命题：已知

$h_1=1,h_{n+1}=\sum_{k=1}^{n}h_{k}h_{n-k+1}$

为序列 $\{h_n\}$ 的递推公式，证明：

$h_k=\frac{1}{k}{2(k-1)\choose k-1}$

序列 $\{h_n\}$ 的生成函数为

$g(x)=h_1x+h_2x^2+\cdots+h_nx^n+\cdots$

有

$g^2(x)=(h_1x+h_2x^2+\cdots+h_nx^n+\cdots)(h_1x+h_2x^2+\cdots+h_nx^n+\cdots)$

$=g(x)-x$

通过代入某些解检验可得

$g(x)=\frac{1-\sqrt{1-4x}}{2}$

第四部曲：最后的结局

根据牛顿二项式定理，

$(1+z)^{\frac{1}{2}}=1+\sum_{k=1}^{\infty}(-1)^{k-1}\frac{1}{2^{2k-1}}\frac{1}{k}{2k-2\choose k-1}z^k}$

代入 $z=-4x$

可得

$g(x)=\sum_{k=1}^{\infty}\frac{1}{k}{2k-2\choose k-1}x^k$

即得

$h_k=\frac{1}{k}{2k-2\choose k-1}$

于是原结论成立。

刚表态过的朋友 (3 人)

yxw10

收藏邀请举报

全部作者的其他最新日志

• 星期六之夜
• 数学系必看的十部电影

发表评论评论 (1 个评论)

回复 mlmiliang 2011-7-25 14:37

网站地图
博士数学题库
博士数学文库
博士数学投稿
联系邮箱：www#math.org.cn（请把#改成@）

微信公众平台

扫描访问手机版

关于我们|手机版|订阅|博士家园 ( 沪ICP备15045866号-1 )（ $沪公网安备$ 沪公网安备 31011702001868号）

GMT+8, 2024-5-4 14:47 , Processed in 0.095740 second(s), 18 queries .

Powered by Discuz! X3.4

© 2004-2024 博士家园

获赠：邀请码
博士投稿
请发电子邮件
电子邮件
www@math.org.cn

在线时间：9:00-16:00
返回顶部