加法定理の一般化
k-ナッチ数列の加法定理を求める
を一般化します。
線形漸化式 $\displaystyle f_{n+k} = \sum_{i=0}^{k-1} a_i f_{n+i}$（$a_i$は定数）を満たす数列$f_n$を考えます。
$v_n = \left(\begin{array}{}
f_n \\
f_{n+1} \\
\vdots \\
f_{n+k-1}
\end{array}\right)$とおくと$k \times k$行列$A$を用いて$v_{n+1} = A v_n$とかけるので、$v_n=A^n v_0$と行列累乗の形にできます。
$
v_{n+m} = A^{n+m} v_0 = A^n (A^m v_0) = A^n v_m
$なので$A^n$を$v_n$とかで表したいです。
長さ$k$の縦ベクトル$v_0, v_1, \ldots, v_{k-1}$を$k$本横に並べて作った行列を$\left(\begin{array}{}
v_0 \ v_1 \ v_2 \ldots v_{k-1}
\end{array}\right)
$のように表記することにすると、
\begin{eqnarray}
\left(\begin{array}{}
v_n \ v_{n+1} \ v_{n+2} \ldots v_{n+k-1}
\end{array}\right)
&=&
\left(\begin{array}{}
A^nv_0 \ A^{n+1}v_0 \ A^{n+2}v_0 \ldots A^{n+k-1}v_0
\end{array}\right) \\
&=&
A^n
\left(\begin{array}{}
v_0 \ Av_0 \ A^2v_0 \ldots A^{k-1}v_0
\end{array}\right) \\
&=&
A^n
\left(\begin{array}{}
v_0 \ v_1 \ v_2 \ldots v_{k-1}
\end{array}\right)
\end{eqnarray}
なので$A^n=\left(\begin{array}{}
v_n \ v_{n+1} \ v_{n+2} \ldots v_{n+k-1}
\end{array}\right)\left(\begin{array}{}
v_0 \ v_1 \ v_2 \ldots v_{k-1}
\end{array}\right)^{-1}$です。（右の行列が可逆なことは仮定します）
まとめると、
$$v_{n+m} = \left(\begin{array}{}
v_n \ v_{n+1} \ v_{n+2} \ldots v_{n+k-1}
\end{array}\right)\left(\begin{array}{}
v_0 \ v_1 \ v_2 \ldots v_{k-1}
\end{array}\right)^{-1}v_m$$
となってこれの第1成分をとると
$$f_{n+m} = {}^t v_n\left(\begin{array}{}
v_0 \ v_1 \ v_2 \ldots v_{k-1}
\end{array}\right)^{-1}v_m$$
となることがわかります。なんだかほぼ自明なことしかしていないですが証明パート終わりです。
$v_{n+1}=\left(\begin{array}{} f_{n+1} \\ f_{n+2} \end{array}\right) = \left(\begin{array}{} 0 & 1 \\ 1 & 1 \end{array}\right) \left(\begin{array}{} f_n \\ f_{n+1} \end{array}\right) =Av_n$とかけます。
$v_0=
\left(\begin{array}{}
f_0 \\
f_1
\end{array}\right)
=
\left(\begin{array}{}
0 \\
1
\end{array}\right)
, \quad
v_1=
\left(\begin{array}{}
f_1 \\
f_2
\end{array}\right)
=
\left(\begin{array}{}
1 \\
1
\end{array}\right)$より
$$\left(\begin{array}{}
v_0 \ v_1
\end{array}\right)^{-1}
=
\left(\begin{array}{}
0 & 1 \\
1 & 1
\end{array}\right)^{-1}
=
\left(\begin{array}{}
-1 & 1 \\
1 & 0
\end{array}\right)
$$
従って
\begin{eqnarray}
f_{n+m}&=&
\left(\begin{array}{}
f_n \ f_{n+1}
\end{array}\right)
\left(\begin{array}{}
-1 & 1 \\
1 & 0
\end{array}\right)
\left(\begin{array}{}
f_m \\
f_{m+1}
\end{array}\right)
=-f_nf_m+f_nf_{m+1}+f_{n+1}f_m \\
&=&f_nf_{m-1}+f_{n+1}f_m
\end{eqnarray}（最後の行は$f_{m+1}-f_m=f_{m-1}$を使った）
$v_{n+1}=\left(\begin{array}{} f_{n+1} \\ f_{n+2} \\ \vdots \\ f_{n+k} \end{array}\right) = \left(\begin{array}{} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ 0 & 0 & 0 & \ddots & 0 \\ \vdots & \vdots & \vdots & \ddots & 1 \\ 1 & 1 & 1 & \cdots & 1 \\ \end{array}\right) \left(\begin{array}{} f_n \\ f_{n+1} \\ \vdots \\ f_{n+k-1} \end{array}\right) =Av_n$とかけます。
$$\left(\begin{array}{}
v_0 \ v_1 \ \ldots \ v_{k-1}
\end{array}\right)^{-1}
=
\left(\begin{array}{}
0 & 0 & \cdots & \cdots & 1 \\
0 & \ddots & \ddots & \cdots & 1 \\
\vdots & \ddots & 1 & \cdots & 2 \\
\vdots & 1 & 1 & \cdots & \vdots \\
1 & 1 & 2 & \cdots & 2^{n-2} \\
\end{array}\right)^{-1}
=
\left(\begin{array}{}
-1 & -1 & \cdots & -1 & 1 \\
-1 & \ddots & \ddots & 1 & 0 \\
\vdots & \ddots & \ddots & 0 & \vdots \\
-1 & 1 & 0 & \ddots & \vdots \\
1 & 0 & \cdots & \cdots & 0 \\
\end{array}\right)
$$
従って
\begin{eqnarray}
f_{n+m}&=&\sum_{i=0}^{k-1}f_{n+i}\left(f_{m+k-1-i}-\sum_{j=0}^{k-2-i}f_{m+j}\right)\\
&=&\sum_{i=0}^{k-1}f_{n+i}\sum_{j=0}^i f_{m-1-i+j}
\end{eqnarray}
（最後の行は漸化式を使った）
添え字を適切に調整することで、
元記事
ともちゃんと合っていることがわかります。
添え字を実数だと思うと実はいけます。
$A=\left(\begin{array}{} 0 & 1 \\ -1 & 0 \end{array}\right), v_0=\left(\begin{array}{} 1 \\ 0 \end{array}\right)$とすると、
$A^n=\left(\begin{array}{} \cos\frac{\pi n}{2} & -\sin\frac{\pi n}{2} \\ \sin\frac{\pi n}{2} & \cos\frac{\pi n}{2} \end{array}\right), v_n=\left(\begin{array}{} \cos\frac{\pi n}{2} \\ \sin\frac{\pi n}{2} \end{array}\right)$だとみなせます。
すると$\left(\begin{array}{}
v_0 \ v_1
\end{array}\right)^{-1}
=
\left(\begin{array}{}
1 & 0 \\
0 & -1
\end{array}\right)^{-1}
=
\left(\begin{array}{}
1 & 0 \\
0 & -1
\end{array}\right)
$であり、
\begin{eqnarray}
\left(\begin{array}{}
\cos\frac{\pi (n+m)}{2} \\
\sin\frac{\pi (n+m)}{2}
\end{array}\right)
&=&
v_{n+m}=
\left(\begin{array}{}
v_n \ v_{n+1}
\end{array}\right)
\left(\begin{array}{}
1 & 0 \\
0 & -1
\end{array}\right)
v_m=
\left(\begin{array}{}
\cos\frac{\pi n}{2} & -\sin\frac{\pi n}{2} \\
\sin\frac{\pi n}{2} & \cos\frac{\pi n}{2}
\end{array}\right)
\left(\begin{array}{}
1 & 0 \\
0 & -1
\end{array}\right)
\left(\begin{array}{}
\cos\frac{\pi m}{2} \\
\sin\frac{\pi m}{2}
\end{array}\right) \\
&=&
\left(\begin{array}{}
\cos\frac{\pi n}{2}\cos\frac{\pi m}{2} - \sin\frac{\pi n}{2}\sin\frac{\pi m}{2} \\
\sin\frac{\pi n}{2}\cos\frac{\pi m}{2} + \cos\frac{\pi n}{2}\sin\frac{\pi m}{2}
\end{array}\right)
\end{eqnarray}
$\alpha=\frac{\pi n}{2}, \beta=\frac{\pi m}{2}$として$n, m$を実数にすれば加法定理が得られます。
最初は$A$を対角化してたんですが整理したら全然必要ないことに気づきました。
楕円関数の加法定理とかは線形じゃないのでこれでは難しそうですね。
