(行列式)=(定数)型の漸化式の解き方
はじめに
この記事では
$$\det\begin{pmatrix}
a_{n-1}&a_n\\a_n&a_{n+1}
\end{pmatrix}=c$$
という漸化式や
$$\det\begin{pmatrix}
f(n-1,k-1)&f(n,k-1)\\f(n-1,k)&f(n,k)
\end{pmatrix}=c$$
といった形の漸化式の解き方について紹介していきます。
補題
いま上のような形の行列式に関する有名事実として次のような公式が成り立ちます。
数列$a_n,b_n$が同じ漸化式
\begin{align}
a_{n+1}&=p_na_n+q_na_{n-1}\\
b_{n+1}&=p_nb_n+q_nb_{n-1}
\end{align}
を満たすとき
$$a_nb_{n-1}-a_{n-1}b_n=(a_0b_1-a_0b_1)\prod^{n-1}_{k=1}(-q_k)$$
が成り立つ。
\begin{align}
a_{n+1}&=p_na_n+q_na_{n-1}\\
b_{n+1}&=p_nb_n+q_nb_{n-1}
\end{align}
の両辺にそれぞれ$b_n,a_n$を掛けて差を取ることで
$$a_{n+1}b_n-a_nb_{n+1}=-q_n(a_nb_{n-1}-a_{n-1}b_n)$$
が成り立つことに注意するとわかる。
$$M_n=\begin{pmatrix}a_n&b_n\\a_{n-1}&b_{n-1}\end{pmatrix},\quad
A_n=\begin{pmatrix}p_n&q_n\\1&0\end{pmatrix}$$
とおくと
$$M_{n+1}=A_nM_n$$
が成り立つので、この漸化式は
$$M_n=A_{n-1}A_{n-2}\cdots A_1M_1$$
と解け、この行列式を取ることで主張を得る。
これは$a_n,b_n$の満たす漸化式から
$$d_n=a_nb_{n-1}-a_{n-1}b_n$$
の値を与える公式となっていますが、逆に$d_n$などの情報から$a_n,b_n$が満たす漸化式を逆算することができ、具体的には以下の公式が成り立ちます(cf.
ベルヌーイの公式
)。
数列$a_n,b_n$に対し
\begin{align}
d_n&=a_nb_{n-1}-a_{n-1}b_n\\
p_n&=a_{n+1}b_{n-1}-a_{n-1}b_{n+1}
\end{align}
とおいたとき
\begin{align}
d_na_{n+1}&=p_na_n-d_{n+1}a_{n-1}\\
d_nb_{n+1}&=p_nb_n-d_{n+1}b_{n-1}
\end{align}
が成り立つ。
\begin{align}
p_na_n
&=(a_nb_{n-1}-a_{n-1}b_n)a_{n+1}+(a_{n+1}b_n-a_nb_{n+1})a_{n-1}\\
&=d_na_{n+1}+d_{n+1}a_{n-1}
\end{align}
とわかる($p_nb_n$についても同様)。
$$M_n=\begin{pmatrix}a_n&b_n\\a_{n-1}&b_{n-1}\end{pmatrix}$$
とおいたとき
\begin{align}
M_{n+1}M_n^{-1}
&=\frac1{d_n}\begin{pmatrix}a_{n+1}&b_{n+1}\\a_n&b_n\end{pmatrix}
\begin{pmatrix}b_{n-1}&-b_n\\-a_{n-1}&a_n\end{pmatrix}\\
&=\frac1{d_n}\begin{pmatrix}p_n&-d_{n+1}\\d_n&0\end{pmatrix}
\end{align}
より
\begin{align}
\begin{pmatrix}a_{n+1}&b_{n+1}\\a_n&b_n\end{pmatrix}
&=\frac1{d_n}\begin{pmatrix}p_n&-d_{n+1}\\d_n&0\end{pmatrix}
\begin{pmatrix}a_n&b_n\\a_{n-1}&b_{n-1}\end{pmatrix}\\
&=\frac1{d_n}
\begin{pmatrix}p_na_n-d_{n+1}a_{n-1}&p_nb_n-d_{n+1}b_{n-1}\\d_na_n&d_nb_n\end{pmatrix}
\end{align}
が成り立つのでこの第$1$行を比較することで主張を得る。
そしてこれを用いることで(行列式)$=$(定数)型の漸化式は線形漸化式に帰着させることができる、ということを以下で見ていきましょう。
特に次の形の主張を覚えておくと何かと便利だと思います。
数列$a_n,b_n$に対し
$$d_n=a_nb_{n-1}-a_{n-1}b_n$$
とおいたとき
$$\frac{d_na_{n+1}+d_{n+1}a_{n-1}}{a_n}
=\frac{d_nb_{n+1}+d_{n+1}b_{n-1}}{b_n}$$
が成り立つ。
本題
例えば$b_n=a_{n+1},\ d_n=cq^n$とすると次のような主張が成り立ちます。
数列$a_n\neq0$が
$$a_{n+1}=\frac{a_n^2+cq^n}{a_{n-1}}\qquad(c\neq0)$$
を満たすとき
$$a_{n+1}=\frac{a_2+qa_0}{a_1}a_n-qa_{n-1}$$
が成り立つ。
上の補題より
$$\frac{a_{n+2}+qa_n}{a_{n+1}}=\frac{a_{n+1}+qa_{n-1}}{a_n}$$
が成り立つことに注意するとわかる。
また例えば二重数列$f(n,k)$に対し
$$d(n,k)=\det\begin{pmatrix}
f(n,k)&f(n,k-1)\\
f(n-1,k)&f(n-1,k-1)
\end{pmatrix}$$
とおいたとき$q_n=d(n+1,k)/d(n,k)$が$k$に依らなければ数列$f(n,0),f(n,1),f(n,2),\ldots$は同じ漸化式
$$a_{n+1}=p_na_n-q_na_{n-1}$$
を満たす系列となることがわかるので、これによって次のような主張が得られます。
二重数列$f(n,k)\neq0$に対しある$k,n$に依らない数列$d_1(n),d_2(k)\neq0$が存在し
$$\det\begin{pmatrix}
f(n,k)&f(n,k-1)\\
f(n-1,k)&f(n-1,k-1)
\end{pmatrix}=d_1(n)d_2(k)$$
が成り立つとき
\begin{align}
p_1(n)&=\frac{d_1(n)f(n+1,0)+d_1(n+1)f(n-1,0)}{d_1(n)f(n,0)}\\
p_2(k)&=\frac{d_2(k)f(0,k+1)+d_2(k+1)f(0,k-1)}{d_2(k)f(0,k)}\\
q_1(n)&=\frac{d_1(n+1)}{d_1(n)}\\
q_2(k)&=\frac{d_2(k+1)}{d_2(k)}
\end{align}
とおくと
\begin{align}
f(n+1,k)&=p_1(n)f(n,k)-q_1(n)f(n-1,k)\\
f(n,k+1)&=p_2(k)f(n,k)-q_2(k)f(n,k-1)
\end{align}
が成り立つ。
$$a_n=f(n,k),\quad b_n=f(n,k-1)$$
や
$$a_k=f(n,k),\quad b_k=f(n-1,k)$$
に対し上の補題を用いることで
\begin{align}
p_1(n,k)&=\frac{d_1(n)f(n+1,k)+d_1(n+1)f(n-1,k)}{f(n,k)}\\
p_2(n,k)&=\frac{d_2(k)f(n,k+1)+d_2(k+1)f(n,k-1)}{f(n,k)}
\end{align}
について
$$p_1(n,k)=p_1(n,k-1),\quad p_2(n,k)=p_2(n-1,k)$$
が成り立つことに注意するとわかる。
またこのことは
$$M(n,k)=\begin{pmatrix}
f(n,k)&f(n,k-1)\\
f(n-1,k)&f(n-1,k-1)
\end{pmatrix}$$
とおいたとき
\begin{align}
M(n+1,k)&=\begin{pmatrix}p_1(n)&-q_1(n)\\1&0\end{pmatrix}M(n,k)\\
M(n,k+1)&=M(n,k)\begin{pmatrix}p_2(k)&1\\-q_2(k)&0\end{pmatrix}
\end{align}
が成り立つことと言い換えられ、これによって
$$M(n+1,k+1)
=\begin{pmatrix}p_1(n)&-q_1(n)\\1&0\end{pmatrix}\cdots
\begin{pmatrix}p_1(1)&-q_1(1)\\1&0\end{pmatrix}
M(1,1)
\begin{pmatrix}p_2(1)&1\\-q_2(1)&0\end{pmatrix}\cdots
\begin{pmatrix}p_2(k)&1\\-q_2(k)&0\end{pmatrix}$$
という明示式が得られます。
二重数列$f(n,k)\neq0$に対し、ある定数$c,p_1,p_2,q_1,q_2\ (c,q_1,q_2\neq0)$が存在し
$$\det\begin{pmatrix}
f(n,k)&f(n,k-1)\\
f(n-1,k)&f(n-1,k-1)
\end{pmatrix}=cq_1^nq_2^k$$
および
\begin{align}
\frac{f(n+1,0)+q_1f(n-1,0)}{f(n,0)}&=p_1\\
\frac{f(0,k+1)+q_2f(0,k-1)}{f(0,k)}&=p_2
\end{align}
が成り立つとき
$$\begin{pmatrix}
f(n,k)&f(n,k-1)\\
f(n-1,k)&f(n-1,k-1)
\end{pmatrix}
=\begin{pmatrix}p_1&-q_1\\1&0\end{pmatrix}^{n-1}
\begin{pmatrix}f(1,1)&f(1,0)\\f(0,1)&f(0,0)\end{pmatrix}
\begin{pmatrix}p_2&1\\-q_2&0\end{pmatrix}^{k-1}$$
が成り立つ。
ちなみに二次方程式
$$x^2-px-q=0$$
の解を$x=\a,\b$とし
$$x_n=\frac{\a^n-\b^n}{\a-\b}$$
とおくと
$$\begin{pmatrix}p&q\\1&0\end{pmatrix}^n
=\begin{pmatrix}x_{n+1}&qx_n\\x_n&qx_{n-1}\end{pmatrix}$$
が成り立つことを覚えておくといいかもしれません。
二重数列$f(n,k)$を
$$f(n,0)=an+1,\quad f(0,k)=bk+1$$
および漸化式
$$f(n,k)=\frac{f(n,k-1)f(n-1,k)+c}{f(n-1,k-1)}$$
によって定めたとき
\begin{align}
&\phantom{{}=}
\begin{pmatrix}
f(n+1,k+1)&f(n+1,k)\\
f(n,k+1)&f(n,k)
\end{pmatrix}\\
&=\begin{pmatrix}2&-1\\1&0\end{pmatrix}^n
\begin{pmatrix}f(1,1)&f(1,0)\\f(0,1)&f(0,0)\end{pmatrix}
\begin{pmatrix}2&1\\-1&0\end{pmatrix}^k\\
&=\begin{pmatrix}n+1&-n\\n&-(n-1)\end{pmatrix}
\begin{pmatrix}(a+1)(b+1)+c&a+1\\b+1&1\end{pmatrix}
\begin{pmatrix}k+1&k\\-k&-(k-1)\end{pmatrix}
\end{align}
が成り立つので、これを展開することで
$$f(n,k)=(ab+c)nk+an+bk+1$$
を得る。
数列$a_n$を漸化式
$$a_{n+1}=\frac{a_n^2+c}{a_{n-1}}\qquad(c\neq0)$$
によって定めたとき
$$f(n,k)=a_{n+k}$$
に対し上の定理を適用することで
$$a_{n+k+1}=\frac{a_{k+1}+a_{k-1}}{a_k}a_{n+k}-a_{n+k-1}$$
が成り立つので、$k=1$とすることで
$$a_{n+2}=\frac{a_2+a_0}{a_1}a_{n+1}-a_n$$
という漸化式を得る。
この記事を高評価した人
この記事に送られたバッジ
投稿者
