LoginSignup
1
1

More than 5 years have passed since last update.

「等比? 等差? フィボナッチ??」の解説(フィボナッチ数判定)

Last updated at Posted at 2016-10-14

@Nabetani さんが出題していた「等比? 等差? フィボナッチ??」を解いてみました。
与えられた5つの部分数列が等比数列等差数列か、はたまたフィボナッチ数列か(またはそれ以外か)を当てる問題でした。以下では、それぞれの判別方法について解説していきます。なお、第$i$項を$a_i$としています。

等比数列の判定

隣り合う項の比をとってやり、それが全て等しければ等比数列と判断できます。
比のままでは少し扱いづらいので、積の形に変形しています。

a_{i} : a_{i+1} = a_{i+1} : a_{i+2} \\
a_{i+1}a_{i+1} = a_{i}a_{i+2}

等差数列の判定

隣り合う項の差が全て等しければ等差数列と判断できます。これは特に説明は不要でしょう。

フィボナッチ数列の判定

これがこの問題のキモだったのではないでしょうか。フィボナッチ数列っぽくなってるかどうかは等式$a_{i+2}=a_{i+1}+a_{i}$が満たされていることを確認すればいいのですが、$a_i$、$a_{i+1}$($=A$とします)自体がフィボナッチ数ではない場合、いくら前述の等式が満たされているからといって、与えられた部分数列はフィボナッチ数列になり得ません。(追記:さらに、$a_i < a_{i+1}$かつ$a_{i+1} = a_{i-1}+a_{i} < a_i + a_i = 2a_i$、または$a_1=a_2=1$である必要もある。)
では、どうやって$a_i$がフィボナッチ数かを判断すればよいのでしょうか。結論から言うと、$5A^2 + 4$または$5A^2 - 4$が完全平方数(ルートをとってもなお整数であるような整数$:1,4,9,16,25,49,...$)であれば$A$はフィボナッチ数となります。

定理

$5A^2 \pm 4 = B^2 $ ならば $A$ は フィボナッチ数である。

証明

$5A^2 \pm 4 = B^2 $を次のように変形する。

\begin{eqnarray}
5A^2 \pm 4 = B^2 \\
B^2 - 5A^2 = \pm 4 \\
(B+\sqrt{5}A)(B-\sqrt{5}A)=\pm 4 \\
\left(\frac{B+\sqrt{5}A}{2}\right)\left(\frac{B-\sqrt{5}A}{2}\right)=\pm 1
\end{eqnarray}

ここで、整数$l$を用いて

\frac{B+\sqrt{5}A}{2} = \left(\frac{1+\sqrt{5}}{2}\right)^l \\
\frac{B-\sqrt{5}A}{2} = \left(\frac{1-\sqrt{5}}{2}\right)^l

と書けるので(参考[1]参照)、

\begin{eqnarray}
A = \frac{1}{\sqrt{5}}\left(\frac{B+\sqrt{5}A}{2} - \frac{B-\sqrt{5}A}{2} \right) \\
=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^l - \left(\frac{1-\sqrt{5}}{2}\right)^l \right) \\
= F_l
\end{eqnarray}

となり、$A$はフィボナッチ数$F_l$であることが分かる。$\blacksquare$

提出コード

提出コードはGolangで書きました。解答は特に晒すほどのものでもないので、リポジトリのリンクだけ載せておきます。

参考

  1. ディリクレの単数定理とペル方程式 - tsujimotterの下書きノート
  2. Why does this test for Fibonacci work? - math.stackexchange.com
1
1
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
1