jjycjn's Math Storehouse

피보나치 수열(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$가 피보나치 수열의 항인지..