알고리즘 피보나치 수열

피보나치 수열은 알고리즘에서 자주 등장하는 소재다.
일종의 숫자의 집합이라고 볼 수 있는데,
0, 1, 1, 2, 3, 5, 8, …
이와 같이 0, 1로 시작하며, 세번째 원소부터는
마지막 두 숫자를 더한 값이 되며, 이 조합은 무한히 이어진다.
고로, 8 뒤의 숫자는 5 + 8 = 13 이 된다.
그 다음 원소는 8 + 13 = 21 이 될 것이다.

알고리즘 문제에서 어떤 숫자가 피보나치 수열에 속하는지 아닌지
판별하라면 어떻게 풀어야 할까?

나는 피보나치 수열을 배열로 만든 후,
해당 숫자가 그 배열에 속해 있는지 여부로 판단하는 알고리즘을 짰다.
https://www.hackerrank.com/rest/contests/master/challenges/is-fibo/hackers/lamiru/download_solution

그런데 다른 답안을 보니 상당수가
https://www.hackerrank.com/rest/contests/codesprint5/challenges/is-fibo/hackers/adhikari_suraj/download_solution
이런 식으로 문제를 풀었다.


즉, 해당 숫자를 N이라고 할 때,
5*N*N+4이거나 5*N*N+4이 자연수의 제곱이 되면 된다는 것인데,
왜일까…?

영어판 위키백과에 언급이 되어 있긴 한데….
http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers