フィボナッチの母関数っぽいのを用いた合同式

892

はじめまして。
みなともと申します。
初めて記事を書きますので慣れないことが多いですが是非最後まで読んで貰えると嬉しいです。
初回はフィボナッチ数列に関する合同式です！

綺麗な合同式

合同式

2^{n} (F_{n - 1} + F_{n + 1}) \equiv 1 (\mod 5)

ここで使っているフィボナッチ数は
$F_{0} = F_{1} = 1, F_{n + 2} = F_{n + 1} + F_{n} (n ≧ 0)$ という風に、1ずらして定義します
(そっちの方が結果綺麗)

$S = \sum_{k = 0}^{n} F_{k} x^{k}$ とすると
$S = F_{0} + F_{1} x + F_{2} x^{2} + \dots + F_{n - 2} x^{n - 2} + F_{n - 1} x^{n - 1} + F_{n} x^{n} \dots ①$
$x S = F_{0} x + F_{1} x^{2} + F_{2} x^{3} + \dots + F_{n - 2} x^{n - 1} + F_{n - 1} x^{n} + F_{n} x^{n + 1} \dots ②$
$x^{2} S = F_{0} x^{2} + F_{1} x^{3} + F_{2} x^{4} + \dots + F_{n - 2} x^{n} + F_{n - 1} x^{n + 1} + F_{n} x^{n + 2} \dots ③$
を用いて等比数列の和の公式と同様にしてSを求めることができます。
①-②-③を考えます。するとx²~xⁿまでは前述したフィボナッチ数列の漸化式より係数が０になります。すると、
$(1 - x - x^{2}) S = (F_{0} + F_{1} x - F_{0} x - F_{n} x^{n + 1} - F_{n - 1} x^{n + 1} - F_{n} x^{n + 2})$
整理して
$(1 - x - x^{2}) S = 1 - F_{n} x^{n + 1} - F_{n - 1} x^{n + 1} - F_{n} x^{n + 2}$
$= 1 - (F_{n} + F_{n - 1}) x^{n + 1} - F_{n} x^{n + 2}$
$= 1 - F_{n + 1} x^{n + 1} - F_{n} x^{n + 2}$
$= 1 - x^{n + 1} (F_{n + 1} + F_{n} x)$
$S = \frac{x^{n + 1} (F_{n} x + F_{n + 1}) - 1}{x^{2} + x - 1}$

これでSを得られました！
ここで、x=2を代入してみましょう。

$S = \frac{2^{n + 1} (2 F_{n} + F_{n + 1}) - 1}{5}$
おっ？近づいて来ましたね！！
$F_{n + 2} = F_{n + 1} + F_{n}$
ですから、巧みに変形して
$S = \frac{2^{n + 1} (2 F_{n} + (F_{n + 2} - F_{n})) - 1}{5}$
$= \frac{2^{n + 1} (F_{n} + F_{n + 2}) - 1}{5}$
あとはもう簡単！！
Sはxが整数だと、整数値になるので
得られた式の分子は5の倍数。つまり
$2^{n + 1} (F_{n} + F_{n + 2}) \equiv 1 (\mod 5)$
nがズレることで影響はでないので
nを1だけずらしてやると……
$2^{n} (F_{n - 1} + F_{n + 1}) \equiv 1 (\mod 5)$
うおおおおぉぉぉ！！！
出た！出た！
ふぅ…()