証明できない等式(13/03/11追記)
もし暇があればだれか教えて下しあ
・その１
任意の自然数nについて
Σ[k=0～n](C(n+k,k)/2^k)＝2^n
→証明できたので追記に
・その２
n＜mを満たす任意の自然数n,mについて
Σ[k=0～m](C(m,k)*(-1)^k*(m-k)^n)＝0
→教えてもらったので追記に
出典（？）とか
その１はありがちな自作問を解く過程で。
「縦n本横n本の道が交差する場所の、左下を起点として、交差点に来るたびに1/2の確率で上または右に移動する。上端または右端に到達した時点で終了するとすると、終了する位置と各々の確率を求めよ」
その２は昨年の県数コンで話題に上っていたものの、証明が付いていなかったので。
「『n人の人間にm個の仕事を割り当てる。全ての人間にちょうど１つの仕事を与え、全ての仕事に対し人をつけるような割り当て方は何通りか』という問いの答えは（その２）の式の左辺となるが、n＜mならば、割り当て方は存在しないので明らかに割り当て方は０通りである」
・その１
任意の自然数nについて
Σ[k=0～n](C(n+k,k)/2^k)＝2^n
→証明できたので追記に
・その２
n＜mを満たす任意の自然数n,mについて
Σ[k=0～m](C(m,k)*(-1)^k*(m-k)^n)＝0
→教えてもらったので追記に
出典（？）とか
その１はありがちな自作問を解く過程で。
「縦n本横n本の道が交差する場所の、左下を起点として、交差点に来るたびに1/2の確率で上または右に移動する。上端または右端に到達した時点で終了するとすると、終了する位置と各々の確率を求めよ」
その２は昨年の県数コンで話題に上っていたものの、証明が付いていなかったので。
「『n人の人間にm個の仕事を割り当てる。全ての人間にちょうど１つの仕事を与え、全ての仕事に対し人をつけるような割り当て方は何通りか』という問いの答えは（その２）の式の左辺となるが、n＜mならば、割り当て方は存在しないので明らかに割り当て方は０通りである」
（１）
Σ[k=0～n](C(n+k,k)/2^k)＝Snとして
Sn＝2^nであることを帰納法で求めればよい
n＝1で成立
n＝pでの成立を仮定し、n＝p+1を考える。
任意の自然数abについてC(a,b)＝C(a-1,b)+C(a-1,b-1)が成り立つので
（パスカルの三角形が分かりやすい）
シグマの中身の(C(p+1+k,k)/2^k)は
k＝0で
C(p+1,0)＝C(p,0)
1≦k≦pで
C(p+1+k,k)/2^k＝C(p+k,k)/2^k+C(p+k,k-1)/2^k
k＝p+1で
C(2p+2,p+1)＝C(2p+1,p+1)/2^(p+1)+C(2p+1,p)/2^(p+1)
＝C(2P+2,p+1)/2^(p+2)+C(2p+1,p)/2^(p+1)
となる。
k＝0と1≦k≦pの第１項の和は
Σ[k=0～p](C(p+k,k)/2^k)＝Sp
1≦k≦pの第２項とk＝p+1の和は
Σ[k=1～p+2](C(p+k,k-1)/2^k)
＝Σ[k=0～p+1](C(p+1+k,k)/2^(k+1))
＝1/2*Σ[k=0～p+1](C(p+1+k,k)/2^k)
＝S(p+1)/2
より
S(p+1)＝Sp+1/2*S(p+1)であり
Sp=2^pよりS(p+1)＝2^(p+1)
よって帰納法より、任意の自然数nで成立
（２）
二項定理より、任意の実数xと任意の自然数mについて
(1+x)^m=Σ[t=0～m](C(m,t)*x^t)
が成り立つ。
この等式について「両辺をxで微分し、xを掛ける」という操作をn回（n＜m）行うと
(1+x)^(m-n)*Q(x)=Σ[t=0～m](C(m,t)*x^t*t^n)
となることが帰納的にわかる。
ここで、x=-1、t=m-kを代入し
Σ[k=0～m](C(m,k)*(-1)^(m-k)*(m-k)^n)＝0
両辺に(-1)^mをかけて(-1)^(-k)=(-1)^kより
Σ[k=0～m](C(m,k)*(-1)^k*(m-k)^n)＝0
Σ[k=0～n](C(n+k,k)/2^k)＝Snとして
Sn＝2^nであることを帰納法で求めればよい
n＝1で成立
n＝pでの成立を仮定し、n＝p+1を考える。
任意の自然数abについてC(a,b)＝C(a-1,b)+C(a-1,b-1)が成り立つので
（パスカルの三角形が分かりやすい）
シグマの中身の(C(p+1+k,k)/2^k)は
k＝0で
C(p+1,0)＝C(p,0)
1≦k≦pで
C(p+1+k,k)/2^k＝C(p+k,k)/2^k+C(p+k,k-1)/2^k
k＝p+1で
C(2p+2,p+1)＝C(2p+1,p+1)/2^(p+1)+C(2p+1,p)/2^(p+1)
＝C(2P+2,p+1)/2^(p+2)+C(2p+1,p)/2^(p+1)
となる。
k＝0と1≦k≦pの第１項の和は
Σ[k=0～p](C(p+k,k)/2^k)＝Sp
1≦k≦pの第２項とk＝p+1の和は
Σ[k=1～p+2](C(p+k,k-1)/2^k)
＝Σ[k=0～p+1](C(p+1+k,k)/2^(k+1))
＝1/2*Σ[k=0～p+1](C(p+1+k,k)/2^k)
＝S(p+1)/2
より
S(p+1)＝Sp+1/2*S(p+1)であり
Sp=2^pよりS(p+1)＝2^(p+1)
よって帰納法より、任意の自然数nで成立
（２）
二項定理より、任意の実数xと任意の自然数mについて
(1+x)^m=Σ[t=0～m](C(m,t)*x^t)
が成り立つ。
この等式について「両辺をxで微分し、xを掛ける」という操作をn回（n＜m）行うと
(1+x)^(m-n)*Q(x)=Σ[t=0～m](C(m,t)*x^t*t^n)
となることが帰納的にわかる。
ここで、x=-1、t=m-kを代入し
Σ[k=0～m](C(m,k)*(-1)^(m-k)*(m-k)^n)＝0
両辺に(-1)^mをかけて(-1)^(-k)=(-1)^kより
Σ[k=0～m](C(m,k)*(-1)^k*(m-k)^n)＝0
コメント
コメントの投稿
トラックバック
