カタラン数の総和の式の証明
初投稿です、c(n)をn番目のカタラン数とした時、
c(n)=Σ[k=1,floor((n+1)/2)] (-1)^(k-1)*c(n-k)*C(n+1-k,k)
(floor(x)は床関数で、C(n,k)は二項係数)
の等号が成立することを、証明することは可能でしょうか？
一応コンピュータでn=100迄成り立つことは検証済みです。
偶然上記の成立しそうな関係を見つけたのですが、
証明する手立ても実力もなく、軽く調べた限り、
このような総和で記した文献が見当たらなかったため、
質問した次第です。
https://mathworld.wolfram.com/CatalanNumber.html
カタラン数C(n)の再帰的漸化式として(ただしC(0)=1 とする。)
C(n)=∑[k=0,n-1]C(k)*C(n-1-k)
C(n)=∑[k=0,n-1]binomial(n-1,2*k)*2^(n-1-2*k)*C(k)
C(n)=∑[k=1,floor((n+1)/2)](-1)^(k-1)*binomial(n+1-k,k)*C(n-k)
などがあるようです。
https://oeis.org/A000108
のサイトでの
FORMULA
の部分に掲載されています。
そこに掲載されているということは正しいということなんでしょうけど、OEIS には証明までは載っていませんね。
カタラン数が関係するなら組み合わせで証明したいところですが、(-1)^k が入った式でそれやるの、難しいんですよねえ。
式の意味を無視して式変形でやるなら、カタラン数も二項係数も階乗に直す方針になるんでしょうか？
まだやってみていませんけど。
Σ[k=0～floor((n+1)/2)]((-1)^(k-1))*C[n-k]*comb(n+1-k,k)=0
を示せばよいですね。
tの関数 f(t) をべき級数展開したときの t^n の係数を
[t^n]f(t)と書くことにします。
Σ[k=0～floor((n+1)/2)]((-1)^(k-1))*C[n-k]*comb(n+1-k,k)
=Σ[p=floor((n-1)/2)～n]((-1)^(n-p-1))*C[p]*comb(p+1,n-p)
=Σ[p=0～∞]((-1)^(n-p-1))*C[p]*comb(p+1,n-p)
=Σ[p=0～∞]((-1)^(n-p-1))*C[p]*[t^n]( (1+t)*(t*(1+t))^p )
=((-1)^(n-1))*[t^n]( (1+t)*Σ[p=0～∞]C[p]*(-t*(1+t))^p )
=((-1)^(n-1))*[t^n]( (1+t)*(1-sqrt(1-4*(-t*(1+t))))/(2*(-t*(1+t))) )
=((-1)^(n-1))*[t^n]( (1-sqrt((1+2*t)^2))/(2*(-t)) )
=((-1)^(n-1))*[t^n](1)
=((-1)^(n-1))*0
=0.
なるほど、カタラン数は母関数で扱う方針がありましたか。
細かいですが、2行目の
> Σ[p=floor((n-1)/2)～n]
は
Σ[p=n-floor((n+1)/2)～n]
ですかね。
一般に a-floor(b) ≠ floor(a-b) ですので。
次の行以降には影響しないので、2行目だけ修正すれば3行目以降は再び正しくなります。
> Σ[p=floor((n-1)/2)～n]
>は
>Σ[p=n-floor((n+1)/2)～n]
>ですかね。
その通りですね。
ご指摘ありがとうございます。
Σ[p=ceil((n-1)/2)～n] と書かなければいけないところを、
間違って、Σ[p=floor((n-1)/2)～n]
と書いてしまっていますね。
失礼しました。
