the art of computer programming 1.2.1 を読む
1.2.1 数学的帰納法
数学的帰納法は以下の方法で証明を行う。
P(n)を整数nについての何らかの言明だとする。
(a) P(1) が真であることを証明する。
(b) [P(1), P(2), ... , P(n)が全て真なら、P(n + 1)も真である。]ことを証明する。
ただし、nを適当な数にしないと、nの分解の例(3は1+1+1=1+2=3というふうに分解できる。よってp(3)=3)のようにp(6)まで試してp(n)は素数になるという仮説をたてるとp(7)=15で泣くことになるので、注意が必要。
アルゴリズムI(証明の構築)
このアルゴリズムは上記の(a)(b)をアルゴリズム的に表したものである。
この数学的帰納法は視点を少しずらすと任意のアルゴリズムの正しさを証明できる方法を構想できる。
クヌース先生によると、ある問題に対してあるアルゴリズムが正しい理由を本当に理解するためには頭の中がすべての表明で一杯になるところまで到達しなければならないらしく、その表明を頭のなかで組み立てる上で役に立つのがアルゴリズムのサンプル実行である。
演習問題
1.[05]
(a) P(0) が真であることを証明する
(b) P(0), P(1), ..., P(n) についてすべて真なら、P(n + 1)も芯になることを証明する。
2.[15]
のときの証明がされていない。
実際にのときはのはであり、のときはとなる。のときのみこの定理は正しい。
3.[18]
n = 1のときに左辺が成り立たない。だが、初項がなので、左辺は0になる。
4.[20]
n = 1 のとき、 = 0.61803398なのでステップ(a)は証明される。
n = 2 のとき、 = 1なのでf(2)も証明される。
よって、次の式が得られる
ステップ(b)が終了したので、この式は数学的帰納法によって証明された。
5.[21]
n > 1で、nが素数の場合はそれ自身の積である。
nが素数でない場合はn = mk と分解でき、mが素数でなければm = abと分解でき、...とすると、n を素数の積に分解できる。
6.[20]
A5のはE4でc ← d, a' ← a, b' ← b となっているのでA6のが成り立つ。
A6のは
となりA5のが成り立つ。
7.[23]
となる。これは1からnまでの総和に等しい。よって、であると仮定する。
であり、成り立つ。で成り立つ。f(n)が成り立つと仮定すると、
これが
となれば、題意はで計算できることが証明できる。
左辺は、
通分して、
となり、左辺と右辺が一致するので、が成り立ち、証明ができた。
8.[25]
Nicomachusの定理が
で成り立つことを証明する。
で成り立つ。
これが、で成り立つとすると、の各項に2nをたせばよいので、
となり、この式がとなれば、証明できたこととなる。
右辺について整理する。
となったので、証明終了。
(b)
この式は、1からnまでの総和の2乗なので、
が証明された。
9.[20]
この問題は別の方に託す。