フィボナッチ数列の一般項が整数になる理由

今回は、フィボナッチ数列についての話です。
有名なので、ご存じの方も多いかと思われますが、一応説明しますと、フィボナッチ数列は
$a_1 = a_2 = 1, a_{n+2} = a_{n+1} + a_n$
で、定義されます。
この数列の一般項を表す式に無理数が現れるのも、また有名な話です。

隣接三項間漸化式を解いてみれば分かります。
現行の学習指導要領で言えば、数学Bの範囲です。

$x^2=x+1$
の異なる二つの実数解を
$\alpha,\beta$
とおくと
$a_{n+2}-\alpha a_{n+1} = \beta(a_{n+1}-\alpha a_n)$
より
$a_{n+1}-\alpha a_n = (a_2-\alpha a_1)\beta^{n-1$ …(1)
同様に
$a_{n+1}-\beta a_n = (a_2-\beta a_1)\alpha^{n-1$ …(2)
(2)-(1)より
$a_n = \frac{(a_2 - \beta a_1)\alpha^{n-1}-(a_2 - \alpha a_1)\beta^{n-1}}{\alpha - \beta}$
これに
$\alpha = \frac{1+\sqrt{5}}{2}, \beta = \frac{1-\sqrt{5}}{2}$
などを代入して整理すると
$a_n = \frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}$ …(3)
これが、フィボナッチ数列の一般項です。

さて、定義から明らかなように、フィボナッチ数列の一般項は有理数です。
それなのに、一般項を表す式には無理数が登場します。
これ如何に。
考えてもみれば簡単なことで、 $(1+\sqrt{5})^n-(1-\sqrt{5})^n$ を展開して整理すると、上手い具合に整数の項が消え、 $a\sqrt{5}$ の形をした項だけが残ります。
したがって、それらを $\sqrt{5}$ で割ってやれば無理数が消える、というわけです。
それならば。
フィボナッチ数列の一般項を、無理数を使わずに表してみましょう。
それが今回の一つ目のお題。前振りが長かったですね。

二項定理を使うと
$(1+\sqrt{5})^n = \sum_{r=0}^{n}{}_nC_r\sqrt{5}^r$
$(1-\sqrt{5})^n = \sum_{r=0}^{n}{}_nC_r(-\sqrt{5})^r$
なので、
$(1+\sqrt{5})^n-(1-\sqrt{5})^n = \sum_{r=0}^{n}{}_nC_r\{\sqrt{5}^r-(-\sqrt{5})^r\}$
nが偶数のとき、シグマの中は0になるので、
$=\sum_{r=1}^{\lfloor\frac{n+1}{2}\rfloor}{}_nC_{2r-1}\{\sqrt{5}^{2r-1}-(-\sqrt{5})^{2r-1}\}$
$=2\sum_{r=1}^{\lfloor\frac{n+1}{2}\rfloor}{}_nC_{2r-1}\sqrt{5}^{2r-1}$ …(4)
と、なります。
ここで、 $\lfloor\frac{n+1}{2}\rfloor$ は、n+1以下の最大の整数を表します。
何故こんな表記を用いるかというと、0からnまでの間に奇数がそれだけあるからです。
そして、(4)を(3)に代入すると
$a_n = \frac{2}{2^n\sqrt{5}}\sum_{r=1}^{\lfloor\frac{n+1}{2}\rfloor}{}_nC_{2r-1}\sqrt{5}^{2r-1}$
$= \frac{1}{2^{n-1}}\sum_{r=1}^{\lfloor\frac{n+1}{2}\rfloor}{}_nC_{2r-1}\sqrt{5}^{2r-2}$
$= \frac{1}{2^{n-1}}\sum_{r=1}^{\lfloor\frac{n+1}{2}\rfloor}{}_nC_{2r-1}5^{r-1}$
と、なります。
これが、フィボナッチ数列の一般項その2、です。

これにて、一般項を、無理数を使わずに表すことができました。
めでたし。

…と、いきたいところなのですが、まだ問題があります。
実は、上の式からはフィボナッチ数列の一般項が有理数になることは分かっても、整数になることまでは明らかではないのです。
どうしましょう。
上の式から考えるととても難しそうなので、初心に帰って
$a_n = \frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}$ …(3)
から考えます。
ここからが、今回の二つ目のお題です。

(3)が整数であることを証明するには、
$(1+\sqrt{5})^n-(1-\sqrt{5})^n$ が $2^n\sqrt{5}$ で割り切れることを示せば良いのです。
証明は、数学的帰納法によります。
n=1のとき、
$(1+\sqrt{5})-(1-\sqrt{5})=2^1\sqrt{5}$
よって成り立つ。
n=1からkまで、成り立っていると仮定すると
$(1+\sqrt{5})^k-(1-\sqrt{5})^k$ が $2^k\sqrt{5}$ で割り切れます。
このとき、
$(1+\sqrt{5})^k-(1-\sqrt{5})^k = a^k-b^k$
とおくと
$(a^k-b^k)(a+b) = a^{k+1} - b^{k+1} + ba^k-ab^k$ …(5)
ここで、帰納法の仮定より $a^k-b^k$ は $2^k\sqrt{5}$ で割り切れ、さらに $a+b=2$ であることから、(5)は $2^{k+1}\sqrt{5}$ で割り切れます。
よって、 $a^{k+1}-b^{k+1}$ が $2^{k+1}\sqrt{5}$ で割り切れることを証明するには、 $ba^k-ab^k$ が $2^{k+1}\sqrt{5}$ で割り切れることを示せば充分です。
$ba^k-ab^k = (1-\sqrt{5})(1+\sqrt{5})^k-(1+\sqrt{5})(1-\sqrt{5})^k$
$= (1-5)(1+\sqrt{5})^{k-1}-(1-5)(1-\sqrt{5})^{k-1}$
$= -4\{(1+\sqrt{5})^{k-1}-(1-\sqrt{5})^{k-1}\}$ …(6)
仮定より $(1+\sqrt{5})^{k-1}-(1-\sqrt{5})^{k-1}$ は $2^{k-1}\sqrt{5}$ で割り切れるので、(6)は $4*2^{k-1}\sqrt{5}=2^{k+1}\sqrt{5}$ で割り切れる。
証明終わり。

大学入試問題に出そうな問題ですね。

ちなみに、ここでの数学的帰納法は、厳密には高校で習うようなタイプのものではありません。
高校では
1)n=1のときに成り立つ
2)n=kのときに成り立つならばn=k+1のときに成り立つ
という二つの事実を示してから、よって任意のnについて成り立つ、と結論付けるのですが、ここでは
1)n=1のときに成り立つ
2)n=1からn=kまで成り立つならばn=k+1のときに成り立つ
という二つの事実を示してから、よって任意のnについて成り立つ、と結論付けるものです。
どっちにしても同じことなのですが。