大学数学基礎解説

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

カタラン数,有限和,漸化式

389

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

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

問題

以下, $(\binom{n}{k})$ を二項係数 $_{n} C_{k}$ とします.

しゅーくりーむさんの問題の(19)

$\begin{aligned} \sum_{k = 0}^{N} \frac{(\binom{2 k}{k})}{k + 1} \frac{(\binom{2 N - 2 k}{N - k})}{N - k + 1} \end{aligned}$ を求めよ.

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

$\begin{aligned} \sum_{k = 0}^{N} \frac{(\binom{2 k}{k})}{k + 1} \frac{(\binom{2 N - 2 k}{N - k})}{N - k + 1} = \frac{(\binom{2 N + 2}{N + 1})}{N + 2} \end{aligned}$

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

例

有限和
$\begin{aligned} a_{N} & = \sum_{0 < n_{2} \leq n_{1} < N} \frac{1}{n_{1}^{2}} \frac{1}{N - n_{2}} \end{aligned}$
は,以下の漸化式を満たす.
$\begin{aligned} 0 & = (n^{3} + 6 n^{2} + 12 n + 8) a_{n + 3} + (- 5 n^{3} - 17 n^{2} - 22 n - 11) a_{n + 2} + (9 n^{3} + 10 n^{2} + 10 n + 3) a_{n + 1} + (- 7 n^{3} + 7 n^{2} - 6 n + 2) a_{n} + (2 n^{3} - 6 n^{2} + 6 n - 2) a_{n - 1} \end{aligned}$

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

一般化

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

$\begin{aligned} \sum_{k = 0}^{N} \frac{(\binom{2 k}{k})}{k + 1} \frac{(\binom{2 N - 2 k}{N - k})}{N - k + 1} = \frac{(\binom{2 N + 2}{N + 1})}{N + 2} \end{aligned}$

において
$\begin{array}{r} \frac{1}{(k + 1) (N - k + 1)} = \frac{1}{N + 2} (\frac{1}{k + 1} + \frac{1}{N - k + 1}) \end{array}$ および $k \to N - k$ としても式は変わらないので,
$\begin{aligned} \sum_{k = 0}^{N} \frac{(\binom{2 k}{k})}{k + 1} \frac{(\binom{2 N - 2 k}{N - k})}{N - k + 1} \\ = \frac{2}{N + 2} \sum_{k = 0}^{N} \frac{(\binom{2 k}{k}) (\binom{2 N - 2 k}{N - k})}{k + 1} \end{aligned}$ により,
$\begin{aligned} \sum_{k = 0}^{N} \frac{(\binom{2 k}{k}) (\binom{2 N - 2 k}{N - k})}{2^{2 N} (k + 1)} = 2 \sum_{k = 0}^{N} \frac{(\binom{2 N + 2}{N + 1})}{2^{2 N + 2}} \end{aligned}$

ここで,記号を
$\begin{array}{r} (a)_{n} = a (a + 1) \dots (a + n - 1) \end{array}$
( ポッホハマー記号 ),
$\begin{array}{r} [a]_{n} = \frac{(a)_{n}}{n!}, β_{n} = [1 / 2]_{n} = \frac{(\binom{2 n}{n})}{2^{2 n}} \end{array}$

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

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

$\begin{aligned} \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{aligned}$

$\begin{aligned} \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 - 3 a) 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 - 3 a) N + 2 (2 - a) (3 - a)} \frac{(4 - a)_{N - 2}}{(N + 3)!} \end{aligned}$

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

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

背景?

Zeilberger's Algorithmにより,
$β_{n} = \frac{(\binom{2 n}{n})}{2^{2 n}}, P_{N} (x)$ をルジャンドル多項式として
$\begin{array}{r} \sum_{k = 0}^{N} β_{k} β_{N - k} x^{k} = x^{\frac{N}{2}} P_{N} (\frac{x + 1}{2 \sqrt{x}}) \end{array}$

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

感想

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