二項係数の和の計算 典型問題

数列二項係数


二項係数がらみの和の計算でよく出てくる以下の式の証明方法を解説します。

(1) \(\displaystyle \sum_{k=0}^{n}\,{}_n{\rm{C}}_k=2^n \\ \)

(2) \(\displaystyle \sum_{k=0}^{n}\,(-1)^k \cdot {}_n{\rm{C}}_k=0 \\ \)

(3) \(\displaystyle \sum_{k=0}^{n}\, k\cdot{}_n{\rm{C}}_k= n\cdot 2^{n-1} \\ \)

(4) \(\displaystyle \sum_{k=0}^{n}\,\dfrac{{}_n{\rm{C}}_k}{k+1}=\dfrac{2^{n+1}-1}{n+1} \\ \)

関連:二項係数 \({}_n{\rm{C}}_k\) の公式については 二項係数の公式 をご覧ください。

二項定理を用いた証明の方針

冒頭の式を証明するためには, 二項定理を利用します。

二項定理
\((a+b)^n =\displaystyle \sum_{k=0}^{n}\,{}_n{\rm{C}}_k \,a^{n-k}\,b^k\)
特に, \(a=1,\,b=x\) とおくと,
\((1+x)^n =\displaystyle \sum_{k=0}^{n}\,{}_n{\rm{C}}_k\,x^k\)

方針
・ (1), (2) の証明
二項定理の式の \(x\) に \(1\) や \(-1\) などの値を代入する

・ (3), (4) の証明
二項定理の式を微分, 積分する

(1)の証明

\(\displaystyle \sum_{k=0}^{n}\,{}_n{\rm{C}}_k=2^n\) の証明

二項定理により,
\(\displaystyle \sum_{k=0}^{n}\,{}_n{\rm{C}}_k\,x^k = (1+x)^n\)
この式で, \(x=1\) とおくと,
\(\displaystyle \sum_{k=0}^{n}\,{}_n{\rm{C}}_k=2^n\) (終)

(2)の証明

\(\displaystyle \sum_{k=0}^{n}\,(-1)^k \cdot {}_n{\rm{C}}_k=0 \) の証明

二項定理により,
\(\displaystyle \sum_{k=0}^{n}\,{}_n{\rm{C}}_k\,x^k=(1+x)^n \)
この式で, \(x=-1\) とおくと,
\(\displaystyle \sum_{k=0}^{n}\,{}_n{\rm{C}}_k\,(-1)^k =0\) (終)

(3)の証明

\(\displaystyle \sum_{k=0}^{n}\, k\cdot{}_n{\rm{C}}_k= n\cdot 2^{n-1} \) の証明

二項定理により,
\(\displaystyle \sum_{k=0}^{n}\,{}_n{\rm{C}}_k\,x^k=(1+x)^n \)
両辺を \(x\) で微分すると,
\(\displaystyle \sum_{k=0}^n k\cdot{}_n{\rm{C}}_k\,x^{k-1} = n(1+x)^{n-1}\)
この式で, \(x=1\)とおくと,
\(\displaystyle \sum_{k=0}^{n}\, k\cdot{}_n{\rm{C}}_k= n\cdot 2^{n-1} \) (終)

(4)の証明

\(\displaystyle \sum_{k=0}^{n}\,\dfrac{{}_n{\rm{C}}_k}{k+1}=\dfrac{2^{n+1}-1}{n+1} \) の証明

二項定理により,
\(\displaystyle \sum_{k=0}^{n}\,{}_n{\rm{C}}_k\,x^k=(1+x)^n \)
両辺を \(0\) から \(1\) まで定積分する。
左辺の積分
\(\displaystyle\int_0^1 ({}_n{\rm{C}}_0 +{}_n{\rm{C}}_1 x +{}_n{\rm{C}}_2 x^2 +\cdots +{}_n{\rm{C}}_n x^n) \,dx \\
=\left[{}_n{\rm{C}}_0 x + {}_n{\rm{C}}_1 \dfrac{x^2}{2}+{}_n{\rm{C}}_2 \dfrac{x^3}{3}+ \cdots + {}_n{\rm{C}}_n \dfrac{x^{n+1}}{n+1}\right]_0^1 \\
={}_n{\rm{C}}_0 + {}_n{\rm{C}}_1 \dfrac{1}{2} +{}_n{\rm{C}}_2 \dfrac{1}{3} + \cdots +{}_n{\rm{C}}_n \dfrac{1}{n+1} \\
=\displaystyle\sum_{k=0}^n \dfrac{{}_n{\rm{C}}_k}{k+1} \\ \)

右辺の積分
\(\displaystyle \int_0^1 (1+x)^n \,dx\\
=\displaystyle \left[\dfrac{(1+x)^{n+1}}{n+1}\right]_0^1 \\
=\displaystyle \dfrac{2^{n+1}-1}{n+1}\)

したがって,
\(\displaystyle \sum_{k=0}^{n}\,\dfrac{{}_n{\rm{C}}_k}{k+1}=\dfrac{2^{n+1}-1}{n+1} \) (終)