Search on the blog

2012年9月28日金曜日

フィボナッチ数列の最大公約数について

Codeforces#140「Anniversary」で出てきた
(Fib(x), Fib(y)) = Fib((x, y))
を簡単に導出してみようと思います。

隣り合うフィボナッチ数は互いに素
隣り合うフィボナッチ数が互いに素ではなかったと仮定します。そのとき、

(Fib(x), Fib(x+1)) = d, d>0
となるようなdが存在します。このとき、フィボナッチ数の定義より、

Fib(x-1) = Fib(x+1) - Fib(x)
なので、d | Fib(x-1) となります。これを繰り返すと、d| Fib(1)となりますがこれはFib(1) = 1と矛盾します。 よって背理法より、隣り合うフィボナッチ数は互いに素となります。

フィボナッチ数の加法定理
x>2,   y>1について、
Fib(x+y) = Fib(x)Fib(y+1) + Fib(x-1)Fib(y)
という性質が成り立ちます。数学的帰納法を使うと証明できるそうですが、ここでは簡単に上の定理が正しいことを説明します。

Fib(x)は階段を1段ずつ、または1段飛ばしで登っていき、x段目に辿り着いたときの上り方のパターン数と考えることができます。Fib(x+y)はx+y段目まで登るとき(最下段からx+y-1段登ったとき)のパターン数です。
最下段からx+y-1段登るときのパターン数を、x段目を通るか通らないかに場合分けすると、
(x+y-1段登るときのパターン数)
= (x段目を通るパターン数) + (x段目を通らないパターン数)
= (x-1段登ったあと、y段登るパターン) + (x-2段登った後、1段飛ばしをして、y-1段登るパターン)
= (x-1段登るパターン数 * y段登るパターン数) + (x-2段登るパターン数 * y-1段登るパターン数)
ということで、まさにこれが加法定理と同じです。

(Fib(x), Fib(y)) = Fib((x,y))
さて、いよいよ目的の定理を考えます。まずは、Fib(x)とFib(x+y)の最大公約数を考えてみます。
(Fib(x), Fib(x+y))
= (Fib(x), Fib(x)Fib(y+1) + Fib(x-1)Fib(y))     (∵加法定理より)
= (Fib(x), Fib(x-1)Fib(y))     (∵ Fib(x) | Fib(x)Fib(y+1)より)
= (Fib(x), Fib(y))     (∵ (Fib(x), Fib(x-1)) = 1より)

はい、来ました。 (Fib(x), Fib(x+y)) = (Fib(x), Fib(y))
です。これを再帰的に繰り替えしていくとユークリッドの互除法(の引き算バージョン)によって、
(Fib(x), Fib(x+y)) = Fib((x, x+y))
となります。よって、目的の定理が成り立ちます。

0 件のコメント:

コメントを投稿