👋

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

2022/12/23に公開約12,400字

初めに

この記事の概要

高校で学習する三項間漸化式のちょっと変わった(?)解法を紹介します。具体的には、次の漸化式で表される数列\{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)を書き換えることで一般項を求める方法が紹介されています。この解法は明快ではあります。しかし、発想にかなりの飛躍があり、納得はしても、同じ方法を使って後から自力で一般項を導出することはかなり難しいと言えます。

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

対象読者

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

保身

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

https://www.kyoritsu-pub.co.jp/book/b10011204.html

なお、筆者が本記事の作成にあたって参考にしたのは初版第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という仮定がおかれているわけです。
ちなみに、p0でもよいです。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_1x_2の値、つまり、第1項と第2項の値が制約として与えられていることが多いです(このような制約を初期条件といいます)。後で詳しく論じますが、無数にあった解は、この制約によってただ一つに絞られます。高校の教科書等では、式(1)と初期条件から、それ満たす解をいきなり求める方法が紹介されている、というわけです。
本記事では、対照的に、次のような手順で解を求めます。

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

本記事のメインは主に手順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_3x_2の値と式(1)から、第4項であるx_4の値も決めることができます。これを繰り返せば、数列のどの項の値も求めることができます。すなわち、「x_1x_2の値が決まっている」という条件の下で、式(1)を満たす数列はただ一つに定まります。
この「x_1x_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_2x_3の値が決まっている」という条件の下でも、式(1)を満たす数列はただ一つに定まります。同様に、第5項と第6項の値を決めたり、第1000項と第1001項の値を決めたりしても、式(1)を満たす解はただ一つに決まります。
つまり、任意の自然数kに対して、「x_kx_{k+1}の値が決まっている」という条件のもとで、式(1)の解はただ一つに定まります。
今述べたことをまとめます。


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


ちなみに...

上記の「隣り合う」という条件は、解を一つに決めるうえで重要です。例えばx_1x_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は任意の値をとれます)。つまり、隣り合っていない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_kx_{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. 式(1)の二つの解f_n, g_nの重ね合わせによって、解を無数に作れる
  2. 特に、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^ng_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)^ng_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_nf_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

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

GitHubで編集を提案

Discussion

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