□投稿者/ らすかる 一般人(6回)-(2021/02/12(Fri) 22:13:04)
 | 経路の交差点に順に数字を書き込んでいって何通りか調べる方法で考えて、
その方法でy=xに当たった時に2倍すればΣ[k=0〜n-1]2^k*a[k]が求まります。
y=0の行はすべて1
y=1の行は(1,1)が2、(2,1)が3、(3,1)が4、…のようになるのでx+1
y=2の行は(2,1)の3の2倍に4,5,6,…を加えていけばよいので
3×2+Σ[k=3〜x](k+1)=(x+1)(x+2)/2
同様にy=3の行は(3+1)(3+2)/2×2+Σ[k=4〜x]{(k+1)(k+2)/2}=(x+1)(x+2)(x+3)/6
y=4の行は(4+1)(4+2)(4+3)/6×2+Σ[k=5〜x]{(k+1)(k+2)(k+3)/6}=(x+1)(x+2)(x+3)(x+4)/24
一般にy=kの行が(x+k)Ckとなりそうなので
これを仮定してy=k+1の行を求めると
((k+1)+k)Ck×2+Σ[m=k+2〜x](m+k)Ck=(x+k+1)C(k+1)
なのでy=nのとき(x+n)Cn
S[n]はy=n-1のときのx=nの値なので
S[n]=(2n-1)C(n-1)
|
|
上記ツリーを一括表示 / 上記ツリーをトピック表示