피보나치 수(Fibonacci number) 판별법

      Comments Off on 피보나치 수(Fibonacci number) 판별법

피보나치 수열(Fibonacci sequence) $F_n$은 다음과 같이 귀납적으로 정의되는 수열이다.

\[ F_0 = 0, \quad F_1 = 1, \quad F_{n} = F_{n-1} + F_{n-2}\; (n \geq 2). \]

이제 피보나치 수열 $F_n$에 나타나는 모든 음이 아닌 정수들을 피보나치 수(Fibonacci number)라 정의하자. 그러면 주어진 양의 정수 $x$에 대하여, 이 수가 피보나치 수인지 아닌지를 어떻게 알 수 있을까? $F_n$은 귀납적으로 정의된 수열이기 때문에 주어진 $x$의 피보나치 수 여부를 판단하는건 간단하지 않은 문제이다. 이번 글에서는 피보나치 수열의 닫힌 형식(closed form)을 구하고 이를 바탕으로 양의 정수 $x$가 피보나치 수열의 항인지 아닌지를 상대적으로 빠르게 판단하는 방법에 대해서 살펴 보고자 한다.

$ $

먼저 두 실수 $\phi$와 $\psi$를 방정식 $x^2-x-1 = 0$의 두 근이라 하자. 즉, $\phi$와 $\psi$는 아래의 값을 갖는 실수이다:

\[ \phi = \frac{1+\sqrt{5}}{2}, \quad \psi=\frac{1-\sqrt{5}}{2} \]

이 두 수는 사실 피보나치 수열과 매우 밀접한 관련이 있다. 특히, 아래의 공식이 성립한다.

$ $

정리 1. 비네의 공식 (Binet's formula)

임의의 음이 아닌 정수 $n$에 대하여

\begin{equation} F_n=\frac{\phi^n-\psi^n}{\phi-\psi} = \frac{1}{\sqrt{5}} (\phi^n - \psi^n) \tag{1} \end{equation}

$ $

증명. 귀납법을 통해 증명한다. 먼저 $n=0$인 경우, 식 (1)의 좌변과 우변이 모두 $0$임은 자명하다. 이제 식 (1)이 정수 $m$일 때 성립한다고 가정하자. $\phi$와 $\psi$가 모두 방정식 $x^2−x−1=0$의 근이므로, $\phi^2=\phi+1$과 $\psi^2=\psi+1$이 성립함을 알 수 있다. 따라서

\begin{align*} \frac{\phi^{m+1}-\psi^{m+1}}{\phi-\psi} &= \frac{\phi^{m-1}\phi^2-\psi^{m-1}\psi^2}{\phi-\psi} \\[5px] &= \frac{\phi^{m-1}(\phi+1)-\psi^{m-1}(\psi+1)}{\phi-\psi} \\[5px] &= \frac{\phi^m-\psi^m}{\phi-\psi}+\frac{\phi^{m-1}-\psi^{m-1}}{\phi-\psi} \\[5px] &= F_m+F_{m-1} \\[5px] &= F_{m+1} \end{align*}

따라서 수학적 귀납법에 의해 식 음이 아닌 정수 $n$에 대해 식 (1)이 성립한다..

$ $

피보나치 수(Fibonacci number) 판별법

이제 비네의 정리를 이용하여 주어진 양의 정수 $x$가 피보나치 수인지 아닌지를 판단하는 방법에 대해 알아보자.

$ $

정리 2. 인접한 두 피보나치 수 판별법

$x \leq y$가 음이 아닌 정수라 하자. 그러면 $x,\,y$가 인접한 두 피보나치 수일 필요충분조건은 $y^2-xy-x^2 = \pm 1$이 성립하는 것이다.

$ $

증명. $(\Longrightarrow)$ 먼저 $x$와 $y$가 인접한 두 피보나치 수, 즉, $x=F_n$이고 $y=F_{n+1}$이라 가정하자. 우선, 두 실수 $\phi$와 $\psi$에 대하여 아래의 사실을 간단히 보일 수 있다.

\[ \phi\psi = -1, \quad \phi+\psi=1, \quad \phi^2=\phi+1, \quad \psi^2=\psi+1. \]

위 사실과 비네의 공식 (정리 1)을 이용하면,

\begin{align*} y^2-xy-x^2 & = (F_{n+1})^2-F_nF_{n+1}-(F_n)^2 \\[5px] & = \frac{\left(\phi^{n+1}-\psi^{n+1}\right)^2}{5} - \frac{\left(\phi^n-\psi^n\right)\left(\phi^{n+1}-\psi^{n+1}\right)}{5} - \frac{\left(\phi_n-\psi_n\right)^2}{5} \\[5px] & = \frac{1}{5} \Big[ \phi^{2n+2} - 2\phi^{n+1}\psi^{n+1} + \psi^{2n+2} - \phi^{2n+1} - \psi^{2n+1} \\[5px] & \qquad + \phi^n\psi^{n+1} + \psi^n\phi^{n+1} - \phi^{2n}+2\phi^n\psi^n - \psi^{2n} \Big] \\[5px] & = \frac{1}{5} \Big[ \phi^{2n}(\phi + 1) - 2(\phi\psi)^{n+1} + \psi^{2n}(\psi+1) - \phi^{2n+1} - \psi^{2n+1} \\[5px] & \qquad + (\psi\psi)^n\psi + (\psi\phi)^n\phi - \phi^{2n} + 2(\phi\psi)^n - \psi^{2n} \Big] \\[5px] & = \frac{1}{5} \Big[ -2(-1)^{n+1} + (-1)^n(\psi+\phi) + 2(-1)^n \Big] \\[5px] & = \frac{1}{5} \Big[ 2(-1)^n + (-1)^n + 2(-1)^n \Big] \\[5px] & = (-1)^n \\[5px] & = \pm 1 \end{align*}

따라서 $y^2-xy-x^2 = \pm 1$을 얻는다.

$ $

$(\Longleftarrow)$ 이제 음이 아닌 모든 정수들의 집합을 $\N_0$으로 나타내기로 하고 아래와 같이 집합 $A$를 정의하자.

\[ A = \set{(x,y)}{y^2-xy-x^2=\pm 1, \mbox{ where } x,\,y \in \N_0}. \]

또한 $A$의 임의의 두 원소 $(x_1,\, y_1)$, $(x_2,\, y_2)$에 대하여, 아래와 같이 순서관계

\[ (x_1,\, y_1) \leq (x_2,\, y_2) \Longleftrightarrow y_1 \leq y_2 \]

를 정의하자. 그러면 이 관계는 집합 $A$ 에서 반대칭성(antisymmetry), 추이성(transitivity), 완전성(totality)를 모두 만족하는 전순서(total order)가 됨을 간단히 보일 수 있다.

이제 집합 $A$의 임의의 원소 $(x,\,y)$에 대하여, $x$와 $y$가 인접한 두 피보나치 수임을 수학적 귀납법으로 보일 것이다. 먼저 $(x,\,y) = (0,\,1)$인 경우, $x=F_0$, $y=F_1$이 되어 명제가 성립한다. 또한 $(x,\, y) = (1,\,1)$인 경우도 $x=F_1$, $y=F_2$가 되어 명제가 성립함을 알 수 있다. 이제 $(x,\,y) \in A$가 $(0,\,1)$, $(1,\,1)$이 아니라 가정하고, $(x,\,y)$ 보다 작은 모든 $(u,\,v) \in A$에 대하여 주어진 명제가 성립한다고 가정하자. 이제 원소 $(y-x,\, x)$를 생각해 보자. 먼저 $y-x \in \N_0$이고 $x \in \N_0$임은 자명하다. 또한

\begin{align*} x^2-(y-x)x-(y-x)^2 &= x^2-xy+x^2-y^2+2xy-x^2 \\[5px] &= -y^2+xy+x^2 \\[5px] &= -(y^2-xy-x^2) \\[5px] &= \pm 1 \end{align*}

를 얻는다. 따라서 $(y-x,\,x) \in A$임을 알 수 있다. 이제 $x < y$이므로 (만약 $x=y$라면 $(x,\,y) = (1,\,1)$이 되어 가정에 모순) $(y−x,\, x) < (x,\, y)$를 얻는다. 따라서 귀납법 가정에 의하여 $y-x$와 $x$는 인접한 두 피보나치 수이다. 즉, 적당한 $k$가 존재하여 $y-x = F_k$, $x=F_{k+1}$를 만족한다. 마지막으로

\[ y = (y-x) + x = F_k + F_{k+1} = F_{k+2} \]

가 되어 $x = F_{k+1}$, $y = F_{k+2}$가 됨을 알 수 있다. 따라서 수학적 귀납법에 의하여 주어진 명제가 성립한다..

$ $

정리 3. 피보나치 수 판별법

$x$가 음이 아닌 정수라 하자. 그러면 $x$가 피보나치 수일 필요충분조건은 $5x^2+4$ 또는 $5x^2−4$가 완전제곱수(perfect square)인 것이다.

$ $

증명. 우선 주어진 음이 아닌 정수 $k$가 완전제곱수일 필요충분조건은 $\sqrt{k}$가 정수인 것이라는 사실을 기억하자. 이제 방정식

\begin{equation} y^2-xy-x^2 = \pm 1 \tag{3} \end{equation}

을 $y$에 관하여 정리하면,

\[ y = \frac{x \pm \sqrt{x^2+4(x^2\pm 1)}}{2} \]

를 얻는다. 이제 $y$가 음이 아니므로 위 등식에서 음이 되는 경우를 제외하면

\begin{equation} y=\frac{1}{2}\left( x+\sqrt{5x^2\pm 4} \right) \tag{4} \end{equation}

와 같이 정리할 수 있다.

$ $

$(\Longrightarrow)$ 먼저 $x$가 피보나치 수라 가정하자. 따라서 적당한 정수 $n$이 존재하여 $x=F_n$을 만족한다. 따라서 정리 2에 의하여 $y=F_{n+1}$는 방정식 (3)의 해가 된다. 따라서 $y$는 등식 (4)의 우변과 같이 정리할 수 있고, 이로부터 $\sqrt{5x^2 \pm 4}$가 정수여야만 함을 알수있다. 따라서 $5x^2 \pm 4$는 완전제곱수이다.

$ $

$(\Longleftarrow)$ 이제 $5x^2 \pm 4$가 완전제곱수라 가정해보자. 따라서 $\sqrt{5x^2 \pm 4}$는 정수이다. 여기서 $x$는 정수이므로 언제나 짝수이거나 홀수이다. 먼저 $x$가 짝수인 경우, $x^2$가 짝수이고 $5x^2 \pm 4$ 또한 짝수이므로 $x+\sqrt{5x^2\pm 4}$가 짝수임을 알 수 있다. 따라서 식 (4)의 우변이 정수이고, $y$ 또한 (음이 아닌) 정수임을 알 수 있다. 만약 $x$가 홀수라면, $x^2$가 홀수이고 $5x^2 \pm 4$ 또한 홀수이므로 $x+\sqrt{5x^2\pm 4}$가 짝수가 되어, 식 (4)의 우변이 정수임을 알 수 있다. 따라서 이 경우에도, $y$는 (음이 아닌) 정수임을 알 수 있다.

따라서 두 경우 모두, $x,\, y$는 음이 아닌 정수이면서 방정식 (3)의 해가 된다. 이제 정리 2를 이용하면, $x,\, y$는 인접한 두 피보나치 수임을 알 수 있고, 특히 $x$는 피보나치 수임을 알 수 있다..

$ $

예제. $x = 2,584$이라 하자. 그러면

\[ 5(2,584)^2 + 4 = 33,385,284 = (5,778)^2 \]

따라서 정리 3에 의해 $x = 2,584$는 피보나치 수임을 알 수 있다. 실제로 $F_{16} = 2,584$이다..