数学II / 式と証明

二項係数の平方和(係数比較)

実戦編式と証明二項定理組合せ係数比較単元横断

問題

$n$ を自然数とする。 $k = 0 \sum n (k n)^{2} = (n 2 n)$ が成り立つことを示せ。ここで $(k n)$ は二項係数 $_{n} C_{k}$ を表す。

ヒントを見る

$(1 + x)^{2 n}$ を $(1 + x)^{n}$ の積に分け、両辺で $x^{n}$ の係数を比べる。左辺は畳み込み $\sum_{k} (k n) (n - k n)$ 。対称性 $(n - k n) = (k n)$ 。

解答・解説

方針

$(1 + x)^{2 n} = (1 + x)^{n} \cdot (1 + x)^{n}$ とみて、両辺の $x^{n}$ の係数を二項定理で書き出し、 $(n - k n) = (k n)$ を使う。

解答

⓪ 発想 — どう考え始めるか。 二項係数の和の等式は、「同じものを2通りに数える」か「同じ式の係数を2通りに読む」かのどちらかで示すのが自然だ。

ここでは式で攻める。 $(1 + x)^{2 n}$ は $(1 + x)^{n} \cdot (1 + x)^{n}$ と全く同じ式。だから展開したときの係数もすべて一致する。

積の側で $x^{n}$ を作るには、前の因子から $x^{k}$ 、後ろから $x^{n - k}$ を取ればよい。その総和に対称性 $(n - k n) = (k n)$ を使うと、平方和が現れる。

定理二項定理

(1 + x)^{m} = j = 0 \sum m (j m) x^{j}

。対称性

(n - k n) = (k n)

① 同じ式を $2$ 通りに。 $(1 + x)^{2 n} = (1 + x)^{n} \cdot (1 + x)^{n} .$ ② 右辺の $x^{n}$ の係数。 二項定理より $(1 + x)^{2 n}$ の $x^{n}$ の係数は $(n 2 n)$ 。

③ 左辺の $x^{n}$ の係数。 $(1 + x)^{n} = \sum_{i} (i n) x^{i}$ どうしの積で $x^{n}$ を作るには、一方から $x^{k}$ 、他方から $x^{n - k}$ 。よって係数は $k = 0 \sum n (k n) (n - k n) = k = 0 \sum n (k n)^{2} (∵ (n - k n) = (k n)) .$ ④ 比較。 同じ多項式の同じ次数の係数だから等しく $k = 0 \sum n (k n)^{2} = (n 2 n) .$

まとめ $(1 + x)^{2 n} = {(1 + x)^{n}}^{2}$ の $x^{n}$ の係数を両側から数えると、平方和 $= (n 2 n)$ 。二項定理と組合せ(係数比較)の融合。「積の係数=畳み込み」を使うのが核心。

発展 — 一歩先へ。 一般には $\sum_{k} (k m) (p - k n) = (p m + n)$ (ヴァンデルモンドの畳み込み)が成り立つ。本問は $m = n = p$ の場合だ。「2つのグループから合わせて $p$ 人選ぶ」を左のグループの人数で場合分けした式で、係数比較 $(1 + x)^{m} (1 + x)^{n} = (1 + x)^{m + n}$ とも対応する。

答

$(1 + x)^{n} (1 + x)^{n} = (1 + x)^{2 n}$ の両辺で $x^{n}$ の係数を比べる。左辺の $x^{n}$ の係数は $\sum_{k} (k n) (n - k n) = \sum_{k} (k n)^{2}$ 、右辺は $(n 2 n)$ 。

別解

別解 — 「男女 $n$ 人ずつから $n$ 人選ぶ」と読む(得意な人向けの高い視点)。 右辺 $(n 2 n)$ は、男 $n$ 人・女 $n$ 人の計 $2 n$ 人から $n$ 人選ぶ場合の数だ。

同じ選び方を、女子の人数 $k$ で場合分けして数え直す。女子を $k$ 人選ぶと男子は $n - k$ 人で、その選び方は

$(k n) (n - k n) = (k n) (k n) = (k n)^{2}$

通り( $(n - k n) = (k n)$ を使った)。 $k = 0, 1, \dots, n$ について足せば左辺になる。

同じ集合を2通りに数えただけで、式変形は一度もしていない。係数比較(本解)で $x^{k}$ と $x^{n - k}$ が分担していたのは、この「女子 $k$ 人・男子 $n - k$ 人」の分担そのものである。

ポイント

平方和は「 $2$ 多項式の積の係数」を疑う。
$(1 + x)^{2 n} = {(1 + x)^{n}}^{2}$ の $x^{n}$ を両側で数える。
対称性 $(n - k n) = (k n)$ で平方和に。

よくある間違い

対称性 $(n - k n) = (k n)$ を使う一言を飛ばし、畳み込みの和が平方和にならない。
積の $x^{n}$ の係数を「 $x^{k}$ どうしの積」で数えてしまう(前から $x^{k}$ 、後ろから $x^{n - k}$ と、べきの合計が $n$ になる組を拾う)。
小さい $n$ で検算しない( $n = 2$ なら $1 + 4 + 1 = 6 = (2 4)$ 。合わなければ添字のミス)。