비네의 공식과 피보나치 수열

시작하기 전...

• $\phi$ , $\psi$ 를 $x^2-x-1=0$ 의 두 근 이라고 하면,

  $\phi=\cfrac{1+\sqrt5}{2}$, $\psi=\cfrac{1+\sqrt5}{2}$

비네의 공식 (Binet's formula)

• 음이 아닌 정수 $n$ 에 대해 아래의 공식이 성립한다.

  $F_n=\cfrac{\phi^n-\psi^n}{\phi-\psi}=\cfrac{1}{\sqrt5}(\phi^n-\psi^n)$

피보나치 수열의 일반항

• 비네의 공식을 활용하여 피보나치 수의 일반항을 구할 수 있다.

  $a_n=\cfrac{1}{\sqrt5}( \left(\cfrac{1+\sqrt5}{2}\right)^n - \left(\cfrac{1-\sqrt5}{2}\right)^n)$

• $x \le y$가 음이 아닌 정수일 때, $x, y$ 가 인접한 두 피보나치 수일 필요충분조건은 아래와 같다.

  $y^2-xy-x^2=\pm1$

• $x$가 음이 아닌 정수라 하자. 그러면 $x$가 피보나치 수일 필요충분조건은 아래와 같다.

  $5x^2+4$ 또는 $5x^2-4$가 완전제곱수(perfect square)인 것이다.

• ref
  • https://jjycjnmath.tistory.com/369
  • https://shoark7.github.io/programming/algorithm/피보나치-알고리즘을-해결하는-5가지-방법