微積分と物理​/数学的帰納

数学的帰納法による証明

帰納的に定義された対象は「数学的帰納法による証明」が行える
数学的論理による説明は慣れないうちはその主張がシンプル過ぎて意味がわからない
なので論理が主張する意味を追いかけて読み行間から意味を汲み取る必要がある。追いかけて読んでみる

自然数\(n\in\mathbb{N}\) に依存する命題 \(p(n)\) に対して

\( (\quad (p(1))\quad \wedge \quad (\quad (\forall k\in \mathbb{N})\quad (p(k)\Rightarrow p(k+1))\quad )\quad )\quad \Rightarrow \quad (\quad (\forall n\in \mathbb{N})\quad (p(n))\quad )\)

が成り立つ。数学的帰納法が成り立つ最低条件がこれとなっている

1. 数列の初期値(この場合\(n=1\))が関数\(P(1)\)で成り立つ事を示している
2. 任意の自然数\(k\)に対して\(p(k) ⇒ p(k+1)\)が成り立つ事を示す。これは離散的に連続するすべての自然数を入力とした関数が同じ性質を持っている事を示している
3. 1.2.が同時に成り立つ事が示せることから任意の自然数\(n\)について\(p(n)\)が成り立つ事を結論づける

これは「プログラマの数学」で説明されるドミノのたとえ話を論理的に説明したもの

Ｃ＃にこの論理を当てはめると\(p(1)\)は初期設定関数、\(p(k) ⇒ p(k+1)\)はループする帰納関数部を指している。\(p(n)\)が成り立つと主張する部分では、この帰納関数の全入出力は（自然数\(n\)がどんな値をとっても）関数\(p\)の性質を持ち続ける事を結論付けている。この論理式の前提を満たす関数は「数学的帰納法」に適合したものであると、この論理式は定義付けている

＜メモ＞
「ホーン節」という面白い考え方があるらしい。上記の解釈は我流であり本当はこれを理解した上でやるべきなのかもしれない。以下、資料
ホーン節
９．５ ホーン節と導出原理
論理プログラミング
ちょっと理解が出来ていないが一度しっかりやってみる必要があるかもしれない…

εδ論法はεとδが対応する関係にあった
この命題も対応する関係を含意によって証明（裏に隠れた関数が同じものだという事を証明）している訳だからよく似た事をしている？

証明の例

以下の漸化式が奇数になる事を証明する
\(\begin{cases} { a }_{ 1 }=3 \\ { a }_{ n+1 }=2{ a }_{ n }-1 \end{cases}\)

規則P:　どの\({a}_{n}\)も\(2\)で割ると\(1\)余る（奇数になる）
規則R:　\({a}_{n+1}\)は\({a}_{n}\)に対する漸化式

＜証明＞
basis:

1. \({a}_{1}=3\)であるから\({a}_{1}\)は\(2\)で割ると\(1\)余る

induction step:

1. \({a}_{n}\)を\(2\)で割ると\(1\)余る数だと仮定する
   つまり\({a}_{n}=2k+1\)とする（\(\forall k\in \mathbb{N}\)）
2. そのとき
   \({a}_{n+1}=2{a}_{n}-1\)
   　　　\(=2(2k+1)-1=4k+2-1\)
   　　　\(=4k+1\)
   であり規則Rが規則Pの性質を保存している。よって\({a}_{n+1}\)も\(2\)で割ると\(1\)余る

以上により、どの\({a}_{n}\)も2で割ると1余り奇数となる

漸化式の証明のまとめ

＜漸化式の特徴＞
漸化式は一般項を\(n\)の式で表せない数列も定義できる

＜漸化式の証明のまとめ＞

• basis:　出発点\({a}_{1}\)が性質Pを持っている事を示す
• induction step:　既に得られた項\({a}_{n}\)から次の項\({a}_{n+1}\)を作る規則Rが性質Pを保存している事を示す
• 以上を示せばすべての項が性質Pを持っている事が証明される

重要なのは再帰的なプログラムコードや関数も、これを意識すると非常に性質を制御しやすく作りやすくなるという点

バックアップストッカー

＜漸化式＞

数列の漸化式は帰納的定義となる

例えば等差数列の総和の漸化式は以下の形となる
<TODO>
等比数列の総和の漸化式は