特性方程式を用いた漸化式の解法の原理

証明する内容

$p$、$q$ を定数($p\neq1$)とする漸化式

$ a_{n+1} = p\,a_n+q \quad \cdots (\ast) $

で定められる数列 $\{a_n\}$ を考えます。この形の漸化式は、$q=0$ なら公比 $p$ の等比数列そのものですが、$q\neq0$ の場合はこのままでは等比数列になりません。

そこで、$x$ の方程式

$ x = px+q \quad \cdots (\ast\ast) $

(これを特性方程式と呼びます)の解を $\alpha$ とすると、もとの漸化式 $(\ast)$ が、次の形に変形できることを証明します。

$ a_{n+1}-\alpha = p\,(a_n-\alpha) $

さらに、この変形によって、数列 $\{a_n-\alpha\}$ が公比 $p$ の等比数列になること、したがって、もとの数列 $\{a_n\}$ の一般項が求められることを説明します。

証明

ステップ1:特性方程式が、ただ1つの解を持つことを確認する

まず、特性方程式 $x=px+q$ を、$x$ について実際に解いてみます。右辺の $px$ を左辺に移項します。

$ x-px = q $

左辺を $x$ でくくります。

$ (1-p)x = q $

ここで、仮定より $p\neq1$ なので $1-p\neq0$ です。したがって、両辺を $1-p$ で割ることができ、

$ x = \frac{q}{1-p} $

という、ただ1つの解が必ず存在します。この解を $\alpha$ とおきます。

$ \alpha = \frac{q}{1-p} \quad \left(\text{すなわち} \ \alpha=p\alpha+q \ \text{を満たす}\right) $

($p=1$ の場合は $(1-p)x=q$ が $0\times x=q$ となってしまい、$q\neq0$ なら解なし、$q=0$ ならすべての $x$ が解になってしまうため、$\alpha$ がただ1つに決まりません。$p\neq1$ という条件が、この証明全体で本質的に重要であることが分かります。)

ステップ2:もとの漸化式から特性方程式を辺々引く

ここからが証明の中心です。もとの漸化式 $(\ast)$ と、特性方程式 $(\ast\ast)$ を、もう一度並べて書きます。

$ a_{n+1} = p\,a_n+q \quad \cdots (\ast) $

$ \alpha = p\,\alpha+q \quad \cdots (\ast\ast) $

この2つの式は、どちらも「(左辺) $=p\times$(何か)$+q$」という、まったく同じ形をしています。そこで、$(\ast)$ から $(\ast\ast)$ を、左辺どうし・右辺どうし、それぞれ引き算します。

$ a_{n+1}-\alpha = (p\,a_n+q)-(p\,\alpha+q) $

右辺のかっこを外し、整理します。

$ a_{n+1}-\alpha = p\,a_n+q-p\,\alpha-q $

右辺の $+q$ と $-q$ が打ち消し合って消えます。

$ a_{n+1}-\alpha = p\,a_n-p\,\alpha $

右辺を $p$ でくくります。

$ a_{n+1}-\alpha = p\,(a_n-\alpha) $

これで、目標としていた変形

$ a_{n+1}-\alpha = p\,(a_n-\alpha) $

が、単に「2つの式を辺々引き算する」というだけの操作で確かに得られることが確認できました。

ステップ3:なぜ「引き算する」という発想でうまくいくのか

ステップ2の計算は機械的にはできますが、なぜ「特性方程式を辺々引く」という発想がそもそも効果的なのか、その理由を確認しておきます。

特性方程式 $\alpha=p\alpha+q$ は、「もし数列のある項がすでに $\alpha$ という値になっていたら、次の項も同じ $\alpha$ のままである」という状況を表す式です。つまり $\alpha$ は、この漸化式にとっての**動かない点(不動点)**にあたります。

もとの漸化式 $a_{n+1}=pa_n+q$ を、$a_n$ を「$\alpha$ からのズレ」の形、つまり $a_n=\alpha+(a_n-\alpha)$ と考えて代入してみると、

$ a_{n+1} = p\bigl(\alpha+(a_n-\alpha)\bigr)+q = (p\alpha+q)+p(a_n-\alpha) = \alpha+p(a_n-\alpha) $

(最後の変形で、特性方程式より $p\alpha+q=\alpha$ であることを使いました。)これは、

$ a_{n+1}-\alpha = p(a_n-\alpha) $

と同じ式です。この計算から分かるように、$q$ という定数項は、実は「数列全体を $\alpha$ だけずらす」ための情報を持っていたにすぎません。$\alpha$ を基準点に選んで「$\alpha$ からのズレ」だけに注目すると、そのズレは常に $p$ 倍されるだけの、定数項のないシンプルな関係になるのです。これが、特性方程式の解 $\alpha$ を引くという操作が意味を持つ理由です。

ステップ4:$\{a_n-\alpha\}$ が等比数列になることを確認する

ステップ2で示した関係式

$ a_{n+1}-\alpha = p\,(a_n-\alpha) $

に注目します。ここで、新しい数列 $\{b_n\}$ を、

$ b_n = a_n-\alpha $

と定義します。この定義を上の関係式に代入すると、

$ b_{n+1} = p\,b_n $

という式が得られます。これは、「数列 $\{b_n\}$ の隣り合う項の比 $\dfrac{b_{n+1}}{b_n}$ が、常に一定の値 $p$ である」ということを表す式にほかならず、等比数列の定義(隣り合う項の比が一定)そのものです。したがって、$\{b_n\}$ は初項 $b_1=a_1-\alpha$、公比 $p$ の等比数列であることが分かります。

ステップ5:等比数列の一般項の公式から $\{a_n\}$ の一般項を求める

$\{b_n\}$ が初項 $b_1=a_1-\alpha$、公比 $p$ の等比数列であることが分かったので、等比数列の一般項の公式 $b_n=b_1\,p^{\,n-1}$ を使うと、

$ b_n = (a_1-\alpha)\,p^{\,n-1} $

$b_n=a_n-\alpha$ という定義に戻すと、

$ a_n-\alpha = (a_1-\alpha)\,p^{\,n-1} $

両辺に $\alpha$ を加えると、

$ a_n = \alpha+(a_1-\alpha)\,p^{\,n-1} $

これが、漸化式 $a_{n+1}=pa_n+q$($p\neq1$)で定められる数列 $\{a_n\}$ の一般項の公式です。以上より、この形の漸化式が、特性方程式の解 $\alpha$ を使うことで、確かに等比数列の問題に帰着できることが証明されました。

この証明のポイント

この証明の核心は、「$a_{n+1}=pa_n+q$ という定数項 $q$ 付きの関係式から、定数項のない $b_{n+1}=pb_n$ という関係式を作り出すには、両辺から同じ定数($\alpha$)を引けばよい」という発想です。そして、その「同じ定数」として、ちょうど都合よく定数項が消えてくれる値こそが、特性方程式 $\alpha=p\alpha+q$ の解、すなわち「代入しても変化しない値(不動点)」なのです。この「複雑な漸化式から、不動点(または基準となる特別な値)を引き算することで、見通しのよい単純な形に帰着させる」という考え方は、より複雑な漸化式(たとえば $a_{n+1}=pa_n+f(n)$ の形)を解くときにも応用される、漸化式全般に通じる重要な発想です。