ずっと前 *1 に, 次の問題 ( 年東大文理共通) をやったことがあるけれども, 別解に気がついた. この問題は, フィボナッチ数列に関係している.
【問】
は正の整数とする。
を
で割った余りを
とおく。
数列 は
を満たすことを示せ。
に対して、
は ともに正の整数で、互いに素であることを証明せよ。
【別解】
たとえば,
として,
を
で実際に割ってみると,
商は,
で, 余りは,
となり, 各項の係数は, フィボナッチ数列に関連しているのではないかと予想できる. ここで, フィボナッチ数列 は,
,
として,
で与えられる数列のことである.
そこで, を
で割った商を
余りを
と仮定し, これが正しいことを数学的帰納法で証明する.
のとき,
となって成立する.
で成立すると仮定すると,
したがって, を
で割った商は,
で, 余りは,
である *2.
,
であるから,
フィボナッチ数列の各項が正の整数であることは当たり前で, フィボナッチ数列の隣接 項は互いに素 (最大公約数が
) であるというのも, よく知られており *3 証明は省略する.
//