k,\ m,\ n$を自然数とし,\ $n≧ k$とする.
(1)\ \ 以下の等式を証明せよ.
[1]\ \ $kC nk=nC{n-1}{k-1}$
[2]\ \ $C{n+1}{k}=C nk+C{n}{k-1}$
[3]\ \ $C n0+C n1+C n2+･･････+C{n}{n-1}+C nn=2^n$
(2)\ \ $C{2^m}{k}\ (k=1,\ 2,\ ･･･,\ 2^m-1)$は偶数であることを示せ.
(3)\ \ $C{2^m-1}{k}\ (k=0,\ 1,\ 2,\ ･･･,\ 2^m-1)$は奇数であることを示せ.
(4)\ \ $C{2^m}{k}\ (k=1,\ 2,\ ･･･,\ 2^m-1)$の最大公約数が2であることを示せ. \\
二項係数の偶奇性とシェルピンスキーのギャスケット
[1]}\ \ 前項でも証明した等式である.\ 階乗で表して左辺と右辺が一致することを示せばよいのであった.
[2]}\ \ 複雑な右辺を階乗で表して左辺を目指せばよいが,\ 階乗の式変形に慣れている必要がある.
[3]}\ \ 二項係数の和の等式は二項定理(数II})を用いて証明する}のが基本である.
\ \ (1+x)^n\,を二項展開し,\ 両辺のxに適切な値を代入する.
$k$がもつ素因数2の個数は多くても$m-1$個}である.
$よって,\ C{2^m}{k}$は素因数2を少なくとも1個もつ.
∴$ $C{2^m}{k}\ (k=1,\ 2,\ ･･･,\ 2^m-1)は偶数である.}$}
(1)の等式[1]を利用し,\ 両辺の素因数2の個数に着目する.}$は偶数であるから,\ 2整数$C{2^m-1}{k},\ C{2^m-1}{k-1}$の偶奇は一致}する.
ここで,\ $C{2^m-1}{0}=1$は奇数}である.
よって,\ 帰納的に$C{2^m-1}{k}\ (k=0,\ 1,\ 2,\ ･･･,\ 2^m-1)}$は奇数}である.
(1)の等式[2]および(2)を利用する.
和が偶数ということは,\ (偶数)+(偶数)または(奇数)+(奇数)ということである.
よって,\,C{2^m-1}{0}\,とC{2^m-1}{1},\ \ C{2^m-1}{1}\,とC{2^m-1}{2},\ \ C{2^m-1}{2}\,とC{2^m-1}{3},\ ･･･\ はそれぞれ偶奇が一致する.
C{2^m-1}{0}\,が奇数なので\,C{2^m-1}{1}\,も奇数であり,\ 後はこれを繰り返すことですべて奇数であるとわかる.
厳密には数学的帰納法(数B})によるが,\ ほぼ明らかな場合は「帰納的に」と記述しておけばよい. \\{奇素数が公約数となることはない.C{2^m}{2^m-1}$がすべて4の倍数であると仮定する.
このとき,\ $C{2^m}{1}+C{2^m}{2}+･･････+C{2^m}{2^m-1}$も4の倍数となる.
これは,\ $2(2^{2^m-1}-1)$が4の倍数ではないことに矛盾する. $(\,\because\ \ 2^{2^m-1}-1は奇数\,)$
よって,\ $C{2^m}{1},\ C{2^m}{2},\ ･･･,\ C{2^m}{2^m-1}$のうち,\ 少なくとも1つは4の倍数ではない.}
∴$ $C{2^m}{k}\ (k=1,\ 2,\ ･･･,\ 2^m-1)}$の最大公約数は2である. \\
(2)で2を公約数にもつことが確定しているので,\ 後は2が\dot{最}\dot{大}公約数であることの証明である.
奇素数を公約数にもたないことおよび4を公約数にもたないことを示せばよい.}
つまり,\ 少なくとも1個の二項係数が奇数の素因数をもたないことと4の倍数でないこと}を示す.
ここでは,\ 二項係数の公約数の考察で役立つ2つの発想を習得してほしい.
1つは単純で,\ 条件を満たす二項係数を具体的に1つ示す}ことである.
奇数の素因数をもたない二項係数はすぐに見つけ出すことができる.
一方,\ 4の倍数ではない二項係数は簡単には見つからないので,\ もう1つの発想を利用する.
二項係数の和を考える}ことである.
すべての二項係数が4を公約数にもつとき,\ その和は4の倍数}となる.
二項定理により二項係数の和が2×(奇数)とわかるから,\ これは矛盾である(背理法).
参考までに,\ 4の倍数ではない二項係数を1つ挙げる別解も示しておく.
分子の(2^m)!\,がもつ素因数2の個数は (階乗の素因数の個数の求め方は別項で解説済)
同様にすると,\ (2^{m-1})!\,がもつ素因数2の個数は2^{m-1}-1個であるとわかる.
よって,\ 分母\{(2^{m-1})!\}^2\,がもつ素因数2の個数は(2^{m-1}-1)×2=2^m-2個}である.
分子の素因数2の個数が分母よりも1個だけ多いから,\ C{2^{m{2^{m-1\,は偶数かつ4の倍数ではない.
なぜ\,C{2^{m{2^{m-1\,という数を考えたかという理由も重要である.
分子(2^m)!\,は多数の素因数2をもつ.
よって,\ 4の倍数でなくなるためには,\ 分母にも多数の素因数2がなければならない.
2^m\,未満で素因数2が多い数を考えると,\ 2^{m-1}\,が思い浮かぶわけである.
二項係数の対称性を考慮すると,\ 2^m}{2}=2^{m-1}\,より大きい数を考える必要はない.
さて,\ 二項係数に関する問題は,\ 背景にパスカルの三角形があることが少なくない.
最上段と両端は1で,\ 各位置の数が左上の数と右上の数の和となるように並べたものである.
このパスカルの三角形は,\ 二項係数を並べたものと一致する.
各位置の数は左上の数と右上の数の和なので,\ 例えば$C42+C43=C53$などが成り立つ.
この等式は,\ パスカルの三角形という観点から見るとほぼ自明だったわけである.
パスカルの三角形において,\ 奇数を●,\ 偶数を○に置き換えてみる.
すると,\ シェルピンスキーのギャスケットと呼ばれる図形が現れる.
これは,\ フラクタル図形(自己相似的な構造をもつ図形)の一種である.
シェルピンスキーのギャスケットは,\ 以下のようにして作図できる.
[1]\ \ 黒い正三角形を用意し,\ 各辺の中点を結んでできる正三角形の内部を白塗りする.
[2]\ \ 残りのすべての黒い正三角形に対して,\ [1]を無限に繰り返す.
シェルピンスキーのギャスケットにより, 二項係数の偶奇性の問題を視覚的に理解できる.
以下,\ 一番上は$C00$なので,\ これを0段目と数える.
また,\ 各段の一番左は$C n0$であって$C n1$ではないことにも注意してほしい.
(2)は,\ $2^m=2,\ 4,\ 8,\ 16,\ ･･･}$段目が両端以外は○であることの証明である.
(3)は,\ $2^m-1=1,\ 3,\ 7,\ 15,\ 31,\ ･･･}$段目がすべて●であることの証明である.
パスカルの三角形の各位置の数は,\ 左上の数と右上の数の和であった.
よって, 丸3個の逆三角形の配置は以下の4パターンに限られる.
これを元に,\ (3)の解答を視覚的に理解しよう.\ 例として,\ 15段目と16段目に着目する.
(2)より16段目は両端以外は○で,\ また,\ $C{15}{0}=1$より,\ 15段目の一番左は●である.
一番左が●で下すべて○なので,\ Bより,\ 15段目には必然的に●が並ぶわけである.
