2014/04/28

f(n)を含む二項間漸化式の2通りの解き方

分野: 数列  レベル: 入試対策

$f(n)$ が多項式のとき二項間漸化式
$a_{n+1}=pa_n+f(n)$
を解く方法を2通り紹介します。2つ目の方法「一般項を予想する」というのが計算量が少ないのでオススメです!

$f(n)$ が定数とのき

$f(n)=q$ (定数)のときは $a_{n+1}=pa_n+q$ となり教科書に最初に登場する最も有名な漸化式です。 $f(n)$ が一般的な場合の議論に入る前に確認しておきます。
$p=1$ だとただの等差数列になりつまらないので $p\neq 1$ とします。

例えば,漸化式 $a_1=1, a_{n+1}=2a_n+3$ は特性方程式を用いて以下のように一般項を求めることができます:

特性方程式 $\alpha=2\alpha+3$ の解は $\alpha=-3$ であり,もとの漸化式と特性方程式を辺々引くと,$a_{n+1}+3=2(a_{n}+3)$
よって,数列 $a_{n}+3$ は初項 $1+3=4$ 公比 $2$ の等比数列なので,
$a_n+3=4\cdot 2^{n-1}$
よって,$a_n=2^{n+1}-3$

ここで,$a_1=1,a_2=5$ となることを確認しておきます。(漸化式の問題では必ず $n=1,2$ を代入して検算する)

それでは,これをふまえて一般の $f(n)$ の場合をやってみます。

漸化式の解き方1:階差を $d$ 回取る方法

多項式 $f(n)$ の次数を $d$ とおきます。 $d=1$ の場合が頻出で,$d=2$ は稀に出題されます。 $d\geq 3$ は見たことがありません。

$a_{n+1}=pa_n+f(n)$ は $d$ 回階差を取ることによって上記の「 $f(n)$ が定数の場合」に帰着できる

頻出の形なので $d=1$ の場合をやってみます。 $d\geq 2$ の場合も同様の手順を繰り返すだけです。

$a_1=1,a_{n+1}=2a_n+3n-3$

与えられた漸化式と,$n→n+1$ としたもの:$a_{n+2}=2a_{n+1}+3(n+1)-3$ の差を取ると,$a_{n+2}-a_{n+1}=2(a_{n+1}-a_n)+3$
ここで,$a_{n+1}-a_{n}=b_{n}$ とおくと,
$b_{n+1}=2b_n+3,b_1=a_2-a_1=2-1=1$ となり,これは先ほど解いた:
$b_{n}=2^{n+1}-3$
よって,階差数列が求まったので一般項も求まる:
$a_n=a_1+\displaystyle\sum_{k=1}^{n-1}b_k\\
=1-3(n-1)+\displaystyle\sum_{k=1}^{n-1}2^{k+1}\\
=-3n+4+4(2^{n-1}-1)\\
=2^{n+1}-3n$

階差を $d$ 回取るということはシグマ計算を $d$ 回やらないといけないわけで計算がめんどくさいです。センター試験はめんどくさい計算をさせるのが好きなので $d=2$ くらいなら誘導つきで出題してくるかもしれません。

漸化式の解き方2:予想して係数比較

長らくおまたせ致しましたm(__)m いよいよ本題です。
$p=1$ のときはただの階差数列になってつまらないので $p\neq 1$ の場合を考えます。

$a_{n+1}=pa_n+f(n)$ の一般項は,$a_n=Ap^n+g(n)$ (ただし,$A$ は定数で $g(n)$ は $d$ 次多項式)と表せるので,$A$ と $g(n)$ を係数比較により求めて,その式が漸化式を満たすことを示せば良い

解き方1よりも少ない計算量で一般項を求めることができます!

$a_1=1,a_{n+1}=2a_n+3n-3$

一般項を $a_n=A\cdot 2^n+Bn+C$ と予想する,
漸化式を満たす
⇔ $A\cdot 2^{n+1}+B(n+1)+C=2(A\cdot 2^{n}+Bn+C)+3n-3$
⇔ $B=2B+3$ かつ $B+C=2C-3$
⇔ $B=-3,C=0$
よって,$a_n=A\cdot 2^n-3n$ が漸化式の解となるが,初期条件 $a_1=1$ より $A=2$ となるので求める一般項は
$a_n=2^{n+1}-3n$

この「予想して係数比較」というのは漸化式の多くの問題で有効です。例えば,→三項間漸化式の3通りの解き方
定番の漸化式に関しては解の一般的な構造を覚えておくとよいでしょう。

予想する部分は少し天下り的ですが解き方2の方が断然楽ですね

Tag: 漸化式の解き方と応用例まとめ

分野: 数列  レベル: 入試対策