Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

@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
cia_rana
Go/Ruby/渋谷の某3DCGプロダクションで働くそふとうぇあえんじにゃーん/Creator Support Engineer
https://medium.com/@cia_rana/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away