チェビシェフ多項式の係数計算で現れる二項係数の和の計算について（解決編）

ずっと気になっていた計算が、いい方法で解けた気がするので、
ちょっとだけ殴り書きしておきます。

あと、最近記事の更新が止まっておりますが、ぼちぼちまた更新します、まぁぼちぼちで。

問題提起

発端は私の書いた記事「直交多項式と超幾何関数(1)〜チェビシェフ多項式と三角関数〜」内において、
私が計算に困っていたところでした。

困っていた主張は次のようなものでした。

$k \leq [n / 2]$ を満たす非負整数 $k, n$ に対し、次の等式が成立する。
$\begin{array}{r} \sum_{j = k}^{[n / 2]} (\binom{n}{2 j}) (\binom{j}{k}) = 2^{n - 2 k - 1} n \frac{(n - k - 1)!}{k! (n - 2 k)!} \end{array}$

ついでにそこまでの計算も端折っていたので、復習がてら背景を書いておきます。

第一種Chebyshev多項式 $T_{n} (x)$ の一般項をexplicitに書き下す式がほしいので
$T_{n} (x)$ が満たす三項間漸化式から導出できないか、という話でした。
第一種Chebyshev多項式が満たす三項間漸化式は
$\begin{array}{r} T_{n + 2} (x) - 2 x T_{n + 1} (x) + T_{n} (x) = 0 \\ T_{0} (x) = 1, T_{1} (x) = x \end{array}$
のようになっていた。
ここから三項間漸化式を解くことで(ここは普通の定数係数の三項間漸化式と同様)
$T_{n} (x)$ の一般項は
$\begin{array}{r} T_{n} (x) = \frac{1}{2} {{(x + \sqrt{x^{2} - 1})}^{n} + {(x - \sqrt{x^{2} - 1})}^{n}} \end{array}$
のようになることがわかった。
次にこれを二項展開して、 $x$ の多項式としての係数が見やすい形にしたい。(ここからの計算を端折っていた)

まずそれぞれの項を二項展開する。
その後出てくる $(x^{2} - 1)$ の冪についても同様に二項展開を行う。その方針で計算をしていく。

$\begin{aligned} T_{n} (x) & = \frac{1}{2} {{(x + \sqrt{x^{2} - 1})}^{n} + {(x - \sqrt{x^{2} - 1})}^{n}} \\ = \frac{1}{2} {\sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} {(\sqrt{x^{2} - 1})}^{k} + \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} (- 1)^{k} {(\sqrt{x^{2} - 1})}^{k}} \\ = \sum_{\begin{array}{c} k = 0 \\ k : 偶数 \end{array}}^{n} (\binom{n}{k}) x^{n - k} {(\sqrt{x^{2} - 1})}^{k} (k が偶数のときのみ値が残る) \\ = \sum_{k = 0}^{[n / 2]} (\binom{n}{2 k}) x^{n - 2 k} (x^{2} - 1)^{k} \\ = \sum_{k = 0}^{[n / 2]} (\binom{n}{2 k}) x^{n - 2 k} {\sum_{j = 0}^{k} (\binom{k}{j}) (- 1)^{j} (x^{2})^{k - j}} (二項定理) \\ = \sum_{k = 0}^{[n / 2]} \sum_{j = 0}^{k} (- 1)^{j} (\binom{n}{2 k}) (\binom{k}{j}) x^{n - 2 j} \\ = \sum_{j = 0}^{[n / 2]} \sum_{k = 0}^{j} (- 1)^{k} (\binom{n}{2 j}) (\binom{j}{k}) x^{n - 2 k} (見映えのため変数 j と k の記号交換) \\ = \sum_{k = 0}^{[n / 2]} (- 1)^{k} {\sum_{j = k}^{[n / 2]} (\binom{n}{2 j}) (\binom{k}{j})} x^{n - 2 k} (和の順序交換) \end{aligned}$
となり、この式が導き出される背景の式まで到達することができた。
この式はここで行き詰まってしまい、
別の導出方法で求めた一般項と等号で結んであげることで、二項係数に関する和の予想が立っていたのだ。

TKSSさんの記事

その後、当時の記事内でも改めて加筆紹介させていただきましたが、
TKSSさんの記事「チェビシェフ多項式の係数計算で現れる二項係数の和の計算ついて」において
この和を $k$ 重和に分解し、望遠鏡和でバサリバサリと和を計算していく手法が得られた。
これは見栄えがかっこいい。
本人が書かれていますように確かに和の範囲等気にすると面倒なところは山ほどありそうで
(もちろん正しい手法でしょうが)厳密性はまた別問題の気がしている。という話であった。

解決編

改めて、主張を述べようと思う。

$k \leq [n / 2]$ なる非負整数 $k, n$ に対し、以下の2つの式が成立する。
$\begin{aligned} (1) & \sum_{j = k}^{[n / 2]} (\binom{n + 1}{2 j + 1}) (\binom{j}{k}) & = 2^{n - 2 k} (\binom{n - k}{k}) \\ (2) & \sum_{j = k}^{[n / 2]} (\binom{n}{2 j}) (\binom{j}{k}) & = \frac{n}{n - k} 2^{n - 2 k - 1} (\binom{n - k}{k}) \end{aligned}$

元々必要だった式は(2)である(第二種の場合を計算する際には(1)の主張が必要である)。
式の形が一見して違うが、次のようにして一致することはすぐにわかる。
$\begin{array}{r} \frac{n}{n - k} (\binom{n - k}{k}) = \frac{n}{n - k} \frac{(n - k)!}{k! (n - 2 k)!} = n \frac{(n - k - 1)!}{k! (n - 2 k)!} \end{array}$

さて、実は(2)の証明は(1)に帰着されることがわかるので、実際(1)を示すだけで良いとなる。

[(2)の証明は(1)に帰着されること]

(1)の成立を仮定する。(1)において、 $n$ を $n - 2$ 、 $k$ を $k - 1$ で置換する。
その時 $k \leq [n / 2]$ の仮定を保っていることに注意する。
$\begin{array}{r} \sum_{j = k - 1}^{[n / 2] - 1} (\binom{n - 1}{2 j + 1}) (\binom{j}{k - 1}) = 2^{n - 2 k} (\binom{n - k - 1}{k - 1}) \end{array}$
次に左辺の和の変数 $j$ を $j - 1$ で置換する。
$\begin{array}{r} \sum_{j = k}^{[n / 2]} (\binom{n - 1}{2 j - 1}) (\binom{j - 1}{k - 1}) = 2^{n - 2 k} (\binom{n - k - 1}{k - 1}) \end{array}$
次に二項係数の吸収定理 $(\binom{n}{k}) = \frac{n}{k} (\binom{n - 1}{k - 1})$ を(逆向きに)使って変形すると
$\begin{aligned} \sum_{j = k}^{[n / 2]} \frac{2 j}{n} (\binom{n}{2 j}) \cdot \frac{k}{j} (\binom{j}{k}) = 2^{n - 2 k} \frac{k}{n - k} (\binom{n - k}{k}) \\ \Leftrightarrow \sum_{j = k}^{[n / 2]} (\binom{n}{2 j}) (\binom{j}{k}) = 2^{n - 2 k - 1} \frac{n}{n - k} (\binom{n - k}{k}) \end{aligned}$
となり(2)式の成立が示された。（証明終わり）

同様にすれば、(2)式を仮定した状態で(1)式の成立も言える。すなわち同値な主張であった。
(1)式の方が見た目が簡単なので、こちらを証明することにする。

証明の方針であるが、
両辺の $n$ に関する母関数が一致することを示すことで(1)式を示していく。
なお、ここで言う「母関数」とは通常型母関数のことであり、
数列 $a_{n}$ に対し、冪級数 $\sum a_{n} t^{n}$ のことをその母関数と呼ぶことにしている。

まず(1)式の右辺の母関数は次のようになる。
$\begin{aligned} \sum_{n \geq 2 k} {2^{n - 2 k} (\binom{n - k}{k})} t^{n} & = 2^{- 2 k} \sum_{n \geq 2 k} (\binom{n - k}{k}) (2 t)^{n} \\ = 2^{- 2 k} \sum_{n \geq k} (\binom{n}{k}) (2 t)^{n + k} (n - k を n と置換する) \\ = 2^{- k} t^{k} \sum_{n \geq k} (\binom{n}{k}) (2 t)^{n} \\ = 2^{- k} t^{k} \frac{(2 t)^{k}}{(1 - 2 t)^{k + 1}} (以下の補題 2 より) \\ = \frac{t^{2 k}}{(1 - 2 t)^{k + 1}} \end{aligned}$
とこのように簡単に母関数が計算できる。

ここで二項係数に関する母関数の式が必要である。簡単に述べておく。

二項係数に関する母関数

1変数冪級数環 $R [[t]]$ の元として(もしくは $| t | < 1$ なる実数に対し)次の式が成立する。
$\begin{array}{r} \sum_{n \geq k} (\binom{n}{k}) t^{n} = \frac{t^{k}}{(1 - t)^{k + 1}} \end{array}$

帰納法でパパッと済ませておく。

$\sum_{m \geq k - 1} (\binom{m}{k - 1}) t^{m} = \frac{t^{k - 1}}{(1 - t)^{k}}$ の式の両辺に $\sum_{l \geq 1} t^{l} = \frac{t}{1 - t}$ を掛ける。左辺を計算する。
$\begin{aligned} {\sum_{m \geq k - 1} (\binom{m}{k - 1}) t^{m}} {\sum_{l \geq 1} t^{l}} & = \sum_{\begin{array}{c} m \geq k - 1 \\ l \geq 1 \end{array}} (\binom{m}{k - 1}) t^{m + l} \\ = \sum_{n \geq k} {\sum_{m = k - 1}^{n - 1} (\binom{m}{k - 1})} t^{n} (*) \\ = \sum_{n \geq k} (\binom{n}{k}) t^{n} (二項係数の和の公式) \end{aligned}$
のように示すことができる。
ここで $(*)$ について少し補足をしておく。
$m \geq k - 1, l \geq 1$ の範囲で $m + l = n$ を満たす格子点 $(m, l)$ は
$(m, l) = (k - 1, n - k + 1), (k, n - k), \dots, (n - 1, 1)$ に限られるからである。

また、 $(*)$ の範囲では和の順序の取り替えを行なっているが、これは行うことが可能である。（証明終わり）

最後に(1)式の左辺の母関数を計算する。実は必要な道具は全部もう揃っている。

$\begin{aligned} \sum_{n \geq 2 k} {\sum_{j = k}^{[n / 2]} (\binom{n + 1}{2 j + 1}) (\binom{j}{k})} t^{n} & = \sum_{j \geq k} (\binom{j}{k}) {\sum_{n \geq 2 j} (\binom{n + 1}{2 j + 1}) t^{n}} (ここの和の順序の取り替えに注意が必要) \\ = \sum_{j \geq k} (\binom{j}{k}) {\sum_{n \geq 2 j + 1} (\binom{n}{2 j + 1}) t^{n - 1}} (n + 1 を n で置換) \\ = t^{- 1} \sum_{j \geq k} (\binom{j}{k}) {\sum_{n \geq 2 j + 1} (\binom{n}{2 j + 1}) t^{n}} \\ = t^{- 1} \sum_{j \geq k} (\binom{j}{k}) \frac{t^{2 j + 1}}{(1 - t)^{2 j + 2}} (補題 2 より) \\ = \frac{1}{(1 - t)^{2}} \sum_{j \geq k} (\binom{j}{k}) {\frac{t^{2}}{(1 - t)^{2}}}^{j} \\ = \frac{1}{(1 - t)^{2}} \frac{{\frac{t^{2}}{(1 - t)^{2}}}^{k}}{{1 - \frac{t^{2}}{(1 - t)^{2}}}^{k + 1}} (補題 2 より) \\ = \frac{1}{(1 - t)^{2}} \frac{t^{2 k} (1 - t)^{2}}{{(1 - t)^{2} - t^{2}}^{k + 1}} (繁分数の分母分子に (1 - t)^{2 k + 2} を掛ける) \\ = \frac{t^{2 k}}{(1 - 2 t)^{k + 1}} \end{aligned}$
となり、(1)式の右辺の母関数と一致することがわかる。
よって(1)式の整合性が言えたことになる。（証明終わり）

いくつかの疑問

(Q1) 和の順序の取り替えのところは、無限和のものを順序交換しているが、大丈夫なのか？
(A1) 十分小さい実数 $t$ に関して絶対収束しているから大丈夫だろう(冪級数としてどうかは知らん)

(Q2) 補題2を $\frac{t^{2}}{(1 - t)^{2}}$ に対して用いているが、大丈夫なのか？
(A2) これも実数範囲に限定しての話であるが、
$\begin{array}{r} | t | < 1 かつ | \frac{t^{2}}{(1 - t)^{2}} | < 1 \Leftrightarrow - 1 < t < \frac{1}{2} \end{array}$
となるので、この領域の $t$ に関しては正しい式であることは確かである。

追伸

$\begin{aligned} \sum_{n \geq 2 k} {\frac{n}{n - k} 2^{n - 2 k - 1} (\binom{n - k}{k})} t^{n} & = \sum_{n \geq 2 k} {\frac{n}{k} 2^{n - 2 k - 1} (\binom{n - k - 1}{k - 1})} t^{n} \\ = k^{- 1} 2^{- 2 k - 1} \sum_{n \geq 2 k} n (\binom{n - k - 1}{k - 1}) (2 t)^{n} \\ = k^{- 1} 2^{- 2 k - 1} \sum_{n \geq k - 1} (n + k + 1) (\binom{n}{k - 1}) (2 t)^{n + k + 1} \\ = k^{- 1} 2^{- k} t^{k + 1} \sum_{n \geq k - 1} (n + k + 1) (\binom{n}{k - 1}) (2 t)^{n} \\ = k^{- 1} 2^{- k} t^{k + 1} {\sum_{n \geq k - 1} (n + 1) (\binom{n}{k - 1}) (2 t)^{n} + k \sum_{n \geq k - 1} (\binom{n}{k - 1}) (2 t)^{n}} \\ = k^{- 1} 2^{- k} t^{k + 1} {\sum_{n \geq k - 1} k (\binom{n + 1}{k}) (2 t)^{n} + k \sum_{n \geq k - 1} (\binom{n}{k - 1}) (2 t)^{n}} \\ = 2^{- k} t^{k + 1} {\sum_{n \geq k} (\binom{n}{k}) (2 t)^{n - 1} + \sum_{n \geq k - 1} (\binom{n}{k - 1}) (2 t)^{n}} \\ = 2^{- k} t^{k + 1} {\frac{1}{2 t} \frac{(2 t)^{k}}{(1 - 2 t)^{k + 1}} + \frac{(2 t)^{k - 1}}{(1 - 2 t)^{k}}} \\ = 2^{- k} t^{k + 1} \frac{(2 t)^{k - 1} {1 + (1 - 2 t)}}{(1 - 2 t)^{k + 1}} \\ = \frac{t^{2 k} (1 - t)}{(1 - 2 t)^{k + 1}} \end{aligned}$

$\begin{aligned} \sum_{n \geq 2 k} {\sum_{j = k}^{[n / 2]} (\binom{n}{2 j}) (\binom{j}{k})} t^{n} & = \sum_{j \geq k} (\binom{j}{k}) {\sum_{n \geq 2 j} (\binom{n}{2 j}) t^{n}} \\ = \sum_{j \geq k} (\binom{j}{k}) \frac{t^{2 j}}{(1 - t)^{2 j + 1}} \\ = \frac{1}{1 - t} \sum_{j \geq k} (\binom{j}{k}) {\frac{t^{2}}{(1 - t)^{2}}}^{j} \\ = \frac{1}{1 - t} \frac{{(\frac{t^{2}}{(1 - t)^{2}})}^{k}}{{(1 - \frac{t^{2}}{(1 - t)^{2}})}^{k + 1}} \\ = \frac{1}{1 - t} \frac{t^{2 k} (1 - t)^{2}}{{(1 - t)^{2} - t^{2}}^{k + 1}} \\ = \frac{t^{2 k} (1 - t)}{(1 - 2 t)^{k + 1}} \end{aligned}$

なんか、、、直接(2)式も普通に示せてしまいましたわ。そりゃそうだけど。

まとめ

やっぱり母関数は偉大だった。以上。
ま、帰納法でも示せるような式ではあるのではあるが、それだと面白みがなくて。

母関数で示したことによる帰結というか、面白いなと思ったのは、
$\begin{array}{r} \sum_{k = 0}^{[n / 2]} (- 1)^{k} {\sum_{j = k}^{[n / 2]} (\binom{n}{2 j}) (\binom{k}{j})} x^{n - 2 k} = T_{n} (x) \end{array}$
というChebyshev多項式が出てくるのに対して、通常母関数を考えると
$\begin{array}{r} \sum_{n \geq 2 k} {\sum_{j = k}^{[n / 2]} (\binom{n}{2 j}) (\binom{j}{k})} t^{n} = \frac{t^{2 k} (1 - t)}{(1 - 2 t)^{k + 1}} \end{array}$
という高々有理式になる、みたいなところである。何か背景に別の理論があるのかな。