二項係数の和と数え上げ

569

はじめに

ここでは, 二項係数に関する次の等式を, 組合せ論的な方法を用いて証明していきます.

$\sum_{k = 0}^{⌊ n / 2 ⌋} k (\binom{n - k}{k}) = \frac{n L_{n} - F_{n}}{5}$

ここで, $(\binom{m}{n})$ は $m$ 個から $n$ 個を選ぶ組合せの数（二項係数）, $⌊ x ⌋$ は $x$ 以下最大の整数, $F_{n}$ は $n$ 番目のフィボナッチ数, $L_{n}$ は $n$ 番目のリュカ数を表します.

これに似た有名な等式として

$\sum_{k = 0}^{⌊ n / 2 ⌋} (\binom{n - k}{k}) = F_{n + 1}$

がありますが, 上の等式は下の等式の証明を出発点として導出することができます.

方針や補題について

まず, 次の組合せについての補題を考えます.

黒と白のいずれかで塗られた合計 $n (\geq 1)$ 個の玉を, 以下の「条件１」を満たすように横一列に並べる方法は $F_{n + 1}$ 通りある. ただし, 同じ色の玉どうしは区別しない.

「条件１」
・黒玉の右隣には白玉がある.

たとえば,（白, 黒, 白）や（黒, 白, 黒, 白, 白）のように並べたものは「条件１」を満たしますが,（白, 黒）や（黒, 黒, 白）などは「条件１」を満たしません.

$n$ 個の玉について, あり得る並べ方の総数を $a_{n}$ とする. $n + 2$ 個の玉が「条件１」を満たすとき, 最も左にある玉の色が

・白ならば, 残りの $n + 1$ 個の玉が「条件１」を満たす.
・黒ならば, その右隣に白玉があり, 残りの $n$ 個の玉が「条件１」を満たす.

よって, 並べ方の総数について, $a_{n + 2} = a_{n + 1} + a_{n}$ が成り立つ. また, 実際に並べてみることで $a_{1} = 1, a_{2} = 2$ がわかるから, $a_{n} = F_{n + 1}$ を得る（初項の決め方が $F_{n}$ の定義よりも１項分ずれているから）.

ここで, $a_{n}$ を別の方法で求めてみます. $n$ 個の玉のうち黒玉の個数を $k$ とすると, 白玉の個数は $n - k$ です. これらが「条件１」を満たすためには２つの白玉の間あるいは左端に黒玉を配置すればよく, その方法は $(\binom{n - k}{k})$ 通りあります. また, 黒玉が連続しないための $k$ の範囲は $0 \leq k \leq ⌊ n / 2 ⌋$ なので, この範囲に渡る $k$ について足し合わせれば
$a_{n} = \sum_{k = 0}^{⌊ n / 2 ⌋} (\binom{n - k}{k})$
が成り立ちます. $n = 0$ のときは $(\binom{0}{0}) = 1$ と約束すれば, 以上の議論から次の結果を得ます.

すべての非負整数 $n$ に対して次が成り立つ.
$\sum_{k = 0}^{⌊ n / 2 ⌋} (\binom{n - k}{k}) = F_{n + 1}$

二項係数の和がフィボナッチ数になるなんて、とても面白い性質です！

次の補題は数学的帰納法を用いることで示されます.

数列 $(a_{n})_{n \geq 0}$ と $(b_{n})_{n \geq 0}$ が $a_{n + 2} = a_{n + 1} + a_{n} + b_{n}$ を満たすならば, $n \geq 2$ に対して次が成り立つ.
$a_{n} = F_{n} a_{1} + F_{n - 1} a_{0} + \sum_{k = 0}^{n - 1} F_{n - 1 - k} b_{k}$

最後に, 玉の並べ方について新たな条件を導入し, それを満たす並べ方の総数について次が成り立つことを示します.

黒, 白, 赤のいずれかで塗られた $n (\geq 1)$ 個の玉を, 以下の「条件２」を満たすように横一列に並べる方法は $\frac{n L_{n} - F_{n}}{5}$ 通りある. ただし, 同じ色の玉どうしは区別しない.

「条件２」
・黒玉の右隣には白玉がある.
・赤玉がちょうど $1$ 個あり, その右隣には白玉がある.

たとえば,（赤, 白, 白）や（黒, 白, 赤, 白）などは「条件２」を満たしますが,（赤, 黒, 白）,（黒, 白, 白）,（赤, 白, 赤, 白）などは「条件２」を満たしません.

$n$ 個の玉について,「条件２」を満たす並べ方の総数を $a_{n}$ とする. $n + 2$ 個の玉が「条件２」を満たすとき, 最も左にある玉の色が

・白ならば, 残りの $n + 1$ 個が「条件２」を満たす.
・黒ならば, その右隣に白玉があり, 残りの $n$ 個が「条件２」を満たす.
・赤ならば, その右隣に白玉があり, 残りの $n$ 個が「条件１」を満たす.

よって, 補題１より $a_{n + 2} = a_{n + 1} + a_{n} + F_{n + 1}$ が成り立つ. 実際に並べてみると $a_{1} = 0, a_{2} = 1$ であるから, これらと漸化式を合わせて $a_{0} = 0$ と定めることができる. 補題３を用いて漸化式を変形すると, $n \geq 2$ に対して
$\begin{aligned} a_{n} & = F_{n} a_{1} + F_{n - 1} a_{0} + \sum_{k = 0}^{n - 1} F_{n - 1 - k} F_{k + 1} \\ = \sum_{k = 0}^{n} F_{n - k} F_{k} (∵ F_{n} F_{0} = 0) \\ = \sum_{k = 0}^{n} \frac{ϕ^{n - k} - \bar{ϕ}^{n - k}}{\sqrt{5}} \cdot \frac{ϕ^{k} - \bar{ϕ}^{k}}{\sqrt{5}} = \frac{1}{5} \sum_{k = 0}^{n} (ϕ^{n} + \bar{ϕ}^{n} - ϕ^{n - k} \bar{ϕ}^{k} - ϕ^{k} \bar{ϕ}^{n - k}) \\ = \frac{1}{5} (n + 1) L_{n} - \frac{2}{5} \frac{ϕ^{n + 1} - \bar{ϕ}^{n + 1}}{ϕ - \bar{ϕ}} = \frac{(n + 1) L_{n} - 2 F_{n + 1}}{5} = \frac{n L_{n} - F_{n}}{5} \end{aligned}$
が成り立つ. また, 主張は $n = 1$ のときも成り立つ.

ただし, $ϕ = \frac{1 + \sqrt{5}}{2}, \bar{ϕ} = \frac{1 - \sqrt{5}}{2}$ であり, フィボナッチ数やリュカ数に関する公式
$F_{n} = \frac{ϕ^{n} - \bar{ϕ}^{n}}{\sqrt{5}}, L_{n} = ϕ^{n} + \bar{ϕ}^{n}, L_{n} = F_{n + 1} + F_{n - 1}$
などを用いました.

目標の等式の証明

すべての非負整数 $n$ に対して次が成り立つ.
$\sum_{k = 0}^{⌊ n / 2 ⌋} k (\binom{n - k}{k}) = \frac{n L_{n} - F_{n}}{5}$

$n (\geq 1)$ 個の玉のうち黒玉と赤玉の個数の合計を $k$ とすると, 白玉の個数は $n - k$ である.「条件２」を満たすようにこれらを並べるには, ２つの白玉の間あるいは左端に白でない玉を配置すればよい. そのようにして白でない玉を置く場所の選び方は $(\binom{n - k}{k})$ 通りあり, そこからさらに赤玉の場所を選ぶ方法は $k$ 通りある. $0 \leq k \leq ⌊ n / 2 ⌋$ に気を付けて足し合わせれば, 並べ方の総数は
$\sum_{k = 0}^{⌊ n / 2 ⌋} k (\binom{n - k}{k})$
であるから, 補題４より $n \geq 1$ に対して主張を得る. また, 主張の等式は $n = 0$ のときも成り立つ.

一般化など

以上の方法において赤玉の個数を $m$ とすれば, 次の性質を示すことができます.

すべての非負整数 $m, n$ に対して
$S_{n}^{(m)} = \sum_{k = 0}^{⌊ n / 2 ⌋} (\binom{n - k}{k}) (\binom{k}{m})$
とおくと, 次が成り立つ.
$S_{n + 2}^{(m + 1)} = S_{n + 1}^{(m + 1)} + S_{n}^{(m + 1)} + S_{n}^{(m)}$

ただし, $k < m$ のときは $(\binom{k}{m}) = 0$ と定義します.
非常に大変な計算になりますが, 具体的に $m = 2, 3, 4$ について求めてみると次のようになります. 実際に $n$ を代入してみると成り立っていることが確認できると思います.

すべての非負整数 $n$ に対して以下が成り立つ.
$\begin{aligned} \sum_{k = 0}^{⌊ n / 2 ⌋} (\binom{n - k}{k}) (\binom{k}{2}) = \frac{5 (n - 1) (n L_{n} - F_{n} - n F_{n + 1}) - n L_{n} + F_{n}}{50} \\ \sum_{k = 0}^{⌊ n / 2 ⌋} (\binom{n - k}{k}) (\binom{k}{3}) = \frac{(n - 1) (n - 3) {3 (n L_{n} - F_{n}) - 5 (n + 1) F_{n}}}{300} \\ \sum_{k = 0}^{⌊ n / 2 ⌋} (\binom{n - k}{k}) (\binom{k}{4}) = \frac{(- 10 F_{n} + 5 L_{n}) n^{4} + (70 F_{n} - 40 L_{n}) n^{3} + (- 80 F_{n} + 85 L_{n}) n^{2} + (- 160 F_{n} - 38 L_{n}) n + 168 F_{n}}{3000} \end{aligned}$