下の命題Aは証明可能でしょうか。
（命題A）
nは正の整数とします。
二項係数mCkにおいて、
m=2^nとするとき、1≦k≦mを満たすすべての整数kに対して、
（mCk）・（2^k）は2^（n+1）で割り切れる
とある問題をとある方針で解いていましたら、上の命題Aが証明できたら、解けたということになりそうですが、命題Aの証明ができず、方針間違えたから、最初からやり直した方がいいか迷ってます。
命題Aは証明できる命題でしょうか。命題の設定がおかしいなどのご指摘もいただけると助かります。
ただ、証明可能な場合、証明自体は自分でやりたいため、やり方は書かないでほしいです。
k=1のときは、（mCk）・（2^k）=2^（n+1）なので、成り立つ。
k=2のときは、（mCk）・（2^k）=2^（n+1）・（2^n-1）なので、成り立つ。
k=mのときは、（mCk）・（2^k）=2^（2^n）で、2^n≧n+1なので、成り立つ。
色々計算してみると、命題Aは成り立つような気がしますが、どうでしょう。
|
No.90709 - 2026/03/07(Sat) 19:56:02
| ☆ Re: 二項係数 NEW / WIZ | | | 横から失礼します。
べき乗演算子^は四則演算より優先度が高いものとします。
二項係数 aCb を C(a, b) と書くことにします。
既に質問者さん自身も書いている通り、以下は成立します。
(1) a, bが自然数の場合、b*C(a, b) = a*C(a-1, b-1) である。
(2) aが自然数の場合、a < 2^a である。(つまり、a+1 ≦ 2^a である。)
修正版も含めて質問者さんのD以降は正しくないと思いますので、以下の方針とします。
自然数aを素因数分解したときの2の指数をs(a)で表すことにする。
s(1) = 0, s(2) = 1, s(3) = 0, s(4) = 2 などとなります。
(3) 自然数aに対して s(2^a) = a である。
(4) 自然数a, bに対して、s(ab) = s(a)+s(b) である。
(5) 自然数a, cに対して、a < 2^c ならば s(a) ≦ c-1 である。
すると、題意の式は以下のように変形できます。
自然数n, kに対して、1 ≦ k ≦ 2^n ならば s(C(2^n, k)*(2^k)) ≧ s(2^(n+1)) か?
つまり s(C(2^n, k)) ≧ n+1-k か? ということになります。
上記の証明は以下の通りです。
s(k*C(2^n, k)) = s((2^n)*C(2^n-1, k-1))
⇒ s(k)+s(C(2^n, k)) = s(2^n)+s(C(2^n-1, k-1))
⇒ s(C(2^n, k)) = n+s(C(2^n-1, k-1))-s(k)
ここで、s(C(2^n-1, k-1)) ≧ 0, -s(k) ≧ -(k-1) = 1-k となりますので、
# (2)より k < 2^k となり、(5)より s(k) ≦ k-1 といえます。
よって、
⇒ s(C(2^n, k)) ≧ n+0+(1-k) = n+1-k
となって、題意は成立するといえます。
|
No.90722 - 2026/03/12(Thu) 11:45:17 |
|
