チェビシェフ多項式の係数計算で現れる二項係数の和の計算ついて

本記事について

本記事はにゃん太郎さんの次の記事
直交多項式と超幾何関数(1)〜チェビシェフ多項式と三角関数〜
の中に現れる次の二項係数の和

$$\sum _{j=k}^{[n/2]}\begin{array}{r}\left(\begin{array}{c}n\\ 2j\end{array}\right)\left(\begin{array}{c}j\\ k\end{array}\right)\end{array}$$
をどのように計算するかについての記事となります。
上記和の出自の詳細については にゃん太郎さんの記事 をご参照ください。

計算

$$\sum _{j=k}^{[n/2]}\begin{array}{r}\left(\begin{array}{c}n\\ 2j\end{array}\right)\left(\begin{array}{c}j\\ k\end{array}\right)\end{array}$$
について、仮に$k=0$ならよくある二項係数の和になり、
$k=1$の場合も同じ計算に帰着できます。
要は2個目の二項係数の$j$に関する項が邪魔なため
これがなくなるよう$j$がある部分の次数(?)下げをします。
次の２つの事実を利用します.

$$\begin{array}{r}\left(\begin{array}{c}n\\ r\end{array}\right)=\frac{n}{r}\left(\begin{array}{c}n-1\\ r-1\end{array}\right)\cdots (1),\left(\begin{array}{c}n\\ r\end{array}\right)=\sum _{k=r-1}^{n-1}\left(\begin{array}{c}k\\ r-1\end{array}\right)\cdots (2)\end{array}$$

$\begin{array}{r}\left(\begin{array}{c}n\\ 2j\end{array}\right)\end{array}$に(1),(2)をこの順に適用すると
$$\begin{array}{r}\left(\begin{array}{c}n\\ 2j\end{array}\right)=\frac{n}{2j}\left(\begin{array}{c}n-1\\ 2j-1\end{array}\right)=\sum _{i_1=2j-2}^{n-2}\frac{n}{2j}\left(\begin{array}{c}{i}_1\\ 2j-2\end{array}\right)\end{array}$$
となり、和の中に同じ形の二項係数が再び現れるので
これを$k-1$回繰り返したのち、もう１回（1）を適用すると
$$\begin{array}{r}\left(\begin{array}{c}n\\ 2j\end{array}\right)=\sum _{i_1=2j-2}^{n-2}\sum _{i_2=2j-4}^{i_1-2}\frac{n{i}_1}{2^{2}j(j-1)}\left(\begin{array}{c}{i}_2\\ 2j-4\end{array}\right)\end{array}$$
$$\begin{array}{r} =\cdots \cdots \end{array}$$
$$=\sum _{i_1=2j-2}^{n-2}\sum _{i_2=2j-4}^{i_1-2}\cdots \sum _{i_m=2j-2m}^{i_{m-1}-2}\cdots \sum _{i_{k-1}=2j-2(k-1)}^{i_{k-2}-2}\frac{n{i}_1{i}_2\cdots i_{k-2}}{2^{k-1}j(j-1)\cdots (j-k+2)}\left(\begin{array}{c}{i}_{k-1}\\ 2j-2(k-1)\end{array}\right)$$
$$=\sum _{i_1=2j-2}^{n-2}\sum _{i_2=2j-4}^{i_1-2}\cdots \sum _{i_m=2j-2m}^{i_{m-1}-2}\cdots \sum _{i_{k-1}=2j-2(k-1)}^{i_{k-2}-2}\frac{n{i}_1{i}_2\cdots i_{k-2}{i}_{k-1}}{2^{k}j(j-1)\cdots (j-k+1)}\left(\begin{array}{c}{i}_{k-1}-1\\ 2j-2k+1\end{array}\right)$$
これより
$$\sum _{j=k}^{[n/2]}\begin{array}{r}\left(\begin{array}{c}n\\ 2j\end{array}\right)\left(\begin{array}{c}j\\ k\end{array}\right)=\sum _{j=k}^{[n/2]}\sum _{i_1=2j-2}^{n-2}\sum _{i_2=2j-4}^{i_1-2}\cdots \sum _{i_m=2j-2m}^{i_{m-1}-2}\cdots \sum _{i_{k-1}=2j-2(k-1)}^{i_{k-2}-2}\frac{n{i}_1{i}_2\cdots i_{k-1}(j-k)!}{2^{k}j!}\left(\begin{array}{c}{i}_{k-1}-1\\ 2j-2k+1\end{array}\right)\left(\begin{array}{c}j\\ k\end{array}\right)\end{array}$$
$$\begin{array}{r}=\sum _{j=k}^{[n/2]}\sum _{i_1=2j-2}^{n-2}\sum _{i_2=2j-4}^{i_1-2}\cdots \sum _{i_m=2j-2m}^{i_{m-1}-2}\cdots \sum _{i_{k-1}=2j-2(k-1)}^{i_{k-2}-2}\frac{n{i}_1{i}_2\cdots i_{k-1}}{2^{k}k!}\left(\begin{array}{c}{i}_{k-1}-1\\ 2j-2k+1\end{array}\right)\end{array}$$
二項係数が単独になったので、$k$重和の取る順序を入れ替えて$j$についての和を最初にとるように変更する
$$\sum _{j=k}^{[n/2]}\begin{array}{r}\left(\begin{array}{c}n\\ 2j\end{array}\right)\left(\begin{array}{c}j\\ k\end{array}\right)=\sum _{i_1=2k-2}^{n-2}\sum _{i_2=2k-4}^{i_1-2}\cdots \sum _{i_m=2k-2m}^{i_{m-1}-2}\cdots \sum _{i_{k-1}=2}^{i_{k-2}-2}\sum _{j=k}\frac{n{i}_1{i}_2\cdots i_{k-1}}{2^{k}k!}\left(\begin{array}{c}{i}_{k-1}-1\\ 2j-2k+1\end{array}\right)\end{array}$$
最初の和は１つ飛ばしの二項係数の和なので計算出来て
$$\sum _{j=k}^{[n/2]}\begin{array}{r}\left(\begin{array}{c}n\\ 2j\end{array}\right)\left(\begin{array}{c}j\\ k\end{array}\right)=\sum _{i_1=2k-2}^{n-2}\sum _{i_2=2k-4}^{i_1-2}\cdots \sum _{i_m=2k-2m}^{i_{m-1}-2}\cdots \sum _{i_{k-1}=2}^{i_{k-2}-2}\frac{n{i}_1{i}_2\cdots i_{k-1}}{2^{k}k!}{2}^{i_{k-1}-2}\end{array}$$
よって次に考える和は
$$\sum _{i_{k-1}=2}^{i_{k-2}-2}{i}_{k-1}{2}^{i_{k-1}-2}$$
となる。これは地道にやればできるやつだが後続のために
次の変形で処理する。
$i_{k-1}=2(i_{k-1}-1)-(i_{k+1}-2)$より
$$\sum _{i_{k-1}=2}^{i_{k-2}-2}{i}_{k-1}{2}^{i_{k-1}-2}=\sum _{i_{k-1}=2}^{i_{k-2}-2}[(i_{k-1}-1)2^{i_{k-1}-1}-(i_{k-1}-2)2^{i_{k-1}-2}]$$
和の中の１項目と次の項の２項目が打ち消しあうので
$$\sum _{i_{k-1}=2}^{i_{k-2}-2}{i}_{k-1}{2}^{i_{k-1}-2}=(i_{k-2}-2-1)2^{i_{k-2}-2-1}-(2-2)2^{2-2}=(i_{k-2}-3)2^{i_{k-2}-3}$$
この結果から次の和は
$$\sum _{i_{k-2}=4}^{i_{k-3}-2}{i}_{k-2}(i_{k-2}-3)2^{i_{k-2}-3}$$
となり、これも$i_{k-2}=2(i_{k-1}-2)-(i_{k+1}-4)$より
$$\sum _{i_{k-2}=4}^{i_{k-3}-2}{i}_{k-2}(i_{k-2}-3)2^{i_{k-2}-3}=\sum _{i_{k-2}=4}^{i_{k-3}-2}[(i_{k-2}-2)(i_{k-2}-3)2^{i_{k-2}-2}-(i_{k-2}-3)(i_{k-2}-4)2^{i_{k-2}-3}]=(i_{k-3}-4)(i_{k-3}-5)2^{i_{k-3}-4}$$
次の
$$\sum _{i_{k-3}=6}^{i_{k-4}-2}{i}_{k-3}(i_{k-3}-4)(i_{k-3}-5)2^{i_{k-3}-4}$$
に対して$i_{k-3}=2(i_{k-1}-3)-(i_{k+1}-6)$が用意できるあたりでおおよそ見当がついて、最終的に
$$\sum _{i_1=2k-2}^{n-2}{i}_1(i_1-k)(i_1-k-1)\cdots (i_1-(2k-3))2^{i_1-k}$$
について$i_1=2(i_1-k+1)-(i_1-(2k-2))$として
$$\sum _{i_1=2k-2}^{n-2}{i}_1(i_1-k)(i_1-k-1)\cdots (i_1-(2k-3))2^{i_1-k}=(n-k-1)(n-k-2)\cdots (n-2k+1)2^{n-k-1}$$
ゆえ
$$\sum _{j=k}^{[n/2]}\begin{array}{r}\left(\begin{array}{c}n\\ 2j\end{array}\right)\left(\begin{array}{c}j\\ k\end{array}\right)=\frac{n}{2^{k}k!}(n-k-1)(n-k-2)\cdots (n-2k+1)2^{n-k-1}\end{array}$$
$$\begin{array}{r}=\frac{n(n-k-1)!}{k!(n-2k)!}{2}^{n-2k-1}\end{array}$$
を得る。

注意

上記では書きたい筋書での議論を優先してあえて言及していないが
$k$重和の和の取り方を変更する箇所は議論に困難がある。
$j$の和の上限はどうなのか、という話だが
$k$重和などとすると本当に面倒くさい。
どうせこの手の数列の一般項計算は厳密には数学的帰納法を
伴うことになるので、最初から次数を１段下げただけの2重和にとどめて
帰納法の仮定として一般項を導入するのが厳密な議論となると思われる。