二項係数の和

方針

解答

⓪ 発想 — どう考え始めるか。 二項係数の和は、$(1+x{)}^n$ の展開式に値を代入すると一瞬で出る。

$x=1$ を入れれば全部の和が $2^n$、$x=-1$ を入れれば符号が交代して和が $0$。

証明したい和が、既知の展開式のどの代入で現れるか。それを逆算するのが発想の核だ。

(1) $x=1$ を代入すると、左辺 $(1+1{)}^n=2^n$、右辺 $\sum _{k=0}^n{}_n{\mathrm{C}}_k\cdot 1^k=\sum {}_n{\mathrm{C}}_k$。よって

$${}_n{\mathrm{C}}_0+{}_n{\mathrm{C}}_1+\cdots +{}_n{\mathrm{C}}_n=2^n$$

(2) $x=-1$ を代入すると、左辺 $(1-1{)}^n=0$、右辺 $\sum _{k=0}^n{}_n{\mathrm{C}}_k(-1{)}^k$。よって

$${}_n{\mathrm{C}}_0-{}_n{\mathrm{C}}_1+\cdots +(-1{)}^n{}_n{\mathrm{C}}_n=0$$

$■$

((1)と(2)を足し引きすると、偶数番目の二項係数の和と奇数番目の和がともに $2^{n-1}$ になることも導ける。)

発展 — 一歩先へ。 代入する値を変えるだけで、別の和が次々に生まれる。

$x=2$ を入れれば ${\sum }_{k=0}^n{}_n{\mathrm{C}}_k{2}^k=3^n$、一般に $x=t$ で ${\sum }_{k=0}^n{}_n{\mathrm{C}}_k{t}^k=(1+t{)}^n$。重み $t^k$ の付いた二項係数の和が、$t$ を選ぶだけで手に入る。

さらに $x$ に $1$ の虚数乗根を代入すると、番号がとびとびの二項係数だけを集めた和も取り出せる。$1$ の $m$ 乗根をすべて代入して平均をとると、$m$ 個おきの二項係数の和が残る(1の冪根フィルター)。$(1+x{)}^n$ という $1$ 本の恒等式が、代入値しだいで無数の和を生む母関数なのだ。

別解

別解 — 部分集合を数えて示す(苦手な人向けの数え上げルート)。 代入を使わず、集合の要素の選び方で考える。

$n$ 個のものからいくつか選ぶ選び方は、各要素を「選ぶ・選ばない」の $2$ 通りだから全部で $2^n$ 通り。一方、ちょうど $k$ 個選ぶ選び方は ${}_n{\mathrm{C}}_k$ 通り。$k=0,1,\dots ,n$ で足し合わせれば同じ全体を数えたことになり、$(1)$ が言える。

$(2)$ は「偶数個選ぶ」場合と「奇数個選ぶ」場合が同数であることを示せばよい。要素を $1$ つ決め、それを「入れる・入れない」で切り替えると、偶数個の選び方と奇数個の選び方が過不足なく $1$ 対 $1$ に対応する($n\ge 1$)。だから両者は同数で、差をとった交代和は $0$。

代入(本解)と同じ結論だが、二項係数が「選び方の個数」だという原点に戻ると、等式の意味が見える。本解と同じ答えだ。