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

の解法

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

もちろんその他にも

$$a_{n+1}=\dfrac{n+1}{n+2}a_n$$

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

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

$$a_{n+1}=ra_n+f(n)\quad \cdots\maru{1}$$

と表せるものだ．

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

早苗　 $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$のとき

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

です．

南海　 以上の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)$を満たす数列，

つまり

$$u_{n+1}=ru_n+f(n)$$

となる数列$\{u_n\}$を何らかの方法で 見つけるのだ．

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

$$a_{n+1}-u_{n+1}=r(a_n-u_n)$$

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

$$a_n-u_n=r^{n-1}(a_1-u_1)$$

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

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

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

早苗　 これは教科書では，

$$\alpha=3\alpha+2$$

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

$$a_{n+1}+1=3(a_n+1)$$

と変形します．

南海　 これがまさに，解法1なのだ．

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

南海　 そうなのだ．

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

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

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

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

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

とおき，

$$g(n+1)=rg(n)+f(n)$$

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

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

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

解法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)$とし，辺々引くと

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

これから

$$a_{n+2}-(t+r) a_{n+1}+t ra_n=f(n+1)-t f(n)$$

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

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

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

$$f(n+1)-t f(n)=2-2t$$

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

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

$$a_{n+2}-a_{n+1}=3(a_{n+1}-a_n)$$

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

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

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

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

$$\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$次多項式のときにも有効だ．

$$f(n+1)-f(n)$$

は$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}$ で割る．

$$\dfrac{a_{n+1}}{r^{n+1}}=\dfrac{a_n}{r^n}+\dfrac{f(n)}{r^{n+1}}$$

である．これから

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

これを求めて，分母を払えばよい．

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

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

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

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

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

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

$$a_{n+1}=ra_n+cp^n$$

を，$a_1=a$で，3通りの方法で解け．

早苗　

解法1

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

$$Ap^{n+1}=r\cdot Ap^n+cp^n$$

$p\ne 0$より

$$Ap=r\cdot A+c$$

これから， $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{array}{l} a_{n+2}=ra_{n+1}+cp^{n+1}\\ pa_{n+1}=pra_n+cp^{n+1} \end{array}$$

より

$$a_{n+2}-pa_{n+1}=ra_{n+1}-pra_n=r(a_{n+1}-pa_n)$$

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

$$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}$$

一方．漸化式は

$$a_{n+1}-ra_n=cp^n$$

なので，辺々引いて

$$(p-r)a_n=(p-r)ar^{n-1}+cp^n-cpr^{n-1}$$

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

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

解法3-1

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

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

$n\ge 2$のとき

$$\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}$$

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

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

解法3-2

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

$$\dfrac{a_{n+1}}{p^{n+1}}=\dfrac{r}{p}\cdot\dfrac{a_n}{p^n}+\dfrac{c}{p}$$

$$\alpha=\dfrac{r}{p}\cdot\alpha+\dfrac{c}{p}$$

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

$$\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)$$

$$∴\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)$$

$$\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*}$$

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

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