定義

通常使われるような定義は次のような形。

定義 definition.

n ∈ N に対し, 式 f(x) が存在して, 数列 {an} が

an = f(an-1), n > 1

と書かれるとき, これを {an} の満たす漸化式 recursive formulae, recurrent formulae という。

最も一般的にすると, n 個の変数 x0, x1, ..., xn-1 に関する式 fn(x0, x1, ..., xn-1) が n 毎に定まって,

an = fn(n, a1, a2, ..., an-1), n > 1

と書かれるときに, この式のことを {an} の満たす漸化式という, ということになる。 しかしこれは一寸難しいかもしれない。

このような式は, もう何度も見ているであろう。 それも含めて, 幾つか例を挙げよう。

例:

  1. an = an-1 + d: A.P.
  2. an = 2an-1 - an-2: A.P.
  3. an = ran-1: G.P.
  4. an = an-12/an-2: G.P.
  5. an = an-1 + an-2: Fibonacci (Leonardo da Pisa, 1175? -- 1250?) & E. Lucas (1842 -- 1891).
  6. an = 3an-1 + 2n.
  7. an = 2an-1 + 4n2 - 1.
  8. an = (an-1 + 4/an-1)/2.
  9. an = 2an-1 + bn-2
    bn = an-1 + 2bn-2

数列から漸化式を作るのではなく, 逆に数列 {an} の満たすべき漸化式が先に与えられており, 最初の数項, つまり a1 の値, a2 の値, ... が与えられていれば, その漸化式と与えられた数値によって, 数列 {an} を決定することが出来る。

定義

数列 {an} を漸化式 an = f(an-1), n > 1 と最初の数項 (この場合は初項のみ) によって定義するとき, この数列の定義の仕方を帰納的定義 inductive definition 又は再帰的定義 recursive definition という。 更にこのとき与えた最初の数項の値をこの漸化式の初期条件 initial condition という。

既に再帰的定義は, Σの定義, 階乗の定義, 二項係数で現れている。

漸化式とは, 漸 (ようや) く化ける式, つまり段々と変化していく式, という意味であろう。 勿論変化していくのは式そのものではなくて, 数列の項 an である。

従って原理的には, 漸化式と初期条件が適当に与えられれば, 与えられた n に対して, 第 n 項 an は高々 n 回の操作で求めることが出来る。 例えば上記の例 8 に於いて a1 = 3 と置くと
a2 = (3 + 3/4)/2 = 13/6 (= 2.166666...),
a3 = (13/6 + 4×6/13)/2 = 313/156 (= 2.00641025641025...),
a3 = (313/156 + 4×156/313)/2 = 195313/97656 (= 2.00001024002621446710903579913165....),
............

(段々 2 に近付いているのは偶然ではない).

しかし, 一般には我々が知りたいのは第 n 項 an そのものであって, その途中の項は別に分からなくても良い。 そこで, 漸化式によって間接的 implicit に定義された数列 {an} の一般項 an を, n だけの式で直接的 explicit に書き表すことを考える。

定義

漸化式 an = f(an-1), n > 1 から, 一般項 an が an = g(n) となるような n だけの式 g(n) を求めることを, その漸化式を解く solve といい, その式 an = g(n) を最初の漸化式の解 solution という。

例:

上記の例 1, 2 の解は an = a1 + (n - 1)(a2 - a1), d = a2 - a1.

3, 4 の解は an = a1・(a2/a1)n-1, r = a2/a1.

5 の解: an = ((a2 - (1-√5)a1/2)((1+√5)/2)n-1 - (a2 - (1+√5)a1/2)((1-√5)/2)n-1)/√5.

6 の解: an = (4 + a1)・3n-1 - 2n+1.

7 の解: an = (a1 + 25)・2n-1 -4n2 - 8n - 13.

8 の解: .

9 の解:
an = ((a1 + b1)・3n-1 + a1 - b1)/2,
bn = ((a1 + b1)・3n-1 - a1 + b1))/2.

問: 以上が解であることを数学的帰納法によって証明せよ。 但し, 2, 4, 5 では n ≧ 3, それ以外では n ≧ 2 でしか漸化式は意味を持っていないので, 例えば 1 では n = 2 としてもとの漸化式そのものになるところから始める。 (n ≧ 3 ではn = 3 から).

さて, 上述のように, 漸化式とその解が与えられていれば, それが解であることは帰納法で証明できる。 ではどうやってその解自体を求めたらよいだろうか。

一つは一般項を推定して, 数学的帰納法によって解であることを示す方法である。 中にはこれでしか解けないものもある。 例えば

a1 = 1, Σk=1n akak+1 = 2Σk=1n akan+1-k.

この解は an = n になる。 (帰納法の仮定としては k ≦ n での成立を仮定する) [大阪市立大 1988 理・工・医。 但しもとの問題は 「an = n を数学的帰納法によって示せ」] しかし一般にはこの方法では予想を立てるのが大変であるばかりでなく, 証明も面倒である。

もう一つは既知の数列への還元 reduction である。 これから扱うのは 「等比数列, 等差数列への還元」 である。

しかし勿論, この方法で全ての数列が解けるわけではない。

例えば 1988 鹿児島大学の理・工・医 の問題 a1 = 2, an+1 = an2 - an + 1 や, a1 = √2, .

後者では tower a↑n = an, a↑m1 = a↑m-1a, a↑mn = a↑m-1(a↑m(n - 1)) というものや, Ackermann (アッカーマン) 函数 ak(a, b, 0) = a + b, ak(a, b, 1) = ab, ak(a, b, 2) = ab, c ≧ 2 に対し ak(a, 0, c+1) = a, ak(a, b+1, c+1) = ak(a, ak(a, b, c+1), c) によって an = (√2)↑2n = ak(√2, n, 3) と書けるが, これは唯単に新しい書き方を提唱したに過ぎない。

又, まったく解かれていない数列に, Hochstadter (ホフスタッター) 数列というのがあり, これは Doublas R. Hochstadter の本 Gödel, Escher, Bach: an Eternal Golden Brade の Part 1 GEB Chapt. V: Recursive Structures and Processes. A Chaotic Sequence というのに出て来るもので

a1 = a2 = 1, , n > 2

(見にくいので an = a(n) と書くと a(n) = a(n - a(n-1)) + a(n - a(n-2))) というものである。 どうやら Fibonacci 列の数の周りをうろうろしているらしい。 が一般項については不明である。

次へ
漸化式の目次へ