证明
songziyu
·
·
算法·理论
证明：
$其中\begin{pmatrix}n\\k\end{pmatrix}=C_n^k，n!!=\begin{cases}1\times3\times\cdots\times n&,&n\%2=1\\2\times4\times\cdots\times n&,&n\%2=0\end{cases}\\$
## 证法1：
$\\$\
$\\首先配成二项式定理的形式：$
$$\sum\limits_{k=0}^{n}\binom{n}{k}\cfrac{(-1)^k}{2k+1}
=\sum\limits_{k=0}^{n}\binom{n}{k}(-1)^{2n-k}\cfrac{1}{2k+1}\tag{1}
\\=\sum\limits_{k=0}^{n}\binom{n}{k}(-1)^{n-k}(-1)^n\int_0^1x^{2k}\mathrm{~d}x\tag{2}
$通过二项式定理：\\
(1-x^2)^n=(-1)^n(x^2-1)^n\\=(-1)^n\sum\limits_{k=0}^{n}\binom{n}{k}x^{2k}(-1)^{n-k}\\=\sum\limits_{k=0}^{n}\binom{n}{k}x^{2k}(-1)^{n-k}(-1)^n
对原式进行变形：\\
\sum\limits_{k=0}^{n}\binom{n}{k}(-1)^{n-k}(-1)^nx^{2k}\mathrm{~d}x\\=\sum\limits_{k=0}^{n}\int_0^1\binom{n}{k}(-1)^{n-k}(-1)^nx^{2k}\mathrm{~d}x\\=\int_0^1\sum\limits_{k=0}^{n}\binom{n}{k}(-1)^{n-k}x^{2k}(-1)^n\mathrm{~d}x\\=\int_0^1(1-x^2)^n\mathrm{~d}x
现在只需要求出这个积分即可，使用分部积分法，构造积分列：\\
记：
I_{n}=\int(1-x^2)^n\mathrm{~d}x
根据分部积分法：(\displaystyle \int u\mathrm{~d}v=uv-\int v\mathrm{~d}u)
I_n=x(1-x^2)^n-\int x\mathrm{d}(1-x^2)^n
注意到：
\mathrm{d}(1-x^2)^n=-2nx(1-x^2)^{n-1}\mathrm{~d}x
于是：
I_n=x(1-x^2)^n-\int\begin{pmatrix}-2nx^2(1-x^2)^{n-1} \mathrm{~d}x\end{pmatrix}\\=x(1-x^2)^n+2n\int x^2(1-x^2)^{n-1}\mathrm{~d}x
由于\displaystyle x^2=1-(1-x^2)：
I_n=x(1-x^2)^n+2n\int(1-(1-x^2))(1-x^2)^{n-1}\mathrm{d}x\\=x(1-x^2)+2n\int(1-x^2)^{n-1}\mathrm{~d}x-(1-x^2)(1-x^2)^{n-1}\mathrm{~d}x\\=x(1-x^2)^n+2n\int(1-x^2)^{n-1}\mathrm{~d}x-(1-x^2)^n\mathrm{~d}x\\=x(1-x^2)^n+2n\int(1-x^2)^{n-1}\mathrm{~d}x-2n\int(1-x^2)^n\mathrm{~d}x\\=x(1-x^2)^n+2nI_{n-1}-2nI_n
所以：
(2n+1)I_n=x(1-x^2)^n+2nI_{n-1}\\In=\cfrac{x(1-x^2)^n}{2n+1}+\cfrac{2n}{2n+1}I_{n-1}\ \ \ \ (3)
不定积分已经计算完毕，现在开始求定积分：\\
设(3)式的原函数为F_n(x)，则F_0(0)=0，F_0(1)=1\\
开始递推：
F_n(0)=\cfrac{0(1-0^2)^n}{2n+1}+\cfrac{2n}{2n+1}F_{n-1}(0)\\=\cfrac{2n}{2n+1}F_{n-1}(0)\\=\cfrac{2n}{2n+1}\times\cfrac{2n-2}{2n-1}F_{n-2}(0)\\=\cfrac{2n}{2n+1}\times\cfrac{2n-2}{2n-1}\times\cfrac{2n-4}{2n-3}\times\cdots\\=\cfrac{(2n)!!}{(2n+1)!!}F_0(0)=0
F_n(1)=\cfrac{1(1-1^2)^n}{2n+1}+\cfrac{2n}{2n+1}F_{n-1}(1)\\=\cfrac{(2n)!!}{(2n+1)!!}F_0(1)\\=\cfrac{(2n)!!}{(2n+1)!!}
证毕
证法2：
引入扩展组合数：
\binom{n}{k}(n\in\mathbb{R},k\in\mathbb{N})=\frac{\prod_{j=0}^{k-1}(n-j)}{k!})\tag{1}
扩展组合数满足扩展二项式定理：
(x+y)^n=\sum\limits_{k=0}^{\infty}\binom{n}{k}x^ky^{n-k}(n\in\mathbb{R})
考虑特殊形式：
(1+x)^n=\sum\limits_{k=0}^{\infty}\binom{n}{k}x^k
记\displaystyle[x^k]表示一个多项式的x^k项系数，则：
[x^k](1+x)^n=\binom{n}{k}\tag{2}
\
\\
扩展组合数的几个特殊性质：
性质1：
\binom{-1}{k}=(-1)^k
证明：
\binom{-1}{k}=\cfrac{(-1-0)(-1-1)(-1-2)(\cdots)(-1-k+1)}{k!}\\=(-1)^k\cfrac{1\times2\times3\times\cdots\times k}{k!}\\=(-1)^k\cfrac{k!}{k!}=(-1)^k
性质2：
\binom{-\frac{1}{2}}{k}=(-1)^k\cfrac{(2k-1)!!}{2^kk!}=(-1)^k\cfrac{(2k-1)!!}{(2k)!!}\tag{3}
证明：
\binom{-\frac{1}{2}}{k}=\cfrac{\prod_{j=0}^{k-1}(-\frac{1}{2}-j)}{k!}\\=(-1)^k\cfrac{\prod_{j=0}^{k-1}(\frac{1}{2}+j)}{k!}\\=(-1)^k\cfrac{\prod_{j=0}^{k-1}(\frac{1+2j}{2})}{k!}\\=(-1)^k\cfrac{\prod_{j=0}^{k-1}(1+2j)}{2^kk!}\\=(-1)^k\cfrac{(2k-1)!!}{2^kk!}
对于双阶乘，有：
(2n)!!=\prod_{k=1}^{n}(2k)=2^k\prod_{k=1}^{n}k=2^kk!\tag{4}
于是：
(-1)^k\cfrac{(2k-1)!!}{2^kk!}=(-1)^k\cfrac{(2k-1)!!}{(2k)!!}
(3)式证毕
考虑用\displaystyle\binom{-\frac{1}{2}}{k}构造等式：
\binom{n}{k}\cfrac{(-1)^k}{2k+1}=\cfrac{(2n)!!}{(2n+1)!!}\binom{-\frac{1}{2}}{k}\binom{x}{n-k}\tag{5}
由此，最后只需证明：
\sum_{k=0}^{n}\cfrac{(2n)!!}{(2n+1)!!}\binom{-\frac{1}{2}}{k}\binom{x}{n-k}=\cfrac{(2n)!!}{(2n+1)!!}
即：
\cfrac{(2n)!!}{(2n+1)!!}\sum_{k=0}^{n}\binom{-\frac{1}{2}}{k}\binom{x}{n-k}=\cfrac{(2n)!!}{(2n+1)!!}
即：
\sum_{k=0}^{n}\binom{-\frac{1}{2}}{k}\binom{x}{n-k}=1
对(5)中的组合数利用(3)式进行展开：
\cfrac{n!}{k!(n-k)!}\times\cfrac{(-1)^k}{2k+1}=\cfrac{(2n)!!}{(2n+1)!!}\times\cfrac{(-1)^k(2k-1)!!}{2^kk!}\times\cfrac{\prod_{j=0}^{n-k-1}(x-j)}{(n-k)!}
先约分：
\cfrac{n!}{2k+1}=\cfrac{(2n)!!}{(2n+1)!!}\times\cfrac{(2k-1)!!}{2^k}\prod_{j=0}^{n-k-1}(x-j)
注意到(2n+1)!!与(2k-1)!!和(2k-1)可以约分，即：
(2n+1)!!=1\times3\times\cdots\times(2k-1)\times(2k+1)\times\cdots\times(2n+1)
于是原式化简为：
n!=\cfrac{(2n)!!}{\prod_{j=0}^{n-k-1}2n+1-2j}\times\cfrac{1}{2^k}\prod_{j=0}^{n-k-1}(x-j)
由(4)式，为消去(2n)!!与n!，将等号右边分母乘上2^{n-k}\\
同时\prod_{j=0}^{n-k-1}(x-j)化简后必须包含\prod_{j=0}^{n-k-1}(2n+1-2j)\\
令2n+1-2j=2x-2j,x=n+\frac{1}{2}
\displaystyle 于是最后构造出等号右侧的项为\binom{n+\frac{1}{2}}{n-k}\\
既然已经构造出：
\binom{n}{k}\cfrac{(-1)^k}{2k+1}=\cfrac{(2n)!!}{(2n+1)!!}\binom{-\frac{1}{2}}{k}\binom{n+\frac{1}{2}}{n-k}
证明原式
\sum_{k=0}^{n}\binom{n}{k}\cfrac{(-1)^k}{2k+1}=\cfrac{(2n!!)}{(2n+1)!!}
的时候，只需证明：
\sum_{k=0}^{n}\binom{-\frac{1}{2}}{k}\binom{n+\frac{1}{2}}{n-k}=1
考虑利用式(2)：
\sum_{k=0}^{n}\binom{-\frac{1}{2}}{k}\binom{n+\frac{1}{2}}{n-k}=\sum_{k=0}^{n}[x^k](1+x)^{-\frac{1}{2}}[x^{n-k}](1+x)^{n+\frac{1}{2}}\tag{6}
\displaystyle 对于(6)式进行卷积，设f(x)=(1+x)^{-\frac{1}{2}}，g(x)=(1+x)^{n+\frac{1}{2}}\\
则：
\sum_{k=0}^{n}\binom{-\frac{1}{2}}{k}\binom{n+\frac{1}{2}}{n-k}=\sum_{k=0}^{n}[x^k]f(x)x^{n-k}g(x)=[x^n](f*g)
\displaystyle f*g等于(1+x)^{-\frac{1}{2}}\times(1+x)^{n+\frac{1}{2}}=(1+x)^n\\
\displaystyle 于是上式就等于[x^n](1+x)^n\\
利用(2)式，则可得：
[x^n](1+x)^n=\binom{n}{n}=1
证毕