a_[1,n]=1
a_[2,n]=n-1+1
a_[3,n]=(n-1)(n-2)/2+(n-1)+1のように
m≧2の時
a_[m,n]=1+Σ[t=1,m-1](n-1)(n-2)…(n-t)/t!とあらわせることを示す。
Ⅰmの時の成立を仮定するとm+1の時
a_[m+1,n]=1+Σ[k=1,n-1](a[m,k])
=1+Σ[k=1,n-1]1 + Σ[t=1,m-1](Σ[k=1,n-1](k-1)(k-2)…(k-t)/t!) (←tとkのΣの逆転)
=1+n-1+Σ[t=1,m-1]( (n-1)(n-2)(n-3)(n-4)…(n-(t+1)))/(t+1)!
=1+n-1+Σ[t=2,m]( (n-1)(n-2)(n-3)(n-4)…(n-t))/t!
=1+Σ[t=1,m]( (n-1)(n-2)(n-3)(n-4)…(n-t))/t!よりm+1でも成立。
Ⅱm=2の時a_[2,n]=n-1+1となりm=2でも成立。
Ⅰ,Ⅱより数学的帰納法からa_[m,n]=1+Σ[t=1,m-1](n-1)(n-2)…(n-t)/t!
これよりa_[m,2m]=1+Σ[t=1,m-1](2m-1)(2m-2)…(2m-t)/t!
=1+Σ[t=1,m-1](2m-1)Ct
=Σ[t=0,m-1](2m-1)Ct
ここで、(2m-1)Ct=(2m-1)C(2m-1-t)より
Σ[t=0,m-1](2m-1)Ct=Σ[t=0,m-1](2m-1)C(2m-1-t)=Σ[t=m,2m-1](2m-1)C(2m-1-t)…①
①とΣ[t=0,2m-1](2m-1)Ct=2^(2m-1)より
Σ[t=0,m-1](2m-1)Ct=2^(2m-2)=4^(m-1)
また、m=1の時もこれを満たす。
解説
上記のとおりです。
やっぱり数列や行列とかだと式が見にくくなるのでTexを少し勉強してみます。はい。
|