実現したいこと

今回はC言語で漸化式と解く.

この記事に掲載してあるソースコードは私のGitHubからダウンロードできます.
必要に応じて活用してください.

漸化式とは

Wikipediaに漸化式について次のように書かれている.

数学における漸化式（ぜんかしき、英: recurrence relation; 再帰関係式）は、各項がそれ以前の項の関数として定まるという意味で数列を再帰的に定める等式である。

数学の学問的な範囲でいうならば,高校数学Bの「数列」の範囲で扱うことになるので,知っている人も多いかと思う.

漸化式の２つの顔

漸化式は引用にも示したような,再帰的な方程式を用いて一意的に定義することができる.
しかし,特別な漸化式において「一般項」というものが存在する.ただし,全ての漸化式においてこの一般項を定義したり求めることができるというわけではない.

基本的な漸化式

以下, $n \in N$ とする.

一般項が簡単にもとまるという点で,高校数学でも扱う基本的な漸化式は次の３パターンが存在する

等差数列の漸化式
等比数列の漸化式
階差数列の漸化式

それぞれの漸化式について順に書きたいと思います.

等差数列の漸化式

等差数列の漸化式は以下のような形をしています.

a_{n + 1} - a_{n} = d (d は 定 数)

これは等差数列の漸化式でありながら,等差数列の定義でもある.
この数列の一般項は次ののようになる.

初項 $a_{1}$ , 公差 $d$ の等差数列 $a_{n}$ の一般項は

a_{n} = a_{1} + (n - 1) d

もし余裕があれば,証明を自分で確認して欲しい.

等比数列の漸化式

等比数列の漸化式は

a_{n + 1} = r a_{n} (r は 定 数)

等差数列同様,これが等比数列の定義式でもある.一般に

r \neq 0, 1

を除く.もちろん,それらの場合でも等比数列といってもいいかもしれないが,初項を

a_{1}

に対して,漸化式から

r = 0

の場合,

a_{1}, 0, 0, \dots

のように第２項以降が0になってしまうため,わざわざ,等比数列であると認識しなくてもよいかもしれない.

$r = 1$ の場合,

a_{1}, a_{1}, a_{1}, \dots

なので,定数列となる.これは等比数列の特殊な場合と捉えるのが妥当かもしれない.

とにかく先に進もう.

ここで等比数列の一般項は
初項 $a_{1}$ , 公比 $r$ の等比数列 $a_{n}$ の一般項は

a_{n} = a_{1} r^{n - 1}

である.これも自分で証明を確認されたい.

階差数列の漸化式

階差数列の定義は,数列 ${a_{n}}$ に対して隣り合う２つの項の差

b_{n} = a_{n + 1} - a_{n}

を項とする数列 ${b_{n}}$ を数列 ${a_{n}}$ の階差数列と定義する.

階差数列の漸化式は, $f (n)$ を階差数列の一般項として,次のような形で表される.

a_{n + 1} = a_{n} + f (n)

そして階差数列の一般項は

a_{n} = {\begin{cases} a_{1} & (n = 1) \\ a_{1} + \sum_{k = 1}^{n - 1} b_{k} & (n ≧ 2) \end{cases}

となる.

これも証明を確認しよう.

ここまで基本的な漸化式を紹介してきたが,これらをあえて数値解析で扱いたいと思う.

基本的な漸化式の数値解析

等差数列

次のような等差数列の $a_{100}$ を求めよ.

{a_{n}} : 1, 5, 9, 13, \dots

ここではあえて一般項を用いず,ひたすら漸化式で第１００項まで計算することにします.

tousa/iterative.c

#include <stdio.h>

#define N 100

int main(void)
{
    int an;

    an = 1; // 初項
    for (int n = 1; n <= N; n++)
    {
        printf("a[%d] = %d\n", n, an);
        an = an + 4;
    }
    return 0;
}

実行結果(一部)は次のようになる.

result

a[95] = 377
a[96] = 381
a[97] = 385
a[98] = 389
a[99] = 393
a[100] = 397

一般項の公式から求めても $a_{100} = 397$ なので正しく実行できていることがわかる.

実行結果としてはうまく行っているのでこれで終わりとしてもよいがこれではあまり面白くない.

というのも,漸化式そのものが再帰的なものなので,再帰関数でこれを扱いたい.

再帰（さいき）は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。

引用: Wikipedia 再帰関数

実際に再帰関数化したものは次のようになる.

tousa/recursive.c

#include <stdio.h>

#define N 100

/* プロトタイプ宣言 */
int an(int n);

int main(void)
{
    for (int n = 1; n <= N; n++)
        printf("a[%d] = %d\n", n, an(n));
    return 0;
}

/* 漸化式(再帰関数) */
int an(int n)
{
    if (n == 1)
        return 1;
    else
        return (an(n - 1) + 4);
}

これも結果は先ほどの実行結果と同じようになる.

引数にnを受け取り,戻り値に $a n (n - 1) + 4$ を返す.
これぞ漸化式と言わんばかりの形をしている.私はこの書き方の方がしっくりくるが人それぞれかもしれない.

等比数列

次のような等比数列の $a_{10}$ を求めよ.

{a_{n}} : 1, 3, 9, 27, \dots

これも,普通に書くと

touhi/iterative.c

#include <stdio.h>

#define N 10

int main(void)
{
    int an;

    an = 1;
    for (int n = 1; n <= N; n++)
    {
        printf("a[%d] = %d\n", n, an);
        an = an * 3;
    }
    return 0;
}

実行結果は

a[7] = 729
a[8] = 2187
a[9] = 6561
a[10] = 19683

となり,これもあっている.

再帰関数で表現すると,

touhi/recursive.c

#include <stdio.h>

#define N 10

/* プロトタイプ宣言 */
int an(int n);

int main(void)
{
    for (int n = 1; n <= N; n++)
        printf("a[%d] = %d\n", n, an(n));
    return 0;
}

/* 漸化式(再帰関数) */
int an(int n)
{
    if (n == 1)
        return 1;
    else
        return (an(n - 1) * 3);
}

階差数列

次のような階差数列の $a_{10}$ を求めよ.

{a_{n}} : 6, 11, 18, 27, 38 \dots

階差数列の定義にしたがって階差数列 $(= b_{n})$ を考えると,

b_{n} = a_{n + 1} - a_{n}

より,

{b_{n}} : 5, 7, 9, 11 \dots

となるので,これで計算してみる.
ちなみに一般項は

a_{n} = n^{2} + 2 n + 3

である.

kaisa/iterative.c

#include <stdio.h>

#define N 10

int main(void)
{
    int an, bn;

    an = 6;
    bn = 5;
    for (int n = 1; n <= N; n++)
    {
        printf("a[%d] = %d\n", n, an);
        an = an + bn;
        bn = bn + 2;
    }
    return 0;
}

実行結果は

a[7] = 66
a[8] = 83
a[9] = 102
a[10] = 123

となり,一般項の値と一致する.

再帰で表現してみる.

kaisa/recursive.c

#include <stdio.h>

#define N 10

/* プロトタイプ宣言 */
int an(int n);
int bn(int b);

int main(void)
{
    for (int n = 1; n <= N; n++)
        printf("a[%d] = %d\n", n, an(n));
    return 0;
}

/* 漸化式(再帰関数) */
int an(int n)
{
    if (n == 1)
        return 6;
    else
        return (an(n - 1) + bn(n - 1));
}

/* 漸化式(再帰関数) */
int bn(int n)
{
    if (n == 1)
        return 5;
    else
        return (bn(n - 1) + 2);
}

これは再帰関数の中で再帰関数を呼び出しているので,沢山計算させていることになるが,これくらいはパソコンはなんなくやってくれるのが文明の利器といったところだろうか.

おわりに

今回はここら辺で一旦区切ろうかと思う.

ここで扱った内容はとても簡単だったかもしれないが,とても重要な概念なのでここでしっかりとイメージをつかみい.

自分の復習のためでもあり,学科の友達に共有するためにこの記事を書いている.続きも書く予定なので,ぜひチェックしていただけるとありがたい.

【数値解析入門】C言語で漸化式で解く Vol.1