up previous 上: 二項間漸化式 前: 漸化式とは何か

の解法

南海  そこで今考えるのは, 式$F(a_k,\ k)$$a_n$については1次で, かつ1次の係数が定数である漸化式である.

もちろんその他にも

\begin{displaymath}
a_{n+1}=\dfrac{n+1}{n+2}a_n
\end{displaymath}

のように係数が$n$の式なるものもある.これはこのようによほど特別な型でなければ解けない. これは今は置いておく.

今考えるのは,漸化式が定数$r$$n$の関数$f(n)$を用いて

\begin{displaymath}
a_{n+1}=ra_n+f(n)\quad \cdots\maru{1}
\end{displaymath}

と表せるものだ.

この型の漸化式ですぐに解けるのはどのようなときか.

早苗  $r=1$ $f(n)=d\ (定数)$なら等差数列です.

$f(n)=0$なら数列$\{a_n\}$は等比数列です.

これらは一般項が求まります.

$a_1=a$とすると,

$r=1$$f(n)=d$のときは$a_n=a+d(n-1)$です.

$f(n)=0$のときは$a_n=ar^{n-1}$です.

南海  その証明は?

早苗  えっ.そうかこれも数学的帰納法で示せばよい.

南海  そう.これはすぐにできる.

もうひとつ$r=1$のとき.これも教科書にのっている.

早苗  はい.階差数列が $a_{n+1}-a_n=f(n)$となるので,$n\ge 2$のとき

\begin{displaymath}
a_n=a_1+\sum_{k=1}^{n-1}f(k)
\end{displaymath}

です.

南海  以上の3つは$\maru{1}$型のうち簡単に解ける漸化式だ.

その他の漸化式も,いろいろ変形を工夫して, このいずれかの解ける場合に持ちこむのだ.

そこで, $a_{n+1}=ra_n+f(n)$型の漸化式の解法をまとめよう.

解き方は,大きく分けて3通りある. それぞれについてまず一般的方法を述べて, 教科書にものっている 漸化式 $a_{n+1}=3a_n+2$$a_1=1$として解きながら説明しよう.

解法1:一つの解を見つける


南海  漸化式 $a_{n+1}=ra_n+f(n)$を満たす数列,

つまり

\begin{displaymath}
u_{n+1}=ru_n+f(n)
\end{displaymath}
となる数列$\{u_n\}$を何らかの方法で 見つけるのだ.

これを, $a_{n+1}=ra_n+f(n)$をから辺々引くと

\begin{displaymath}
a_{n+1}-u_{n+1}=r(a_n-u_n)
\end{displaymath}

これから数列$\{a_n-u_n\}$は公比$r$の等比数列なので,

\begin{displaymath}
a_n-u_n=r^{n-1}(a_1-u_1)
\end{displaymath}


\begin{displaymath}
∴\quad a_n=u_n+r^{n-1}(a_1-u_1)\quad \cdots\maru{2}
\end{displaymath}

早苗  一つ見つけるといっても簡単ではありません.

南海  いや実は $a_{n+1}=3a_n+2$の場合,教科書はこの方法で解いている.

早苗  これは教科書では,

\begin{displaymath}
\alpha=3\alpha+2
\end{displaymath}

とおいて$\alpha=-1$.これから

\begin{displaymath}
a_{n+1}+1=3(a_n+1)
\end{displaymath}

と変形します.

南海  これがまさに,解法1なのだ.

早苗  $u_n$は?…. そうかわかりました.$u_n=-1$で定数の数列です.

南海  そうなのだ.

早苗  このとき$\maru{2}$

\begin{displaymath}
a_n+1=3^{n-1}(a_1+1)=2\cdot3^{n-1}
\end{displaymath}

となります.これから $a_n=2\cdot3^{n-1}-1$です.

南海  この解法1は$f(n)$$n$の多項式のとき特に有効だ. $f(n)$の次数を$j$とする.$j$次式$g(n)$

\begin{displaymath}
g(n)=e_jn^j+e_{j-1}n^{j-1}+\cdots
\end{displaymath}

とおき,

\begin{displaymath}
g(n+1)=rg(n)+f(n)
\end{displaymath}

となるように,係数比較して$g(n)$を決める. 未知係数が$j+1$個あり,それらをすべて比較した連立1次方程式を解けばよい. そして,$u_n=g(n)$とすればよいのだ.

早苗  $f(n)$$n$の多項式のときは, 一つの解自身が$n$の多項式で得られるのですね.

南海 f(n) が cpn の指数関数型でもこの方法が使える. それはあとの例でやろう.

解法2:3項間漸化式に持ちこむ


南海  $a_{n+1}=ra_n+f(n)$より $a_{n+2}=ra_{n+1}+f(n+1)$である. また漸化式に定数$t$をかけて $t a_{n+1}=t ra_n+t f(n)$とし,辺々引くと

\begin{displaymath}
a_{n+2}-t a_{n+1}=ra_{n+1}-t ra_n+f(n+1)-t f(n)
\quad \cdots\maru{3}
\end{displaymath}

これから

\begin{displaymath}
a_{n+2}-(t+r) a_{n+1}+t ra_n=f(n+1)-t f(n)
\end{displaymath}

ここで$f(n+1)-t f(n)$が簡単なものになるように$t$を選ぶのだ. それができれば,三項間漸化式が得られる.

早苗  これも難しく見えます.

この方法で $a_{n+1}=3a_n+2$を解くのはどうなるのですか. この場合は$f(n)=2$なので

\begin{displaymath}
f(n+1)-t f(n)=2-2t
\end{displaymath}

そうか,この場合は$t=1$でいいのですね.

これは要するに $a_{n+1}=3a_n+2$ $a_{n+2}=3a_{n+1}+2$から

\begin{displaymath}
a_{n+2}-a_{n+1}=3(a_{n+1}-a_n)
\end{displaymath}

と階差をとる方法です. 得られた階差数列が等比数列になるタイプです.

$a_2=3+2=5$なので,

\begin{displaymath}
a_{n+1}-a_n=3^{n-1}(a_2-a_1)=4\cdot 3^{n-1}
\end{displaymath}

したがって,階差数列からもとの数列を求めて

\begin{eqnarray*}
a_n&=&a_1+\sum_{k=1}^{n-1}4\cdot 3^{k-1}\\
&=&1+4\cdot\dfrac{3^{n-1}-1}{3-1}=2\cdot 3^{n-1}-1
\end{eqnarray*}

となるのです.$n=1$のときも成り立ちます.

南海  階差をとる方法は$f(n)$$n$$j$次多項式のときにも有効だ.

\begin{displaymath}
f(n+1)-f(n)
\end{displaymath}

$j-1$次となる.何回かくりかえせば,最後は定数になって解ける.

早苗  でもそこから,階差数列を順に解いていくのは大変です.

南海  そうだ.$n$の1次式や2次式なら可能だが,それ以上になると不便だ.

$t\ne 1$の場合は,例題でやってみよう.

解法3:等比数列との比をとる


南海  以上の2つの解法が一般的なものだ.

もう一つ $a_{n+1}=F(a_n,\ n)$$a_n$の定数係数の 1次式であることを生かす解法がある.

$\maru{1}$の両辺を $r^{n+1}$ で割る.

\begin{displaymath}
\dfrac{a_{n+1}}{r^{n+1}}=\dfrac{a_n}{r^n}+\dfrac{f(n)}{r^{n+1}}
\end{displaymath}

である.これから

\begin{displaymath}
\dfrac{a_n}{p^n}=\dfrac{a_1}{r}+\sum_{k=1}^{n-1}\dfrac{f(k)}{r^{k+1}}
\end{displaymath}

これを求めて,分母を払えばよい.

早苗  $a_{n+1}=2a_n+5^n$などでは, $2^{n+1}$で割らずに,$5^{n+1}$で割るのも習いました.

南海  0でない定数$p$で割って,

\begin{displaymath}
\dfrac{a_{n+1}}{p^{n+1}}
=\dfrac{r}{p}\cdot\dfrac{a_n}{p^n}+\dfrac{f(n)}{p^{n+1}}
\end{displaymath}

とし, $\dfrac{f(n)}{p^{n+1}}$が簡単になるようにできるのなら, それも一つの方法である.

早苗  $f(n)=cp^n$のような指数型のときは使えます.

例 1.1   $p$は0でなく,$r$$r \ne p$となる定数,$c$は定数とする.漸化式

\begin{displaymath}
a_{n+1}=ra_n+cp^n
\end{displaymath}

を,$a_1=a$で,3通りの方法で解け.

早苗 

解法1

$u_n=Ap^n$でできないか考えてみます.

\begin{displaymath}
Ap^{n+1}=r\cdot Ap^n+cp^n
\end{displaymath}

$p\ne 0$より

\begin{displaymath}
Ap=r\cdot A+c
\end{displaymath}

これから, $A=\dfrac{c}{p-r}$である. つまり $u_n=\dfrac{c}{p-r}p^n$は一つの解である. $u_1=\dfrac{cp}{p-r}$より,$\maru{2}$から

\begin{eqnarray*}
a_n&=&u_n+r^{n-1}(a_1-u_1)\\
&=&\dfrac{c}{p-r}p^n+r^{n-1}\lef...
...{p-r} \right)\\
&=&ar^{n-1}+cp\cdot\dfrac{p^{n-1}-r^{n-1}}{p-r}
\end{eqnarray*}

解法2

$t=p$で解法2を用いる.

$a_{n+1}=ra_n+cp^n$の両辺に$p$をかけ,$n+1$のときの漸化式から引く.

\begin{displaymath}
\begin{array}{l}
a_{n+2}=ra_{n+1}+cp^{n+1}\\
pa_{n+1}=pra_n+cp^{n+1}
\end{array}\end{displaymath}

より

\begin{displaymath}
a_{n+2}-pa_{n+1}=ra_{n+1}-pra_n=r(a_{n+1}-pa_n)
\end{displaymath}

数列 $\{a_{n+1}-pa_n\}$は公比$r$の等比数列なので,

\begin{displaymath}
a_{n+1}-pa_n=r^{n-1}(a_2-pa_1)=r^{n-1}(ra+cp-pa)=-(p-r)ar^{n-1}+cpr^{n-1}
\end{displaymath}

一方.漸化式は

\begin{displaymath}
a_{n+1}-ra_n=cp^n
\end{displaymath}

なので,辺々引いて

\begin{displaymath}
(p-r)a_n=(p-r)ar^{n-1}+cp^n-cpr^{n-1}
\end{displaymath}


\begin{displaymath}
∴\quad a_n=ar^{n-1}+cp\cdot\dfrac{p^{n-1}-r^{n-1}}{p-r}
\end{displaymath}

3項間漸化式から得られる2項間漸化式の一方がはじめの漸化式で,もう一つが新しく得られたものです.

解法3-1

漸化式の両辺を$r^{n+1}$で割る.

\begin{displaymath}
\dfrac{a_{n+1}}{r^{n+1}}=\dfrac{a_n}{r^n}+\dfrac{c}{r}\left(\dfrac{p}{r}\right)^n
\end{displaymath}

$n\ge 2$のとき

\begin{displaymath}
\dfrac{a_n}{r^n}
=\dfrac{a}{r}+\sum_{k=1}^{n-1}\dfrac{c}{r}\...
...\cdot\dfrac{\left(\dfrac{p}{r}\right)^{n-1}-1}{\dfrac{p}{r}-1}
\end{displaymath}


\begin{displaymath}
∴\quad a_n=ar^{n-1}+cp\cdot\dfrac{p^{n-1}-r^{n-1}}{p-r}
\end{displaymath}

$n=1$のときもこの式で成立する.

解法3-2

漸化式の両辺を$p^{n+1}$で割る.

\begin{displaymath}
\dfrac{a_{n+1}}{p^{n+1}}=\dfrac{r}{p}\cdot\dfrac{a_n}{p^n}+\dfrac{c}{p}
\end{displaymath}


\begin{displaymath}
\alpha=\dfrac{r}{p}\cdot\alpha+\dfrac{c}{p}
\end{displaymath}

より $\alpha=\dfrac{c}{p-r}$である.これから

\begin{displaymath}
\dfrac{a_{n+1}}{p^{n+1}}-\dfrac{c}{p-r}=\dfrac{r}{p}\left(\dfrac{a_n}{p^n}-\dfrac{c}{p-r}\right)
\end{displaymath}


\begin{displaymath}
∴\quad \dfrac{a_n}{p^n}-\dfrac{c}{p-r}
=\left(\dfrac{r}{p} \right)^{n-1}\left(\dfrac{a}{p}-\dfrac{c}{p-r} \right)
\end{displaymath}

\begin{eqnarray*}
∴\quad a_n&=&\dfrac{c}{p-r}\cdot p^n+pr^{n-1}\left(\dfrac{a}{...
...{p-r} \right)\\
&=&ar^{n-1}+cp\cdot\dfrac{p^{n-1}-r^{n-1}}{p-r}
\end{eqnarray*}

南海 このように漸化式の解法は一つではない.一つの漸化式が与えられると,その漸化式を含むより一般的な場合の考え方が適用できる.具体的な漸化式の一般化が一つではないので,それに対応していろいろな解法ができる.これからも漸化式の解法は柔軟に対応するようにしたい.


up previous
上: $a_{n+1}=ra_n+f(n)$型の漸化式 前: 漸化式とは何か
Aozora Gakuen