| (A) フィボナッチ数の加法定理 F[m+n] = F[m]F[n+1]+F[m-1]F[n] の証明
m, n は自然数で、m ≧ 2 とする。
m = 2 の場合、F[1] = F[2] = 1 なので、 F[2+n] = F[n+1]+F[n] = F[2]F[n+1]+F[2-1]F[n] となり加法定理は成立する。
m = 3 の場合、F[2] = 1, F[3] = 2 なので、 F[3+n] = F[n+2]+F[n+1] = (F[n+1]+F[n])+F[n+1] = 2F[n+1]+F[n] = F[3]F[n+1]+F[3-1]F[n] となり加法定理は成立する。
k を 3 以上の自然数として、m = k と m = k-1 で加法定理の成立を仮定すると、 F[(k+1)+n] = F[k+n]+F[(k-1)+n] = (F[k]F[n+1]+F[k-1]F[n])+(F[k-1]F[n+1]+F[k-2]F[n]) = (F[k]+F[k-1])F[n+1]+(F[k-1]+F[k-2])F[n] = F[k+1]F[n+1]+F[k]F[n] となり、m = k+1 でも成立する。
以上から、数学的帰納法により 2 以上の自然数 m と 任意の自然数 n に対して、 F[m+n] = F[m]F[n+1]+F[m-1]F[n] が成立する。
(B) フィボナッチ数の整除定理 m | n ならば F[m] | F[n] の証明
n を 2 以上の自然数とすると、加法定理より、 F[n+n] = F[n]F[n+1]+F[n-1]F[n] = F[n](F[n+1]+F[n-1]) つまり、F[n] | F[2n] が成立する。
k を 2 以上の自然数、u を自然数として、F[kn] = u*F[n] を仮定すると、 F[(k+1)n] = F[n]F[kn+1]+F[n-1]F[kn] = F[n]F[kn+1]+F[n-1]*u*F[n] = F[n](F[kn+1]+F[n-1]*u) となり、F[n] | F[(k+1)n] が成立する。
以上から、数学的帰納法により v と n を 2 以上の自然数とするとき F[n] | F[vn] が成立する。 # n = 1 や v = 1 でも上記は成立しますが。
(C) F[p] が素数ならば、p は奇素数であるか 4 であることの証明
3 以上の自然数 a と 2 以上の自然数 b が存在して p = ab ならば、 a < p であり、1 < F[a] < F[p] かつ整除定理より F[a] | F[p] となり F[p] は素数ではありえない。
従って、F[p] が素数となるためには p は真の約数を持たないか、 真の約数の値が 2 以下の場合である。
真の約数を持たないということは、p は素数であるということてある。 但し、F[2] = 1 は素数ではないので、p は奇素数である。 真の約数の値が 2 以下ということは p は 2 の冪であることが必要だが、 2^3 = 8 は 4 という真の約数を持つため、可能性は p = 2^2 のみとなるが、 F[4] = 3 は素数である。
以上から、F[p] が素数ならば、p は奇素数か 4 であるといえる。
|