k-ナッチ数列の加法定理の一般化
今回は
Y.K.さんの記事
で示された$k$-ナッチ数列の加法定理の一般化を与えようと思う. $k$-ナッチ数列は
\begin{align}
W_n&=W_{n-1}+\cdots+W_{n-k}
\end{align}
という$k+1$項間漸化式と初期条件$W_0=\cdots=W_{k-2}=0,W_{k-1}=1$を満たすものである. そのとき, $k$-ナッチ数列の加法定理は
\begin{align}
W_{n+m}&=\sum_{i=1}^kW_{n-i+1}\sum_{j=i}^kW_{m+j-2}
\end{align}
が成り立つというものだった. これは
さくねこさんの記事
で一般の定数係数の$k+1$項間漸化式を満たす数列に対して拡張されているようである. しかし, 一般の場合の明示式は与えられていないようなので, 今回はそれを与えようと思う.
$A_n$が満たす漸化式を
\begin{align}
A_n&=a_1A_{n-1}+\cdots+a_kA_{n-k}\quad n\geq k
\end{align}
とする. 次に, 負の引数まで拡張された数列$E_n$を$E_0=1$,
\begin{align}
E_{-n}=0\qquad n<0
\end{align}
と定義し, $E_1$以降は漸化式
\begin{align}
E_n&=a_1E_{n-1}+\cdots+a_kE_{n-k}\qquad n>0
\end{align}
によって定まるものとする. $A_n$の漸化式の母関数を考えると,
\begin{align}
0&=\sum_{k\leq n}(A_n-a_1A_{n-1}-\cdots-a_kA_{n-k})t^n\\
&=-c_0-c_1t-\cdots-c_{k-1}t^{k-1}+\sum_{0\leq n}(A_nt^n-a_1A_nt^{n+1}-\cdots-a_kA_nt^{n+k})\\
&=-c_0-c_1t-\cdots-c_{k-1}t^{k-1}+(1-a_1t-\cdots-a_kt^k)\sum_{0\leq n}A_nt^n\\
\end{align}
を得る. ここで, $c_0,\dots,c_{k-1}$はある定数である. よって, 母関数は
\begin{align}
\sum_{0\leq n}A_nt^n&=\frac{c_0+c_1t+\cdots+c_{k-1}t^{k-1}}{1-a_1t-\cdots-a_kt^k}
\end{align}
と表される. 一方, $E_n$の母関数も全く同様に,
\begin{align}
\sum_{0\leq n}E_nt^n&=\frac{1}{1-a_1t-\cdots-a_kt^k}
\end{align}
と表されるので, これを上の式に代入すると,
\begin{align}
\sum_{0\leq n}A_nt^n&=(c_0+c_1t+\cdots+c_{k-1}t^{k-1})\sum_{0\leq n}E_nt^n
\end{align}
を得る. この両辺の係数を比較すると
\begin{align}
E_n&=c_0E_n+c_1E_{n-1}+\cdots+c_{k-1}E_{n-k+1}
\end{align}
と表される. よって, $E_n$の加法定理が与えられれば, その線形和として$A_n$の加法定理を得ることができる. $E_{n+m}$の2変数の母関数を考えると,
\begin{align}
\sum_{0\leq n,m}E_{n+m}s^nt^m&=\sum_{0\leq N}E_N\sum_{0\leq n,m,n+m=N}s^nt^m\\
&=\sum_{0\leq N}E_N\frac{s^{N+1}-t^{N+1}}{s-t}\\
&=\frac 1{s-t}\left(s\sum_{0\leq N}E_Ns^N-t\sum_{0\leq N}E_Nt^N\right)\\
&=\frac 1{s-t}\left(\frac{s}{1-a_1s-\cdots- a_ks^k}-\frac{t}{1-a_1t-\cdots-a_kt^k}\right)\\
&=\frac 1{s-t}\frac{s\left(\displaystyle1-\sum_{i=1}^ka_it^i\right)-t\left(\displaystyle1-\sum_{i=1}^ka_is^i\right)}{(1-a_1s-\cdots -a_ks^k)(1-a_1t-\cdots-a_kt^k)}\\
&=\frac{1+st\displaystyle\sum_{i=1}^ka_i\frac{s^{i-1}-t^{i-1}}{s-t}}{(1-a_1s-\cdots -a_ks^k)(1-a_1t-\cdots-a_kt^k)}\\
&=\frac{1+\displaystyle\sum_{i=1}^ka_i\sum_{j=1}^{i-1}s^jt^{i-j}}{(1-a_1s-\cdots -a_ks^k)(1-a_1t-\cdots-a_kt^k)}
\end{align}
よってこの両辺の$s^nt^m$の係数を比較して,
\begin{align}
E_{n+m}&=E_nE_m+\sum_{i=1}^ka_i\sum_{j=1}^{i-1}E_{n-j}E_{m-i+j}\\
&=E_nE_m+\sum_{j=1}^{k-1}E_{n-j}\sum_{i=j+1}^ka_iE_{m-i+j}
\end{align}
を得る. これより$A_n$の加法定理も
\begin{align}
A_{n+m}&=\sum_{l=0}^{k-1}c_lE_{n+m-l}\\
&=\sum_{l=0}^{k-1}c_lE_{n-l}E_m+\sum_{l=0}^{k-1}c_l\sum_{j=1}^{k-1}E_{n-l-j}\sum_{i=j+1}^ka_iE_{m-i+j}\\
&=A_nE_m+\sum_{j=1}^{k-1}A_{n-j}\sum_{i=j+1}^ka_iE_{m-i+j}
\end{align}
と得ることができる. $E_m=\sum_{i=1}^ka_iE_{m-i}$であることから, これは
\begin{align}
A_{n+m}&=\sum_{j=0}^{k-1}A_{n-j}\sum_{i=j+1}^ka_iE_{m-i+j}
\end{align}
と書き換えることができる. まとめると以下を得る.
数列$\{A_n\}_{n\geq 0}$を漸化式
\begin{align}
A_n&=a_1A_{n-1}+\cdots+a_kA_{n-k}\quad n\geq k
\end{align}
を満たすものとする. 負の引数まで拡張された数列$E_n$を$E_0=1$,
\begin{align}
E_{-n}=0\qquad n<0
\end{align}
と定義し, $E_1$以降は漸化式
\begin{align}
E_n&=a_1E_{n-1}+\cdots+a_kE_{n-k}\qquad n>0
\end{align}
によって定義されるものとすると,
\begin{align}
A_{n+m}&=\sum_{j=0}^{k-1}A_{n-j}\sum_{i=j+1}^ka_iE_{m-i+j}
\end{align}
が成り立つ.
$k$-ナッチ数列の場合, $a_1=\cdots=a_k=1, E_n=W_{n+k-1}$であるからこれを代入すると,
\begin{align}
W_{n+m}&=\sum_{j=0}^{k-1}W_{n-j}\sum_{i=j+1}^kW_{m-i+j+k-1}\\
&=\sum_{j=0}^{k-1}W_{n-j}\sum_{i=j+1}^kW_{m+i-2}\qquad i\mapsto k+j+1-i\\
&=\sum_{j=1}^{k}W_{n-j+1}\sum_{i=j}^kW_{m+i-2}\qquad j\mapsto j-1\\
\end{align}
となってY.Kさんが示した形の$k$-ナッチ数列の加法定理が得られることが分かる.
