◆東京都 小林 祐介 さんからの解答。
【問題１】
二項定理より
nＣ0＋nＣ1＋…＋nＣn-1＋nＣn
＝(１＋１)n
＝２n
【問題１別解】
nＣ0＋nＣ1＋・・＋nＣn-1＋nＣn＝２n・・(1)と仮定する。
［１］ n＝1の時
1Ｃ0＋1Ｃ１＝21
で成り立っている。
［２］ n＝kの時、(1)が成り立っているとすると
n＝k＋1のとき
k+1Ｃ0＋k+1Ｃ1＋…＋k+1Ｃk＋k+1Ｃｋ+1k+1Ｃ0＝kＣ0＝1，
＝k+1Ｃ0＋(kＣ0＋kＣ1)＋…＋(kＣk-1＋kＣk)＋k+1Ｃk+1
k+1Ｃk+1＝kＣk＝1より
k+1Ｃ0＋k+1Ｃ1＋…＋k+1Ｃk＋k+1Ｃｋ+1
＝2(kＣ0＋kＣ1＋…＋kＣk-1＋kＣk)
＝2k+1
で成り立っている。
［１］，［２］より@は全ての自然数ｎについて成り立つ。
【問題２】
問題１と同様に
nＣ0−nＣ1＋…＋(-1)n×nＣn
＝(１−１)n
＝０
【問題２別解】
［１］ n＝1の時
1Ｃ0−1Ｃ1＝０
［２］ n≧2の時
nＣ0−nＣ1＋…＋(-1)n-1nＣn-1＋(-1)nnＣnnＣ0＝n-1Ｃ0＝1，nＣn＝n-1Ｃn-1＝1より
＝nＣ0−(n-1Ｃ0＋n-1Ｃ1)＋…＋(-1)n-1 (n-1Ｃn-2＋n-1Ｃn-1)＋(-1)n nＣn
nＣ0＋nＣ1＋…＋nＣn-1＋nＣn＝0
［１］，［２］より全ての自然数ｎについて成り立つ。
【問題３】
2nＣn
＝2n-1Ｃn＋2n-1Ｃn-1
＝2n-2Ｃn＋2×(2n-2Ｃn-1)＋2n-2Ｃn-2
＝2n-3Ｃn＋3×(2n-3Ｃn-1)＋3×(2n-3Ｃn-2)＋2n-3Ｃn-3
＝…(n回この操作を繰り返す)
| ＝2n-nＣn＋n(2n-nＣn-1)＋ |
n(n-1) 2 | (2n-nＣn-2)＋…＋ |
n(n-1) 2 | (2n-nＣ2)＋n(2n-nＣ1)＋2n-nＣ0 |
＝(nＣ0)2＋(nＣ1)2＋…＋(nＣn)2
この式はパスカルの三角形において
nＣk(k≦n)から2nＣnの項にいたる道筋が
ちょうどnＣk通りあることを示している。
【問題４】
［１］nが奇数の場合、
2nＣn＝nＣ02＋nＣ12＋… ＋nＣn2において
nＣ02＝nＣn2，
nＣ12＝nＣn-12，
…
nＣ(n-1)/22＝nＣ(n+1)/22より
2nＣnは偶数。
［２］nが偶数の場合、
2nＣn＝nＣ02＋nＣ12＋… ＋nＣn2において
nＣ02＝nＣn2，
nＣ12＝nＣn-12，
…
nＣn/2-12＝nＣn/2+12
nＣn/2においてn＝2kとおくと、
nＣn/2＝2kCkとなる。
この2kCkを上の［１］［２］の2nＣnにあてはめると、
もとの2nＣnは有限の整数なのでいつかは偶数の和に分解できる。
よって2nＣnは偶数。
【コメント】
実は元の問題は問題４だけだったのですが、私は他の証明が思いつかなかったので、ヒントとして問題３を追加しました。
問題３の式を使わないで、問題４を証明できるのでしょうか。
◆京都府 sambaGREEN さんからの解答。
【問題４】
2nＣnはｎ個の白石とｎ個の黒石を一列に並べる場合の数です。
この中には白黒反転させた並べ方が必ずペアーで存在します。
●○●●○・・・●○○
○●○○●・・・○●●
というふうに。
したがって，2nＣnは偶数。
◆神奈川県 いわし さんからの解答。
【問題４】
図のような縦横n区画((n+1)本)の格子状の道で、対角線上の頂点AからBへの最短経路の数Nは
N=2nＣnです。
その任意の経路(例えば図の赤い経路)について、ABに関して対称な経路(青い経路)が存在しますから、Nは偶数です。
◆四年寝太郎 さんからの解答。
【問題３】
(x+y)2n = (x+y)n * (x+y)n であり、
| (x+y)2n = |
2n Σ i=0 | 2nＣi * xi* y2n-i |
(x+y)n * (x+y)n
| = |
n Σ i=0 | nＣi * xi* yn-i | * |
n Σ j=0 | nＣj * xj* yn-j |
だから、特にxnynの項の係数について考えると、
左辺の係数は2nＣnであり、
右辺の係数は
|
n Σ i=0 | nＣi * nＣn-i |
| = |
n Σ i=0 | nＣi2 |
【問題４】
2nＣn
= 2n-1Ｃn-1 + 2n-1Ｃn
= 2 * 2n-1Ｃn
2n-1Ｃnは整数だから2nＣnは偶数。
◆東京都 千葉 英伸 さんからの解答。
【問題４】
《別解その１》
問題１より、
nＣ0＋nＣ1＋・・＋nＣn＝２n（偶数）
なので、nＣ0，nＣ1，・・，nＣn のなかで、奇数になるものは偶数個ある。
奇数か偶数かという性質は２乗しても変わらないので、
nＣ02，nＣ12，・・，nＣn2のなかに、奇数になるものはやはり偶数個含まれている。
従って、問題３より、
2nＣn＝nＣ02＋nＣ12＋・・＋nＣn2
も偶数になる。
《別解その２》
素朴に考えて、コンビネーションの定義から、
ｎ≧１であれば、
◆富山県 N.C さんからの解答。
【問題４】
mＣr＝mＣm-rですから、
m=2n-1、r=n-1をあてはめると
2n-1Ｃn-1＝2n-1Ｃn
が導かれます。従って，
2nＣn
＝2n-1Ｃn＋2n-1Ｃn-1
＝2n-1Ｃn＋2n-1Ｃn
＝２2n-1Ｃn
は、偶数となります。
2nＣnは、パスカルの三角形の偶数段目の中央です。
パスカルの三角形は左右対称ですから，中央の項の左斜め上の項
2n-1Ｃn-1と右斜め上の項2n-1Ｃnは一致します。
その他にも、n!を素因数分解したときの２の指数e
（n!=(奇数)×２eとなる数e）は、
| e=[ |
n 2 | ]+[ |
n 4 | ]+[ |
n 8 | ]+... |
となることを用いても証明できると思います。
◆愛知県の高校生 Sparking さんからの解答。
【問題４】
単純に 2n-1Ｃn-1＝2n-1Ｃn
（二項係数の対称性）から
2nＣn
＝2n-1Ｃn-1＋2n-1Ｃn
＝２・（2n-1Ｃn）
（尚二行目の定理はＡさんが自分を含めて２ｎ人の中からｎ人のグループを作らせてもらうときの作り方は
(1)Ａさんがそのグループに入りたかった場合の数
（2n-1人からn-1人を選ぶ）と
(2)Ａさんがそのグループに入りたくなかった場合の数
（2n-1人からｎ人を選ぶ）
との和で表せると説明できる。）
◆静岡県 ヨッシー さんからの解答。
【問題４】
2nＣn
| ＝ |
2n×(2n-1)×・・・×(n+1) n×(n-1)×・・・×１ |
| ＝ |
2n ｎ | × |
(2n-1)×・・・×(n+1) (n-1)×・・・×１ |
| ＝２×2n-1Ｃn-1 |
2n-1Ｃn-1は整数なので、2nＣn は偶数
◆大阪府 河野 進 さんからの解答。
【問題４】
【問題４】の証明には
2nＣn ≡ 0 (mod 2)
を示せば十分だと思います。
そのためには、以前お送りした公式集の様なものの (2.1) とした次の補題（教科書からの丸写しです）を使えば簡単だと思います。
【補題】
p を素数とする。
m, k を負でない整数とし、各々の「p 進法表示」を
aN･･･a0, bN･･･b0 とする
| （正確には、m = |
N Σ i=0 | aipi,k = |
N Σ i=0 | bipi） |
このとき、
| mＣk ≡ |
N Π i=1 | aiＣbi (mod p) |
が成り立つ。
証明は (x+1)m を (Z/pZ)[x] の元と見て展開し
xk の係数を決定することでできます。
この補題で p = 2, m = 2n, k = n としますと、
a0 = 0, ai =bi-1 (i ＞ 0) となります。
j を bi = 1 を満たす i の最小値としますと
（n を正整数とすると、この様な j は存在します）、
aj = 0,
ajＣbj = 0Ｃ1 = 0 となります。
従って、補題より
| 2nＣn ≡ |
N Π i=1 | aiＣbi (mod 2)= 0. |
つまり、2nＣn は偶数です。
◆東京都 小林 祐介 さんからの解答。
【問題４考察】
n，kは自然数とする。
| 2nＣn＝ |
2n×(2n-1)×・・・×(n+1) n! |
2n×(2n−1)×…×(n＋1)に含まれる2の指数をxn，
n!に含まれる2の指数をynとする。
xn+1−yn+1＝xn−yn＋１−α
（n＋1＝2α･β（αは0以上の整数、βは奇数））
x1−y1＝1
これを解いてグラフにしてみると下の図のようになる。
何となくフラクタライズな関係が見えてきそうな気がするのですが。
ただxn−yn＞0を証明するのは難しそうです。
このグラフを見て思ったのですが
nが２kの時、2nＣnは指数2を１つしか持ってないようなのでこんな問題はどうでしょう？
「
は2では割り切れますが、4では割り切れるでしょうか？」
この問題を提案したいと思います。
◆富山県 N.C さんからのコメント。
解答ではなくて済みません。
ちゃちゃを入れます。
東京都の小林 祐介さんの【問題４考察】についてですが、
ｎを２進数で表記したものと、
2nＣnを素因数分解したときの
２の指数Ｘn−Ｙnの関係は、どうなっているのでしょうか。
掲載されているグラフから読み取った限りでは、下記のように
２の指数Ｘn−Ｙnは、ｎの２進表記における１の個数と一致しています。
| ｎ（２進表記） | Ｘn−Ｙn |
|---|---|
| １ | １ |
| １０ | １ |
| １１ | ２ |
| １００ | １ |
| １０１ | ２ |
| １１０ | ２ |
| １１１ | ３ |
| １０００ | １ |
| １００１ | ２ |
| １０１０ | ２ |
| １０１１ | ３ |
| １１００ | ２ |
| １１０１ | ３ |
| １１１０ | ３ |
| １１１１ | ４ |
| １００００ | １ |
◆大阪府 河野 進 さんからの解答。
小林祐介さんの問題に付いて考えましたが、４では割り切れないと思います。
次のように考えました。
i を 2n より小さい正整数としますと、
2n + i の素因数分解に於ける２の指数は i の素因数分解に於ける２の指数に等しいので、
|
2n+1！ 2n！ | の素因数分解に於ける２の指数は |
は４を法として２だと思います。
◆宮城県 アンパンマン さんからの解答。
【問題１】
nＣ0＋nＣ1＋…＋nＣn-1＋nＣn
＝(1+1)n
=２n
【問題２】
nＣ0−nＣ1＋…＋(-1)n-1nＣn-1＋(-1)nnＣn
＝(1-1)n
=0
【問題３】
(1+x)n*(1+x)n=(1+x)2n のxn の係数から
(nＣ0)2＋(nＣ1)2＋・・＋(nＣn)2
＝2nＣn
を証明できます。
【問題４】
2nCn
=nＣ02＋nＣ12＋・・＋nＣn2
●case1 n=奇数
2nCn
=2(nＣ02＋nＣ12＋・・＋(nＣ(n-1)/2)2)
=偶数
●case2 n=偶数
2nCn
=2(nＣ02＋nＣ12＋・・＋(nＣ(n-2)/2)2)+(nＣn/2)2
=偶数（2C1＝２、帰納法で証明できる）
◆茨城県 小川 康幸 さんからの解答。
【問題４】
| 2nＣn＝ |
2n n | *(2n-1Cn-1)=2*(2n-1Cn-1) |
よって、2nＣnは偶数である。
さて、ここで問題になっていた、
を一般化した、
【定理】
pを素数、n，mを自然数とする。
が成立する。
を証明したいと思います。
その為に、補題を二つほど準備します。
【補題１】
f＜pn なる任意の自然数 f に対して、
となる。
【証明】
f=pr*s
ただし、sは、pと互いに素な自然数、rは、0以上の整数と書ける。
pr≦pr*s= f＜pn より r＜n である。
ここで、
とおくと、
よって、
ゆえに、
が、pで割り切れる。
sとpは互いに素なので、
が、pで割り切れる。
よって、となる。
証明終
【補題２】
g＜pn なる任意の非負整数 g に対して、
となる。
証明
数学的帰納法で示す。
g=0 のとき
だから、正しい。
g=k のとき、
となると仮定する。
ただし、kは、0＜k＜pn-1 なる、非負整数である。
0＜k+1＜pn だから、補題１より、
よって、
よって、g=k+1 のときも、 となって、正しい。
よって、数学的帰納法により、示された。
証明終わり
準備は出来ましたので、
を示します。
証明
補題２より、
p＞2のとき、pn-1は、偶数だから、
p=2のときも、
いずれにしても、
となる。
よって、
(ただし、hは非負整数)と書ける。
よって、
となる。
よって、
は、示された。
証明終わり
は、この定理の、m=2、p=2、n=kの特別な場合である。
この定理を使うと
12C4≡3 (mod 6) ,
72C8≡9 (mod 18),
54C9≡6 (mod 18)
などが言えます。
◆山梨県 Footmark さんからの解答。
nＣ0＋nＣ1*Ｘ＋nＣ2*Ｘ2＋…＋nＣn-1*Ｘn-1＋nＣnＸn
＝(1+Ｘ)n
今後はこの式を元の式と呼びます。
【問題１】
元の式で、Ｘ＝１ とすると
nＣ0＋nＣ1＋…＋nＣn-1＋nＣn
＝(1+1)n
＝２n
【問題２】
元の式で、Ｘ＝−１ とすると
nＣ0−nＣ1＋…＋(-1)nnＣn
＝(１−１)n
＝０
【問題３】
ｎｘｎのマスで、右１マス進むのを→で、上１マス進むのを↑で表すと、
ＰからＱに行く最短経路は、
ｎ個の→とｎ個の↑の計２ｎ個の→,↑の並び方になります。
ですから、
最短経路の数＝ 2nＣn
また、必ず図のいずれかの●は通らねばなりません。
１番上の●は０段、１番下の●はｎ段にあるものとすると、
↓
ですから、
最短経路の数
＝nＣ02＋nＣ12＋・・＋nＣn2
∴nＣ02＋nＣ12＋・・＋nＣn2＝2nＣn
【問題４】
【問題３】同様ｎｘｎのマスでの最短経路と考えます。
１つの最短経路の道順があれば、その道順の「横に進む」と「縦に進む」を入れ替えた道順も必ずあります。
この２つの道順で１対になっているので必ず偶数です。