読者です 読者をやめる 読者になる 読者になる

the art of computer programming 1.2.1 を読む

taocp the_art_of_computer_programming

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(証明の構築)

I1.[P(1) を証明する] k ← 1を行い、P(k) の証明を出力する。

I2.[k = n?] k = n なら、アルゴリズムを終了する。必要な証明は出力されている。

I3.[P(k + 1)を証明する] P(1), ... , P(k) のすべてが真なら、P(k + 1) は真であることの証明を出力する。また、P(1), ... , P(k) をすでに証明したので、P(k + 1) は真であると出力する

I4.[k に 1 を加える]k に 1 を加え、ステップI2に進む。

このアルゴリズムは上記の(a)(b)をアルゴリズム的に表したものである。

 

この数学的帰納法は視点を少しずらすと任意のアルゴリズムの正しさを証明できる方法を構想できる。

クヌース先生によると、ある問題に対してあるアルゴリズムが正しい理由を本当に理解するためには頭の中がすべての表明で一杯になるところまで到達しなければならないらしく、その表明を頭のなかで組み立てる上で役に立つのがアルゴリズムのサンプル実行である。

 

演習問題

1.[05]

    (a) P(0) が真であることを証明する

    (b) P(0), P(1), ..., P(n) についてすべて真なら、P(n + 1)も芯になることを証明する。

 

2.[15]

    n = 2のときの証明がされていない。

    実際にn = 2のときはのa^{n-1}aであり、n = 3のときはa^2となる。a = 1のときのみこの定理は正しい。

 

3.[18]

    n = 1のときに左辺が成り立たない。\frac{1}{0 \times 1}だが、初項が\frac{1}{1 \times  2}なので、左辺は0になる。

 

4.[20]

    n = 1 のとき、\phi^-1 = 0.61803398なのでステップ(a)は証明される。

    n = 2 のとき、\phi^0 = 1なのでf(2)も証明される。

    よって、次の式が得られる

    F_{n+1} = F_{n-1}+F{n} \le \phi^{(n-1)-2)}+\phi^{n-2}=\phi^{n-3}(1+\phi)=

    \phi^{n-1}=\phi^{((n+1)-2)}

    ステップ(b)が終了したので、この式は数学的帰納法によって証明された。

 

5.[21]

    n > 1で、nが素数の場合はそれ自身の積である。

    nが素数でない場合はn = mk と分解でき、mが素数でなければm = abと分解でき、...とすると、n を素数の積に分解できる。

 

6.[20]

    A5のam + bn = dはE4でc ← d, a' ← a, b' ← b となっているのでA6のa'm + b'n = cが成り立つ。

    A6のam + bn = c(a'-qa)m+(b'-qb)n=(a'm+b'n)-(qam+bqn)

    =qd+r-q(am+bn)=qd+r-qd=r=a'm+b'nとなりA5のa'm+b'nが成り立つ。

 

7.[23]

    1^2=1

    2^2-1^2=3

    3^2-2^2+1^2=6

    4^2-3^2+2^2-1^2=10

    5^2-4^2+3^2-2^2+1^2=15

    6^2-5^2+4^2-3^2+2^2-1^1=21

    となる。これは1からnまでの総和に等しい。よって、f(n)=\frac{n(n+1)}{2}であると仮定する。

    f(1) = 1であり、成り立つ。f(2) = 3で成り立つ。f(n)が成り立つと仮定すると、

f(n + 1) = (n+1)^2-\frac{n(n+1)}{2}

これが

\frac{(n+1)(n+2)}{2}

となれば、題意はf(n)=\frac{n(n+1)}{2}で計算できることが証明できる。

左辺は、

(n^2+2n+1)-\frac{n(n+1)}{2}

通分して、

\frac{2n^2+4n+2-n^2-n}{2}

=\frac{n^2+3n+2}{2}

=\frac{(n+2)(n+1)}{2}

となり、左辺と右辺が一致するので、f(n + 1) = (n+1)^2-\frac{n(n+1)}{2}が成り立ち、証明ができた。

 

 

8.[25]

    Nicomachusの定理が

f(n) = (n^2-n+1)+(n^2-n+3)+...+(n^2-n+2n-1)

で成り立つことを証明する。

    f(1) = 1^2-1+2-1=1で成り立つ。

    これが、f(n)で成り立つとすると、f(n)の各項に2nをたせばよいので、

    f(n + 1) = 2n^2+f(n)+(n^2-n+2n+1)+2n

    となり、この式が(n+1)^3となれば、証明できたこととなる。

    右辺について整理する。

    2^n+n^3+n^2-n+2n+1+2n

    =n^3+3n^2+3n+1

    =(n+1)^3

    f(n+1)=(n+1)^3となったので、証明終了。

 

(b)

    f(n) = 1+3+5+...+(n^2-n+1)+...+(n^2-n+2n-1)

    =\frac{\frac{n(n+1)}{2}(1+n^2+n-1)}{2}

    =\frac{(n^2+n)^2}{4}

    =(\frac{n(n+1)}{2})^2

    この式は、1からnまでの総和の2乗なので、

    1^3+2^3+...+n^3=(1+2+...+n)^2が証明された。

 

9.[20]

    この問題は別の方に託す。