【５】二項係数の偶奇性（１）

シェルピンスキーの三角形の数学的な背景について調べてみよう．

（Ｑ）（ａ＋ｂ）^nの二項展開の係数は，ｎが２^k−１の形であるとき，そのときに限りすべて奇数となることを証明せよ．

（Ａ）（ａ＋ｂ），（ａ＋ｂ）^2，・・・，（ａ＋ｂ）^n-1に対して成り立っていると仮定して，（ａ＋ｂ）^nに対しても成り立つことを証明する．

　両端の１を除くｎ−１個の二項係数は

　　ｎ／１＝ｎ，ｎ（ｎ−１）／１・２，・・・，ｎ（ｎ−１）・・・１／１・２・・・（ｎ−１）＝ｎ

　これらがすべて奇数であるための必要十分条件は

［１］両端のｎが奇数であること

［２］残りの数の分母，分子から奇数を取り去って作られる数が奇数であることである．

　ｎ＝２ｍ＋１とおけば，これらの数は

　　ｍ／１＝ｍ，ｍ（ｍ−１）／１・２，・・・，ｍ（ｍ−１）・・・１／１・２・・・（ｍ−１）＝ｍ

で表される．ｍ＜ｎであるから，このｍ−１個の数はｍが２^k-1−１の形であるとき，そのときに限りすべて奇数となる．

　　ｎ＝２ｍ＋１＝２（２^k-1−１）＋１＝２^k−１

より，ＱＥＤ．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　ｎ＝２^k−１，すなわち，１，３，８，１５，３１，・・・５，のとき，nＣmは奇数である段が出来あがる．すると，

　　n+1Ｃm＝nＣm-1＋nＣm

により，ｎ＝２^kのとき，nＣmは偶数となる．

詳細に調べると，

［１］ｎ＝ｐのとき，nＣmはｐの倍数である

　両端nＣ0＝nＣn＝１ですから，両端以外のnＣm（１≦ｍ≦ｎ−１）について考えます．ｎ＝ｐのとき

　　pＣm＝ｐ！／ｍ！（ｐ−ｍ）！

１≦ｍ≦ｐ−１，１≦ｐ−ｍ≦ｐ−１より，分母は素因数ｐを含んでいない．よって，pＣmはｐの倍数である．

［２］ｎ＝２^kのとき，nＣmは偶数である

　　（ａ＋ｂ）^2＝ａ^2＋｛係数が偶数の項｝＋ｂ^2

　　｛（ａ＋ｂ）^2｝^2＝ａ^4＋｛係数が偶数の項｝＋ｂ^4

　　｛（ａ＋ｂ）^4｝^2＝ａ^8＋｛係数が偶数の項｝＋ｂ^8，・・・

数学的帰納法より，nＣmは偶数である

［３］ｎ＝２^k−１のとき，nＣmは奇数である

　［２］より，n+1Ｃmは偶数である．

　　n+1Ｃm＝nＣm-1＋nＣm

　　１＋nＣ1＝偶数→nＣ1は奇数

　　nＣ1＋nＣ2＝偶数→nＣ2は奇数，・・・

よって，nＣmは奇数である．

　さらに，nＣmがすべては奇数になるのは，ｎ＝２^k−１のときに限るというのが当該の命題です．実際，他の行には偶数があるのですが，

［４］ｎ＝２^kのとき，両端以外のnＣm，２^k−１個はすべて偶数である

［５］ｎ＝２^k＋１のとき，真ん中のnＣm，２^k−２個はすべて偶数である

［６］ｎ＝２^k＋２のとき，真ん中のnＣm，２^k−３個はすべて偶数である

・・・・・・・・・・・・・・・

［７］ｎ＝２^k+1−２＝２^k＋２^k−２のとき，真ん中のnＣm，２^k−（２^k−１）＝１個はすべて偶数である

［８］nＣmがすべては奇数になるのは，ｎ＝２^k−１のときだけ

ということになります．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

まとめると，nＣm（ｍ＝０〜ｎ）がすべては奇数になるのは，ｎ＝２^k−１のときに限る．さらに，ｋ＞１に対してnＣm（ｍ＝１〜ｎ−１）がｋで割り切れるための必要十分条件は，ｋが素数であって，ｎ＝ｋ^mの形に書けるときに限る．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝