👋

三項間漸化式の一般項の求め方(差分方程式つまみぐい)

2022/12/24に公開

math

tech

初めに

この記事の概要

高校で学習する三項間漸化式のちょっと変わった(?)解法を紹介します。具体的には、次の漸化式で表される数列 $\{x_n\}_{n=1,2,3,...}$ の一般項を求める方法を紹介します。

x_{n + 2} + p x_{n + 1} + q x_n = 0 \quad (q \neq 0) \tag{1}

多くの高校生向けの教科書やWeb記事では、特性方程式とよばれる二次方程式 $\lambda ^2 + p\lambda + q = 0$ の解を利用して式(1)を書き換えることで一般項を求める方法が紹介されています。この解法は明快ではあります。しかし、発想にかなりの飛躍があり、納得はしても、同じ方法を使って後から自力で一般項を導出することはかなり難しいと言えます。

本記事では、できるだけ発想を飛躍させることなく、文脈に沿って一般項を求める方法を紹介します(多分)。とくに、本記事で紹介した考え方を用いることで、後からでも自力で一般項を導出することができるように意識して解説します(したい)。
また、一般項を求めるために、差分方程式の非常に基本的な概念を導入します。ちなみに筆者は完全な差分方程式にわかです。

対象読者

三項間漸化式を勉強したけど、特性方程式とか、その解を使った式変形に発想の飛躍を感じてしまっている高校生や高専生を意識した記事になっています。また、今回紹介する解法は、とある微分方程式の解法と関連があります。微分方程式を知っている読者は、本記事をより楽しめるかもしれません。

保身

本記事は、共立出版、広田良悟先生と高橋大輔先生の、『差分と超離散』という書籍のほんの一部を、数学にわかの筆者が魔翻訳し、うすめたものとなっています。誤りが含まれることが無いよう努力しましたが、厳密性は欠かれているものとしてお読みください。正確な議論が知りたい場合には、実際の書籍を確認してください。書籍へのリンクを張っておきます。

なお、筆者が本記事の作成にあたって参考にしたのは初版第7刷(2020)、p16からp26のあたりです。

準備

問題を眺める

式(1)を再掲します。

x_{n + 2} + p x_{n + 1} + q x_n = 0 \quad (q \neq 0) \tag{1}

求めたいのは、式(1)に示した漸化式を満たす数列 $\{x_n\}_{n=1,2,3,...}$ の一般項です。このような数列 $\{x_n\}_{n=1,2,3,...}$ を、式(1)の解と呼ぶことにします。
式(1)で $q \neq 0$ となっているのは、「式(1)は三項間漸化式である」という仮定があるからです。もし $q = 0$ であると、式(1)は、

x_{n + 2} + p x_{n + 1} = 0

となり、二項間漸化式となってしまいます。問題としたいのは三項間漸化式ですから、 $q \neq 0$ という仮定がおかれているわけです。
ちなみに、 $p$ は $0$ でもよいです。 $p = 0$ のとき、式(1)は、

x_{n + 2} + q x_{n} = 0

になります。こちらは先ほどの $p=0$ の場合とちがって、隣り合っていない二つの項の関係を表しています。これも三項間漸化式の一種と考えます。

解は無数にある

さて、式(1)の解を求めたいわけですから、式(1)を満たす数列の一般項を、関数 $f(n)$ を用いて、

x_n = f(n) \tag{2}

のようにあらわすことができればOKです......といいたいところですが、そう単純には行きません。
実は、式(1)は無数の解をもちます。式(1)だけでは条件が弱く、それを満たす数列が無限に出てきてしまうのです。したがって、式(2)のように、 $x_n$ を一つの関数の形で表すことはできません(表せたとしても、それは式(1)の解のうち一つを表したにすぎません)。本記事で問題にしたいのは、なんとかして、式(1)を満たすすべての解をまとめて表すことはできないか、ということです。
ところで、高校の教科書等でこの手の問題が出題される場合、式(1)とは別に、 $x_1$ と $x_2$ の値、つまり、第1項と第2項の値が制約として与えられていることが多いです(このような制約を初期条件といいます)。後で詳しく論じますが、無数にあった解は、この制約によってただ一つに絞られます。高校の教科書等では、式(1)と初期条件から、それ満たす解をいきなり求める方法が紹介されている、というわけです。
本記事では、対照的に、次のような手順で解を求めます。

式(1)を満たすすべての解をまとめてあらわす
求めた無数の解の中から、与えられた初期条件を満たす解を取り出す

本記事のメインは主に手順1の方です。手順1がわかれば、手順2はたやすく行えます。

以下では、まず手順1、すなわち、式(1)を満たすすべての解をまとめてあらわす方法を説明していきます。無限に存在する解を一挙に把握するのは、かなり難しく思えるかもしれません。この、一見困難な問題を解決するために、式(1)の解の性質について考察していきましょう。

解の持つ性質

解を一つに決めるには？

式(1)を再掲します。

x_{n + 2} + p x_{n + 1} + q x_n = 0 \quad (q \neq 0) \tag{1}

前述したとおり、式(1)は解を無数に持ちます。(1)という条件だけでは、それを満たす数列を一つに定めることができないのです。では、「式(1)を満たす」という条件のほかにどんな条件を追加すれば、その解を一つに決めることができるでしょうか。

おそらく一番簡単な方法は、第1項と第2項の値を決めてしまうことです。第1項の値 $x_1$ と、第2項の値 $x_2$ を何らかの値に決めてしまったとします。このとき、式(1)から、

x_3 = - px_2 -qx_1

のように第3項の値を決めることができます。同様に、 $x_3$ 、 $x_2$ の値と式(1)から、第4項である $x_4$ の値も決めることができます。これを繰り返せば、数列のどの項の値も求めることができます。すなわち、「 $x_1$ と $x_2$ の値が決まっている」という条件の下で、式(1)を満たす数列はただ一つに定まります。
この「 $x_1$ と $x_2$ の値が決まっている」という条件を、式(1)の初期条件といいます。初期条件を決めると式(1)の解は一つに定まる、というわけです。
今述べたことをまとめます。

初期条件( $x_1, x_2$ の値)を決めると、式(1)の解はただ一つに定まる。

ところで、わかりやすく第1項と第2項の値を決めてもよいですが、かわりに第2項と第3項の値を決めても、式(1)の解は一つに定まります。式(1)から、第1項である $x_1$ は、 $q \neq 0$ ですから、

x_1 = - \frac{1}{q}x_3 - \frac{p}{q}x_2

のように求めることができますし、第4項以降については先ほどと同様にすべての項を決めることができます。つまり、「 $x_2$ と $x_3$ の値が決まっている」という条件の下でも、式(1)を満たす数列はただ一つに定まります。同様に、第5項と第6項の値を決めたり、第1000項と第1001項の値を決めたりしても、式(1)を満たす解はただ一つに決まります。
つまり、任意の自然数 $k$ に対して、「 $x_k$ と $x_{k+1}$ の値が決まっている」という条件のもとで、式(1)の解はただ一つに定まります。
今述べたことをまとめます。

隣り合う二つの項の値( $x_k, x_{k+1}$ の値)を決めると、式(1)の解はただ一つに定まる。

ちなみに...

上記の「隣り合う」という条件は、解を一つに決めるうえで重要です。例えば $x_1$ と $x_3$ のように、隣り合っていない二つの項の値を決めたとします。このとき、 $p \neq 0$ であれば、

x_2 = -\frac{1}{p}x_3 - \frac{q}{p}x_1 \tag{3}

のように $x_2$ の値が決まり、その他の項の値も決めることができます。しかし、 $p = 0$ のときは式(3)は成立せず、 $x_2$ の値は決まりません( $x_2$ は任意の値をとれます)。つまり、隣り合っていない２つの項の値を決めても、それを満たす数列が1つに決まるとは限りません。

解の重ね合わせ

式(1)が持つもう一つの性質として、解の重ね合わせについて述べます。
何らかの方法によって、無数に存在する式(1)の解のうち、2つの解を一般項の形で表すことができたとしましょう。それぞれ $f_n, g_n$ とします。 $f_n, g_n$ は式(1)の解ですから、任意の自然数 $n$ に対して、次式が成り立ちます。

f_{n+2} + pf_{n+1} + qf_n = 0 \tag{4}

g_{n+2} + pg_{n+1} + qg_n = 0 \tag{5}

この時、次の数列 $a_n$ は、式(1)の解になります。

a_n = C_1 f_n + C_2 g_n \tag{6}

ここで、 $C_1, C_2$ は任意定数です。

実際に式(6)を式(1)に代入してみると、式(4)と式(5)に注意して、

\begin{align*} a_{n+2} &+ pa_{n+1} +qa_{n} \\ &= (C_1 f_{n+2} + C_2 g_{n+2}) + p(C_1 f_{n+1} + C_2 g_{n+1}) + q(C_1 f_n + C_2 g_n) \\ &= C_1(f_{n+2} + pf_{n+1} + qf_n) + C_2(g_{n+2} + pg_{n+1} + qg_n) \\ &= 0 \end{align*}

となりますから、確かに式(6)は式(1)の解になっています。式(6)は、式(1)の二つの解 $f_n, g_n$ を、定数倍して足し合わせたものになっています。これを解の重ね合わせといいます。
以上の議論から、式(1)の解の重ね合わせは、また式(1)の解となる、ということがわかります。

$f_n, g_n$ がそれぞれ式(1)の解であるとき、その重ね合わせ $C_1 f_n + C_2 g_n$ も式(1)の解である(ただし $C_1, C_2$ は任意定数)。

重ね合わせですべての解を表せる？

式(6)は、 $C_1, C_2$ という任意定数を含んでいます。これは、最初に挙げた「式(1)のすべての解をまとめて表示する」という目標にかなり肉薄しているように思えます。なぜなら、式(6)の任意定数の値を変化させることで、式(1)を満たす解を無数に得ることができるからです^[1]。しかし、「式(6)で式(1)の解すべてを表すことができているか」については疑問が残ります。 $C_1, C_2$ をどう選んでも得ることができない解が、まだ存在するかもしれないからです。
この可能性を否定し、「式(6)が式(1)の解すべてを表している」と結論するためには、式(1)のどんな解も式(6)の形で表せることを示す必要があります。つまり、式(1)の解すべてを、二つの解の重ね合わせ $C_1 f_n + C_2 g_n$ で表せることを示したいわけです。

式(1)の解 $x_n$ に対して、自然数 $k$ を選び、 $x_k$ と $x_{k+1}$ の値を決めたとします。前述の議論から、この条件を満たす解はただ一つに定まります。もしこの解 $x_n$ が、 $f_n, g_n$ の重ね合わせで表せるならば、次式が成り立つはずです。

\begin{equation*} \left\{ \, \begin{aligned} C_1 f_k + C_2 g_{k} &= x_k \\ C_1 f_{k+1} + C_2 g_{k+1} &= x_{k+1} \tag{7} \end{aligned} \right. \end{equation*}

式(7)は $C_1, C_2$ に対する連立一次方程式になります。もし、任意の $k, x_k, x_{k+1}$ に対して、その解 $C_1, C_2$ がただ一つに定まるなら、 $x_n$ はその解 $C_1, C_2$ によって、 $x_n = C_1 f_n + C_2 g_n$ のように、 $f_n, g_n$ の重ね合わせで表せることがわかります。
まとめると、以下のようになります。

任意の自然数 $k$ 、任意の数の組 $x_k, x_{k+1}$ に対して、 $C_1, C_2$ に関する連立一次方程式

\begin{equation*} \left\{ \, \begin{aligned} C_1 f_k + C_2 g_{k} &= x_k \\ C_1 f_{k+1} + C_2 g_{k+1} &= x_{k+1} \end{aligned} \right. \end{equation*}

が常にただ一つの解をもつような、式(1)の解 $f_n, g_n$ が見つかれば、その重ね合わせ $C_1 f_n + C_2 g_n$ は式(1)のすべての解を表す。

式(1)の2つの解 $f_n, g_n$ を使ってすべての解を表すために課された上記の条件が成り立つとき、 $f_n, g_n$ は互いに線形独立であるといいます。線形独立の定義も書いておきます。

二つの数列 $f_n, g_n$ が線形独立であるとは、
任意の自然数 $n$ 、任意の数の組 $x_k, x_{k+1}$ に対して、 $C_1, C_2$ に関する連立一次方程式

\begin{equation*} \left\{ \, \begin{aligned} C_1 f_k + C_2 g_{k} &= x_k \\ C_1 f_{k+1} + C_2 g_{k+1} &= x_{k+1} \end{aligned} \right. \end{equation*}

が常にただ一つの解をもつことである。

この定義、なかなか複雑でとらえどころがないように思えますが、あまり気にしなくてもOKです(おい)。実用上は、「二つの数列が線形独立であるとは、一方の数列が他方の定数倍でかけないこと」と思っていればOKです。
一方の数列が他方の数列の定数倍で書けたとしましょう。つまり、 $f_n = Ag_n$ が成り立っていたとしましょう。この時、式(7)は、

\begin{equation*} \left\{ \, \begin{aligned} C_1 Ag_k + C_2 g_{k} &= x_k \\ C_1 Ag_{k+1} + C_2 g_{k+1} &= x_{k+1} \end{aligned} \right. \end{equation*}

上の式に $g_{k+1}$ を、下の式に $g_k$ をかけると、

\begin{equation*} \left\{ \, \begin{aligned} C_1 Ag_k g_{k+1} + C_2 g_k g_{k+1} &= x_k g_{k+1} \\ C_1 Ag_k g_{k+1} + C_2 g_k g_{k+1} &= x_{k+1} g_k \end{aligned} \right. \end{equation*}

となり、 $x_k g_{k+1} = x_{k+1} g_k$ であれば解は無数に存在。それ以外の場合は解は存在しないことになります。いずれにしてもただ一つの解をもつことは無く、 $f_n, g_n$ は線形独立ではありません。一方が他方の定数倍となっている場合、その組は線形独立ではありません。
一方が他方の定数倍でない場合でも、線形独立でない例が存在する可能性は否定できていませんが、本記事ではそのような例は登場しないので、あまり気にする必要はありません(本当に怒られそう)。
本記事では、二つの解が本当に線形独立なのかについてはこれ以上詳しく言及しません(ごめんなさい)。

線形独立という用語を使って、先ほど導いた命題を言い換えておきます。

線形独立な数列の組 $f_n, g_n$ が式(1)の解ならば、その重ね合わせ $C_1 f_n + C_2 g_n$ は式(1)のすべての解を表す

ここまでの議論で分かったことをまとめます。

式(1)の二つの解 $f_n, g_n$ の重ね合わせによって、解を無数に作れる
特に、 $f_n, g_n$ が線形独立のとき、式(1)のすべての解を作ることができる

以上によって、線形独立な二つの解を見つけることさえできれば、式(1)のすべての解を表すことができるということがわかりました。
以下では、式(1)から、何とかして線形独立な二つの解を求められないか、考えていきます。

初期条件

線形独立な二つの解を求める方法を説明する前に、ここで、初期条件が与えられた場合に、解をどのようにして取り出すのかについて言及しておきます。
すべての解を重ね合わせによって表せたとします。

x_n = C_1 f_n + C_2 g_n

この式で表されている無数の解のうち、ある初期条件を満たすものを取り出すには、上式の $n$ に1と2を代入した式を立て、その式から $C_1, C_2$ を決めてやればよいです。

\begin{equation*} \left\{ \, \begin{aligned} C_1 f_1 + C_2 g_1 &= x_1 \\ C_1 f_2 + C_2 g_2 &= x_2 \end{aligned} \right. \end{equation*}

この式は $C_1, C_2$ に関する連立方程式であり、 $f_n, g_n$ が線形独立であることから、これを満たす解はただ一つのみです。これによって、任意定数である $C_1, C_2$ の値が決定され、無数の解から初期条件を満たす解が取り出せたというわけです。

それではいよいよ、線形独立な二つの解を求める方法について説明していきます。

線形独立な解を求める

式(1)を再掲します。

x_{n + 2} + p x_{n + 1} + q x_n = 0 \quad (q \neq 0) \tag{1}

やりたいことは、この式を満たす二つの線形独立な解を見つけることです。
どんな手を使ってもいいので、線形独立な解が二つ見つかれば勝ちです。なぜならその二つを重ね合わせが、式(1)を満たすすべての解を表すからです。
とにかく二つの解を見つければよいわけなので、こんな予想を立ててみます。

式(1)の解には、等比数列が含まれる

この時点では、あくまで予想でしかありません。しかし、もしこの予想が正しければ、2つの解を見つける上で大きな一歩になります。とにかくやってみましょう。
式(1)が公比 $\lambda$ の数列 $x_n = \lambda^n$ を解に持つと仮定します。ここで、 $\lambda = 0$ の場合はただ $0$ が続いていくだけの数列なので、これは除いておきます。すなわち、 $\lambda \neq 0$ としておきます。これを式(1)に代入してみます。

\lambda^{n+2} + p \lambda^{n+1} + q \lambda^n = 0

先ほど $\lambda \neq 0$ という制約を課しておいたので、両辺を $\lambda^n$ で割れます。すると、次のような $\lambda$ に関する2次方程式が出てきます。

\lambda^2 + p \lambda + q = 0

この式こそが、いわゆる特性方程式です。特性方程式は、線形独立な二つの解を求める過程で、解を等比数列と仮定したときにあらわれる二次方程式のことであったわけです。
この二次方程式を満たす $\lambda$ に対して、数列 $x_n = \lambda^n$ とすると、この数列は式(1)の解になります。うまい具合に式(1)の解を見つけられそうです。早速この二次方程式を解きましょう。特性方程式の判別式の値によって場合分けします。

特性方程式が二つの異なる実数解をもつ場合

特性方程式が二つの異なる実数解をもつ場合、すなわち、 $p^2 - 4q > 0$ の場合から考えていきます。特性方程式の二つの解を $\alpha, \beta$ とおくと $f_n = \alpha^n$ 、 $g_n = \beta^n$ は、どちらも式(1)の解となっています。さらに、 $\alpha \neq \beta$ ですから、 $f_n, g_n$ は線形独立です。以上より、式(1)のすべての解は、次のように表すことができます。

x_n = C_1 \alpha^n + C_2 \beta^n

特性方程式が二つの異なる複素数解をもつ場合

特性方程式が二つの異なる複素数解をもつ場合、すなわち、 $p^2 - 4q < 0$ の場合を考えます。二次方程式の二つの複素数解は、互いに共役の関係にあるので、それぞれ $\lambda_1 + i\lambda_2$ 、 $\lambda_1 - i \lambda_2$ とおけます。当然、 $f_n = (\lambda_1 + i\lambda_2)^n$ 、 $g_n = (\lambda_1 - i \lambda_2)^n$ はそれぞれ式(1)の解です。また、 $f_n, g_n$ は線形独立です。先ほどと同様に、このまま、すべての解は

x_n = C_1 (\lambda_1 + i\lambda_2)^n + C_2 (\lambda_1 - i\lambda_2)^n

である、としてもよいですが、もう少し変形してきれいに表すことができます。

$\lambda_1 \plusmn i \lambda_2$ を、極形式で表示します。つまり、動径の大きさ $r$ と、偏角 $\theta$ により、

\lambda_1 \plusmn \lambda_2 = re^{\plusmn i\theta}

と書き換えます。この書き換えにより、

f_n = r^n e^{in\theta}, \quad g_n = r^n e^{-in\theta}

となります。ここで、二つの解の重ね合わせは、また解であることから、次の $f'_n, g'_n$ も解となります。

f'_n = \frac{f_n + g_n}{2} = r^n \frac{e^{in\theta} + e^{-in\theta}}{2} = r^n \cos(n\theta)

g'_n = \frac{f_n - g_n}{2i} = r^n \frac{e^{in\theta} - e^{-in\theta}}{2i} = r^n \sin(n\theta)

相変わらず、 $f'_n, g'_n$ は線形独立です。最後に、 $f'_n, g'_n$ を重ね合わせて、すべての解を表します。

x_n = r^n \{C_1 \cos(n\theta) + C_2 \sin(n\theta)\}

特性方程式が重解を持つ場合

特性方程式が重解を持つ場合、すなわち $p^2 - 4q = 0$ のときについて考えます。
特性方程式の解は $-\frac{p}{2}$ であり、 $f_n = (-\frac{p}{2})^n$ は式(1)の解です。
この場合が厄介です。特性方程式を用いて得られた解が一つのみで、重ね合わせを作るためには、少なくとももう一つ解が(しかも線形独立な解が)必要になるからです。
もう一つの解を求めるために、次のような予想をします(かなり脈絡がないです、ゆるして)。

式(1)が $g_n = C_n f_n = C_n (-\frac{p}{2})^n$ という形の解を持つ

もう一つの解は $f_n$ と似た形をしていて、 $C_n$ という何か別の数列を $f_n$ にかけることで作れる、と予想するわけです。
この予想を満たす( $g_n$ が $f_n$ と線形独立になる) $C_n$ が一つでも見つかれば、重ね合わせによりすべての解を表せます。

$g_n$ を式(1)に代入してみます。

C_{n+2} (-\frac{p}{2})^{n+2} + p C_{n+1} (-\frac{p}{2})^{n+1} + q C_n (-\frac{p}{2})^n = 0

重解の条件から、 $p^2 = 4q$ であることに注意して、

q C_{n+2}(-\frac{p}{2})^n - 2q C_{n+1} (-\frac{p}{2})^n + q C_n(-\frac{p}{2})^n = 0

$p^2 = 4q$ であるから、 $q \neq 0$ より、 $p \neq 0$ である。よって、両辺を $q, (-\frac{p}{2})^n$ で割ると、

C_{n+2} - 2C_{n+1} + C_n = 0

この式は、次のように書き換えられます。

C_{n+1} = \frac{C_n + C_{n + 2}}{2} \tag{8}

さて、この式を満たす $C_n$ が、一つでも見つかればOKです。
式(8)は、すべての項 $C_{n+1}$ について、その値が、両隣 $C_n, C_{n+2}$ の平均( $\frac{C_n + C_{n+2}}{2}$ )に等しいことを表すと解釈できます。このような制約を満たす $C_n$ には、例えば

C_n = n \tag{9}

といったものがあります。式(9)を式(8)に代入すると左辺は $n+1$ 、右辺は $\frac{n + n + 2}{2} = \frac{2(n + 1)}{2} = n + 1$ となるので、確かに式(9)は式(8)を満たします。
以上より、 $g_n = n f_n = n (-\frac{p}{2})^n$ は式(1)の解となります。また、 $f_n, g_n$ は線形独立です。これにより、

x_n = C_1 g_n + C_2 f_n = (C_1 n + C_2)(-\frac{p}{2})^n

と、すべての解を表すことができます。

まとめ

ごちゃごちゃしてしまいましたが、最後にまとめます。
本記事で紹介したのは次のような三項間漸化式の解を求める方法です。

x_{n + 2} + p x_{n + 1} + q x_n = 0 \quad (q \neq 0) \tag{1}

この漸化式は解を無数に持ちますが、そのすべての解を、線形独立な二つの解の重ね合わせで表すことができるのでした。
線形独立な二つの解を見つけるために、式(1)が等比数列の形の解 $x_n = \lambda^n, (\lambda \neq 0)$ をもつと予想し、式(1)に代入すると特性方程式が得られます。
特性方程式の判別式に応じて場合分けしながら線形独立な二つの解を導出し、重ね合わせます。
最終的な解は、

特性方程式が二つの異なる実数解をもつ場合
- 解は $x_n = C_1 \alpha^n + C_2 \beta^n$
- $\alpha, \betaは$ 特性方程式の解
特性方程式が重解を持つ場合
- 解は $x_n = (C_1 n + C_2)(-\frac{p}{2})^n$
特性方程式が二つの異なる複素数解をもつ場合
- 解は $x_n = r^n \{C_1 \cos(n\theta) + C_2 \sin(n\theta)\}$
- $r$ は解の動径の大きさ, $\theta$ は虚部が正の方の解の偏角

となります。

最後に

いかがだったでしょうか。
後半の方は急いで書き上げてしまったこともあり、かなり説明が雑になってしまったように思います。もっとわかりやすく説明できたと思うのに......反省が多いです。精進します。
ちなみに本記事は、こちらのアドベントカレンダーとして作成しました。良ければほかの記事も参照ください。

https://adventar.org/calendars/7912

脚注

$f_n, g_n$ の選び方によっては、解を無数に得ることができない場合もあり得ます。例えば $f_n = 0, g_n = 0$ はどちらも式(1)の解ですが、その重ね合わせは $x_n=0$ にしかなりません。 ↩︎

GitHubで編集を提案

Discussion

ログインするとコメントできます