二項係数の級数まとめ

二項係数を含む級数をできる限り挙げてみました．二項係数マニアになりたい人必見です．
証明は方針のみ載せています．詳しい証明は気が向いたら別の記事として投稿しようと思います．

二項定理

二項定理

$$\begin{gathered} \sum _{k=0}^n{x}^k{y}^{n-k}\left(\begin{array}{c}n\\ k\end{array}\right)=(x+y{)}^n \\ \sum _{k=0}^n\left(\begin{array}{c}n\\ k\end{array}\right)=2^n \\ \sum _{k=0}^n(-1{)}^k\left(\begin{array}{c}n\\ k\end{array}\right)=0 \end{gathered}$$

二項定理に$x,-x$を代入して連立
$$\begin{gathered} \sum _{i=0}^n{x}^{2i+1}\left(\begin{array}{c}n\\ 2i+1\end{array}\right)=\sum _{0\le k\le n,kは奇数}{x}^k\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{1}{2}\{(1+x{)}^n-(1-x{)}^n\} \\ \sum _{i=0}^n{x}^{2i}\left(\begin{array}{c}n\\ 2i\end{array}\right)=\sum _{0\le k\le n,kは偶数}{x}^k\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{1}{2}\{(1+x{)}^n+(1-x{)}^n\} \\ \sum _{i=0}^n\left(\begin{array}{c}n\\ 2i+1\end{array}\right)=\sum _{0\le k\le n,kは奇数}\left(\begin{array}{c}n\\ k\end{array}\right)=2^{n-1} \\ \sum _{i=0}^n\left(\begin{array}{c}n\\ 2i\end{array}\right)=\sum _{0\le k\le n,kは偶数}\left(\begin{array}{c}n\\ k\end{array}\right)=2^{n-1} \end{gathered}$$

変形すれば二項定理
$$\begin{gathered} \sum _{k=0}^{n}k{x}^k\left(\begin{array}{c}n\\ k\end{array}\right)=nx(1+x{)}^{n-1} \\ \sum _{k=0}^{n}k\left(\begin{array}{c}n\\ k\end{array}\right)=n\cdot 2^{n-1} \end{gathered}$$

対称性$\left(\begin{array}{c}n\\ k\end{array}\right)=\left(\begin{array}{c}n\\ n-k\end{array}\right)$の利用
$$\begin{gathered} \sum _{k=0}^n\left(\begin{array}{c}2n+1\\ k\end{array}\right)=2^{2n} \\ \sum _{k=0}^n\left(\begin{array}{c}2n\\ k\end{array}\right)=2^{2n-1}+\frac{1}{2}\left(\begin{array}{c}2n\\ n\end{array}\right) \end{gathered}$$

ヴァンデルモンドの畳み込み

ヴァンデルモンドの畳み込み
恒等式$(x+1{)}^p(x+1{)}^q=(x+1{)}^{p+q}$の$x^r$の係数比較
$$\sum _{k=0}^r\left(\begin{array}{c}p\\ k\end{array}\right)\left(\begin{array}{c}q\\ r-k\end{array}\right)=\left(\begin{array}{c}p+q\\ r\end{array}\right)$$

恒等式$(x+1{)}^n(1+x{)}^n=(x+1{)}^{2n}$の$x^n$の係数比較 or $n\times n$の最短経路の数え上げ
$$\sum _{k=0}^n{\left(\begin{array}{c}n\\ k\end{array}\right)}^2=\left(\begin{array}{c}2n\\ n\end{array}\right)$$

恒等式$(1-x{)}^n(x+1{)}^n=(1-x^2{)}^n$の$x^n$の係数比較
$$\sum _{k=0}^n(-1{)}^k{\left(\begin{array}{c}n\\ k\end{array}\right)}^2=\begin{array}{r}\{\begin{array}{l}(-1{)}^{\frac{n}{2}}\left(\begin{array}{c}n\\ \frac{n}{2}\end{array}\right)(nは偶数)\\ 0(nは奇数)\end{array}\end{array}$$
上2式を連立
$$\sum _{i=0}^n{\left(\begin{array}{c}n\\ 2i+1\end{array}\right)}^2=\sum _{0\le k\le n,kは奇数}{\left(\begin{array}{c}n\\ k\end{array}\right)}^2=\begin{array}{r}\{\begin{array}{l}\frac{1}{2}\{\left(\begin{array}{c}2n\\ n\end{array}\right)-(-1{)}^{\frac{n}{2}}\left(\begin{array}{c}n\\ \frac{n}{2}\end{array}\right)\}(nは偶数)\\ \frac{1}{2}\left(\begin{array}{c}2n\\ n\end{array}\right)(nは奇数)\end{array}\end{array}$$$$\sum _{i=0}^n{\left(\begin{array}{c}n\\ 2i\end{array}\right)}^2=\sum _{0\le k\le n,kは偶数}{\left(\begin{array}{c}n\\ k\end{array}\right)}^2=\begin{array}{r}\{\begin{array}{l}\frac{1}{2}\{\left(\begin{array}{c}2n\\ n\end{array}\right)+(-1{)}^{\frac{n}{2}}\left(\begin{array}{c}n\\ \frac{n}{2}\end{array}\right)\}(nは偶数)\\ \frac{1}{2}\left(\begin{array}{c}2n\\ n\end{array}\right)(nは奇数)\end{array}\end{array}$$

フィボナッチ型

漸化式$a_{n+2}=a_{n+1}+x{a}_n$が成立
$$\begin{gathered} \sum _{k=0}^n{x}^k\left(\begin{array}{c}n-k\\ k\end{array}\right)=\frac{{\left(\frac{1+\sqrt{1+4x}}{2}\right)}^{n+1}-{\left(\frac{1-\sqrt{1+4x}}{2}\right)}^{n+1}}{\sqrt{1+4x}}(x\ne -\frac{1}{4}) \\ \sum _{k=0}^n\left(\begin{array}{c}n-k\\ k\end{array}\right)=F_{n+1} \\ \sum _{k=0}^n{(-\frac{1}{4})}^k\left(\begin{array}{c}n-k\\ k\end{array}\right)=\frac{n+1}{2^n} \end{gathered}$$

多変数型

ここでのΣは，$k_1+\dots +k_m=n$をみたすすべての非負整数の組$(k_1,\dots ,k_m)$について和を取る

多項定理
$$\begin{gathered} \sum _{k_1+\dots +k_m=n}{x}_1^{k_1}{x}_2^{k_2}\dots x_m^{k_m}\left(\begin{array}{c}n\\ k_1,k_2,\dots ,k_m\end{array}\right)=(x_1+x_2+\dots +x_m{)}^n \\ \sum _{k_1+\dots +k_m=n}\left(\begin{array}{c}n\\ k_1,k_2,\dots ,k_m\end{array}\right)=m^n \end{gathered}$$

恒等式$((x+1{)}^n{)}^m=(x+1{)}^{mn}$の$x^n$の係数比較 or $(m-1)n\times n$の最短経路の数え上げ
$$\sum _{k_1+\dots +k_m=n}\left(\begin{array}{c}n\\ k_1\end{array}\right)\left(\begin{array}{c}n\\ k_2\end{array}\right)\dots \left(\begin{array}{c}n\\ k_m\end{array}\right)=\left(\begin{array}{c}mn\\ n\end{array}\right)$$

ディクソンの等式

$$\begin{gathered} \sum _{k=-a}^a(-1{)}^k\left(\begin{array}{c}a+b\\ a+k\end{array}\right)\left(\begin{array}{c}b+c\\ b+k\end{array}\right)\left(\begin{array}{c}c+a\\ c+k\end{array}\right)=\frac{(a+b+c)!}{a!b!c!} \\ \sum _{k=-n}^n(-1{)}^k{\left(\begin{array}{c}2n\\ n+k\end{array}\right)}^3=\frac{(3n)!}{(n!{)}^3} \end{gathered}$$

証明: $x=c+a,m=b-a,r=a$として，両辺を$x$の多項式と考えると，両辺は$m+2r$個の根$x=-m-r,\dots ,r-1$をもつ$m+2r$次式で，さらに$x=r$で一致する．

階乗冪・和差分学

$n\ge s$とする．

変形すれば二項定理
$$\begin{gathered} \sum _{k=0}^n{k}^{\underset{―}{s}}{x}^k\left(\begin{array}{c}n\\ k\end{array}\right)=n^{\underset{―}{s}}{x}^s(1+x{)}^{n-s} \\ \sum _{k=0}^n{k}^{\underset{―}{s}}(-1{)}^k\left(\begin{array}{c}n\\ k\end{array}\right)=0 \\ \sum _{k=0}^n{k}^{\underset{―}{s}}\left(\begin{array}{c}n\\ k\end{array}\right)=n^{\underset{―}{s}}\cdot 2^{n-s} \end{gathered}$$

任意の多項式は下降階乗冪の和で表せるので
任意の$n$次以下の多項式$P(x)$に対し，
$$\sum _{k=0}^n(-1{)}^{k}P(k)\left(\begin{array}{c}n\\ k\end{array}\right)=0$$

差分法での離散マクローリン展開
自然数に対して定義される任意の関数$f(n)$に対し，
$$f(n)=\sum _{k=0}^n{\mathrm{\Delta }}^{k}f(0)\left(\begin{array}{c}n\\ k\end{array}\right)$$

その他

関係式$\left(\begin{array}{c}k\\ s\end{array}\right)=\left(\begin{array}{c}k+1\\ s+1\end{array}\right)-\left(\begin{array}{c}k\\ s+1\end{array}\right)$の利用
$$\sum _{k=s}^n\left(\begin{array}{c}k\\ s\end{array}\right)=\left(\begin{array}{c}n+1\\ s+1\end{array}\right)$$

異なる$n$個のものから$s$個以上選んでさらにそこから$s$個選ぶ場合の数
$$\sum _{k=s}^n\left(\begin{array}{c}n\\ k\end{array}\right)\left(\begin{array}{c}k\\ s\end{array}\right)=2^{n-s}\left(\begin{array}{c}n\\ s\end{array}\right)$$

数学的帰納法
$$\sum _{k=0}^s(-1{)}^k\left(\begin{array}{c}n\\ k\end{array}\right)=(-1{)}^s\left(\begin{array}{c}n-1\\ s\end{array}\right)$$

無限級数

ニュートンの二項定理
実数に拡張した二項係数$\left(\begin{array}{c}r\\ k\end{array}\right):=\frac{r^{\underset{―}{k}}}{k!}$に対して，
$$\sum _{k=0}^{\mathrm{\infty }}{x}^{r-k}{y}^k\left(\begin{array}{c}r\\ k\end{array}\right)=(x+y{)}^r(|x|>|y|,(x,y)\in {\mathbb{R}}^2)$$