しゅーくりーむさんの問題を一般化する

こんにちは,itouです.今回はXで見かけた しゅーくりーむさんの問題 の(19)に関して書きます.

問題

以下,${n\choose k}$を二項係数${}_n \mathrm{ C }_k$とします.

難しいですね...私は解けませんでした.しゅーくりーむさんによるとカタラン数の漸化式から導けるらしいです.一般に,このような問題は解く(=closed formで表す)ことが非常に難しいです.(closed formで表せないことの方が多いです.)結果からいうとこの問題の答えは以下です.

\begin{align} &\sum_{k=0}^{N}\frac{{2k\choose k}}{k+1}\frac{{2N-2k\choose N-k}}{N-k+1}=\frac{{2N+2\choose N+1}}{N+2} \end{align}

この等式を導く方法の一つがZeilberger's Algorithmです.つい先日, GWリレー記事:有限和とZeilberger's Algorithm という記事を書きました.Zeilberger's Algorithmとは,ある関数$a(n)$が与えられたとき,それが満たす多項式係数漸化式を与えるアルゴリズムです.

このように,ある有限和を漸化式によって特徴づけることができるのがZeilberger's Algorithmです.そして,求められた漸化式が斉次2項間漸化式なら,容易に解くことができます.しゅーくりーむさんの問題においては
\begin{align} a_N=&\sum_{k=0}^{N}\frac{{2k\choose k}}{k+1}\frac{{2N-2k\choose N-k}}{N-k+1} \end{align}
とおき,アルゴリズムを適用して,
\begin{align} (N+2)a_N=2(2N+1)a_{N-1} \end{align}
を得るのでこの漸化式を繰り返し適用し,$a_0=1$を用いて
\begin{align} a_N=\frac{{2N+2\choose N+1}}{N+2} \end{align}
を得ます.

一般化

Zeilberger's Algorithmを用いると,この等式の一般化を得ることができます.まず,少し変形しておきます.

\begin{align} &\sum_{k=0}^{N}\frac{{2k\choose k}}{k+1}\frac{{2N-2k\choose N-k}}{N-k+1}=\frac{{2N+2\choose N+1}}{N+2} \end{align}

において
\begin{align} \frac{1}{(k+1)(N-k+1)}=\frac{1}{N+2}\left(\frac{1}{k+1}+\frac{1}{N-k+1}\right) \end{align}および$k\rightarrow N-k$としても式は変わらないので,
\begin{align} &\sum_{k=0}^{N}\frac{{2k\choose k}}{k+1}\frac{{2N-2k\choose N-k}}{N-k+1}\\ &=\frac{2}{N+2}\sum_{k=0}^{N}\frac{{2k\choose k}{2N-2k\choose N-k}}{k+1}\\ \end{align}により,
\begin{align} &\sum_{k=0}^{N}\frac{{2k\choose k}{2N-2k\choose N-k}}{2^{2N}(k+1)}=2\sum_{k=0}^{N}\frac{{2N+2\choose N+1}}{2^{2N+2}}\\ \end{align}

ここで,記号を
\begin{align} (a)_n=a(a+1)\cdots(a+n-1) \end{align}
( ポッホハマー記号 ),
\begin{align} [a]_n=\frac{(a)_n}{n!},\beta_n=[1/2]_n=\frac{{2n\choose n}}{2^{2n}} \end{align}

とします.(この記号については こちらも参照 )

これを用いると,上の等式は
\begin{align} &\sum_{k=0}^{N}\frac{\beta_k\beta_{N-k}}{k+1}=2\beta_{N+1}\\ \end{align}
とかけます.
さて,やはりZeilberger's Algorithmを用いると,以下の等式を得ます.
\begin{align} &\sum_{k=0}^{N}\frac{[a]_k[1-a]_{N-k}}{k+1}=\frac{1}{1-a}[1-a]_{N+1} \end{align}
分母を少し変えてみます.

\begin{align} \sum_{k=0}^{N}\frac{[a]_k[1-a]_{N-k}}{(k+1)(k+2)}&=\frac{2\{(1-a)N+2-a\}}{(1-a)(2-a)(N+2)}[1-a]_{N+1}\\ &=2\{(1-a)N+2-a\}\frac{(3-a)_{N-1}}{(N+2)!} \end{align}

\begin{align} \sum_{k=0}^{N}\frac{[a]_k[1-a]_{N-k}}{(k+1)(k+2)(k+3)}&=\frac{3\{(1-a)(2-a)N^2+(1-a)(10-3a)N+2(2-a)(3-a)\}}{(1-a)(2-a)(3-a)(N+3)(N+2)}[1-a]_{N+1}\\ &=3\{(1-a)(2-a)N^2+(1-a)(10-3a)N+2(2-a)(3-a)\}\frac{(4-a)_{N-2}}{(N+3)!} \end{align}

逆に,分子に$k$が来る場合は,

\begin{align} &\sum_{k=0}^{N}[a]_k[1-a]_{N-k}=1 \end{align}
\begin{align} &\sum_{k=0}^{N}k[a]_k[1-a]_{N-k}=aN\\ \end{align}
\begin{align} &\sum_{k=0}^{N}k(k+1)[a]_k[1-a]_{N-k}=\frac{a}{2}N\{(1+a)N+3-a\}\\ \end{align}
などが求まります.

背景?

Zeilberger's Algorithmにより,
$\beta_n=\frac{{2n\choose n}}{2^{2n}},P_N(x)$を ルジャンドル多項式 として
\begin{align} \sum_{k=0}^{N}\beta_k\beta_{N-k}x^{k}=x^{\frac{N}{2}}P_N\left(\frac{x+1}{2\sqrt{x}}\right) \end{align}

であることが分かります.この等式の両辺を$x$で微分したり積分したりすることで上の等式(において$a=1/2$としたもの)の左辺の形を得ることができます.微分については容易ですが,積分については,私の力不足のためにできませんでした...ルジャンドル多項式には直行性があるなど良い性質があるので,求めることは不可能ではないと思います.

感想

Zeilberger's Algorithmで遊んでいるとこんな感じで等式を得ることができます.(ただし,自分で有限和の形をもってくる必要があるので,効率は悪いですが).$k\rightarrow N-k$について対称な形だと有限和が求まることが多い気がします.今回の等式はカタラン数がらみだったので,組み合わせ論的解釈を応用できないでしょうか.

謝辞

ここまで読んで下さりありがとうございました.誤植等指摘よろしくお願いいたします.