素人が数学に挑戦 数学的帰納法と再帰性

群論からまたも脱線。
今回学んだのは数学的帰納法という論理の組み立て方と再帰性って概念（性質）について。
あっち行ったりこっち行ったりまとまりがないんですが、まあいいんです趣味なんで。
楽しくやります。

この話は日常生活でも有用かなあと思います。

素人が数学に挑戦　群

群論って抽象的な議論が展開される分野です。なんでそんなこと考えるの？って感じますが、超高度な抽象化が必要な状況があったのだろうと無理やり納得させて前へ進めていきます。とりあえず群の定義から。群定義群（グルー...

riku-nagahama.xyz

2022.03.19

数学的帰納法と再帰性

まずは数学的帰納法について。

帰納法

帰納（きのう、英: Induction、希: επαγωγή（エパゴーゲー））とは、個別的・特殊的な事例から一般的・普遍的な規則・法則を見出そうとする論理的推論の方法のこと。演繹においては前提が真であれば結論も必然的に真であるが、帰納においては前提が真であるからといって結論が真であることは保証されない。

Wikipedia

一般的にいって帰納は、あくまでも確率・確度といった蓋然性の導出に留まる。例えば、「ネコaはネズミを追いかける」「ネコbはネズミを追いかける」「ネコcはネズミを追いかける」という事例が幾つかあるので、「全てのネコはネズミを追いかける」と結論を下すとしよう。ここでは、自分が見たネコだけから「全てのネコ」という全称命題に範囲を飛躍させている。しかし、この先新たにネズミを追いかけない猫が発見される可能性は常にある。したがって、「全てのネコはネズミを追いかける」と定式化することには疑問が残る。

Wikipedia

上の表がとても分かりやすい。
要するに帰納法は個別の事象を眺めて共通点から正しそうな結論を導きだす論法のことです。
数学の厳密な帰納法と違て、一般的な帰納法は曖昧になってしまいますが、それによって求めた確からしそうな事象は確かなのだと認めてしまおうって合意がされている感じです。これを疑ってしまうと永遠に証明が終わらないので。
演繹は事柄の見方を変えるだけなので結論は常に真です。

再帰的

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

Wikipedia

「『「絵を描く人の絵」を描く人の絵』を描く人の絵を…」のように同じ構造（例では「絵を描く人の」）を繰り返しあてはめること（入れ子）ができる性質をいう。

Wikipedia

大量絶滅のフラクタル

自然現象って不思議な周期があるなって感じるんですよね。決まった周期があるって。フラクタル構造直観的にはミクロの周期がマクロの周期を決めているって発想になりますが、マクロの周期がミクロに作用しているんじゃないかって感じること...

riku-nagahama.xyz

2022.03.06

合わせ鏡した時のあれ。
定義からするとフラクタル構造も再帰性ですかね。
株価とかも同じような構造が繰り返されているんで、再帰的な感じがします。

みんなが相場のグラフを見て、それで自分の立ち位置（売りか買い）を決めるわけです。
「株価を見ている人たちによって株価の動きが決定され、またその動きによって株価が…」。
再帰的ですね。おもしれ。

漸化式（再帰関係式）

数学で再帰的な数列を表すものに漸化式があります。

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

Wikipedia

再帰的な数列とは例えば、数列のある項を選んだとします。
すると、次の項が自然に決定されるような数列のことです。
それを表した等式が漸化式と呼ばれます。

自然数{1,2,3,4,5….}を漸化式で表すと
$a_{n+1} = a_n + 1$
$a_n = 1$とすると
$a_{n+1} = 1 + 1 = 2$
となり自動的に1の次の項が定まります。
$a_100$でも$a_1000$でも前の項が分かれば次の項は必然的に求めることができます。

ただ、いきなり$a_100$を求めたい時もあります。
いちいち100項まで求めるのは面倒です。
そこで登場するのが数学的帰納法。
漸化式の再帰的な性質を利用して等差数列の初項で成立する性質がその数列全体に成立することを証明します。

数学的帰納法

数学的帰納法の方法は
1. n = 1で命題が成立することを証明する
2. n = kで命題が真であるなら、ｋ+1でも真であることを証明する

等差数列である自然数の初項から第n項までの和は
$\frac{1}{2}n(n + 1)$
で表せます。

この式が自然数全体で成立することを上の手順に従って証明してみます。

まずは数学的帰納法の手順に従って1から1までの和を求めます。
$\frac{1}{2}n(n + 1) = \frac{2}{2} = 1$
手順1は完了。

次の手順です。
n = kを代入すると第k項までの和は等差数列の和の公式により表現できます。
$\frac{1}{2}k(k + 1)$
和の公式が正しいことの証明は本題ではないので認めてしまいます。

上式に(k + 1)を足すと第ｋ+1項までの和が求められます。
$\frac{1}{2}k(k + 1)(k + 1)$
(k + 1)でくくって
$= (k + 1)(\frac{1}{2}k + 1)$
$= (k + 1)\frac{k + 2}{2}$
1/2を外へだして
$= \frac{1}{2}(k + 1)(k + 2)$

n = k + 1 とすると等差数列の和の公式より
$\frac{1}{2}(k + 1)(k + 2)$
上式の結果と一致し、手順2も完了。

漸化式の再帰的な性質からこれを無限に繰り返していくことができるので、等差数列の和の公式が自然数全体で成立することが証明できました。

僕はこの証明をグーグル先生に教えてもらいましたが、無から漸化式の性質と等差数列の和の公式を利用して論理的に無限回必要な証明を省いてしまう数学者は超かっこええ。
数学論理の組み立て方って曲芸的で「その手があったか！」みたいな論法張るんでアハ体験で脳みそが気持ちよくなりますよね。

視点を変えるだけで形が変わったりして面白いなあって思います。