【応用】連立漸化式(対称型)

ここでは、2つの数列の漸化式について見ていきます。漸化式の係数に対称性がある場合を取り上げます。

【広告】

連立漸化式を三項間漸化式に帰着させる方法

例題
数列 $\{a_n\}$, $\{b_n\}$ が次を満たしている。
\begin{eqnarray}
& & a_1=3,\ b_1=1 \\[5pt] & & a_{n+1}=3a_n+b_n \ (n=1,2,3,\cdots) \\[5pt] & & b_{n+1}=a_n+3b_n \ (n=1,2,3,\cdots) \\[5pt] \end{eqnarray}数列 $\{a_n\}$, $\{b_n\}$ の一般項を求めなさい。

2つの数列が混じっています。普通の連立方程式であれば、片方の式を何倍かした後に、もう片方の式を足したり引いたりして、 $x,y$ のどちらかを消すという加減法を用いて計算することが多いですが、今の場合はうまくいきません。例えば、2つ目の漸化式を3倍して1つ目の漸化式から引いても、消えるのは $a_n$ だけで、 $a_{n+1}$ が残ってしまいます。

連立方程式を解く場合には、加減法以外に、代入法もありましたね。こちらの方法は、以下のようにして使うことができます。

まず、1つ目の漸化式を変形すると\[ b_n=a_{n+1}-3a_n \]となります。この式は、 $n$ のところを $n+1$ にしても成り立つ(すべての自然数で成り立つから)ので、\[ b_{n+1}=a_{n+2}-3a_{n+1} \]も成り立ちます。これらを2つ目の漸化式に代入すると
\begin{eqnarray}
a_{n+2}-3a_{n+1} &=& a_n+3(a_{n+1}-3a_n) \\[5pt] a_{n+2}-6a_{n+1}+8a_n &=& 0 \\[5pt] \end{eqnarray}となり、数列 $\{a_n\}$ だけに関する漸化式となります。

【応用】三項間漸化式で見た内容を使えば、これを解くことができます。特性方程式 $x^2-6x+8=0$ の解は $x=2,4$ なので
\begin{eqnarray}
a_{n+2}-2a_{n+1} &=& 4(a_{n+1}-2a_n) \\[5pt] a_{n+2}-4a_{n+1} &=& 2(a_{n+1}-4a_n)
\end{eqnarray}の2つの式が得られます。これらから
\begin{eqnarray}
a_{n+1}-2a_n &=& 4^{n-1}(a_2-2a_1) \\[5pt] a_{n+1}-4a_n &=& 2^{n-1}(a_2-4a_1)
\end{eqnarray}の2つの式が得られます。 $a_1=3$ で、1つ目の漸化式から $a_2=3a_1+b_1=10$ なので、
\begin{eqnarray}
a_{n+1}-2a_n &=& 4^n \\[5pt] a_{n+1}-4a_n &=& -2^n
\end{eqnarray}の2つの式が得られます。1つ目から2つ目を引くと
\begin{eqnarray}
a_n &=& \frac{4^n+2^n}{2}
\end{eqnarray}が得られます。また、1つ目の漸化式から
\begin{eqnarray}
b_n &=& a_{n+1}-3a_n \\[5pt] &=& \frac{4^{n+1}+2^{n+1}}{2}-3\cdot\frac{4^n+2^n}{2} \\[5pt] &=& \frac{4\cdot 4^n -3\cdot 4^n +2\cdot 2^n-3\cdot 2^n}{2} \\[5pt] &=& \frac{4^n-2^n}{2} \\[5pt] \end{eqnarray}が得られます。こうして、一般項は\[ a_n=\frac{4^n+2^n}{2},\ b_n=\frac{4^n-2^n}{2} \]と求められます。

連立漸化式の対称性を利用する方法

上のように解けば、一般的な連立漸化式を解くことが可能です。しかし、係数に対称性がある場合は、これを利用してもう少し簡単に解くことができます。

今の場合
\begin{eqnarray}
a_{n+1}&=&3a_n+b_n \\[5pt] b_{n+1}&=&a_n+3b_n \\[5pt] \end{eqnarray}となっていますが、1つ目の右辺の計数は、 $3,1$ で、2つ目は $1,3$ となっています。このような対称性がある場合、両辺を足す、両辺を引く、という式を考えることで、道が開けてきます。
\begin{eqnarray}
a_{n+1}+b_{n+1}&=&4(a_n+b_n) \\[5pt] a_{n+1}-b_{n+1}&=&2(a_n-b_n)
\end{eqnarray}こうして得られる2つの式をよく見ると、数列 $\{a_n+b_n\}$ は公比が4の等比数列であり、数列 $\{a_n-b_n\}$ は公比が2の等比数列であることがわかります。初項をそれぞれ計算すれば
\begin{eqnarray}
a_n+b_n&=&4^n \\[5pt] a_n-b_n&=&2^n
\end{eqnarray}と計算でき、両辺を足す・引くことにより
\begin{eqnarray}
a_n&=&\frac{4^n+2^n}{2} \\[5pt] b_n&=&\frac{4^n-2^n}{2} \\[5pt] \end{eqnarray}と求めることができます。

このように、対称性がある場合は、これを利用して2つの数列の和・差を考えることで、すっきりと解くことができるようになります。

おわりに

ここでは、対称性のある連立漸化式について、一般的な解き方と対称性を利用した解き方の2つを紹介しました。対称性がある場合には、これを利用して、計算量を減らすことを考えましょう。