피보나치 수 (Fibonacci numbers)

피보나치 수를 구하는 여러가지 방법 과 https://cp-algorithms.com/algebra/fibonacci-numbers.html를 참고

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) 의 형태로 정의되는 수열. 초기 몇 항의 값은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … 이다

여러가지 DP 문제들의 답이 피보나치 수가 되는 경우도 많고, 또한 수열 자체에도 여러가지 성질들이 많아서 그것들에 관한 문제도 많이 나온다. ko:피보나치 수 참고

비네의 공식(Binet's formula) 이라고 불리는 클로즈드 폼으로 된 일반항 공식이 있기는 하지만, 이 공식을 이용해서 계산하는 것은 실수오차때문에 사용하기 힘들다.

피보나치 수의 점화식도 동차 선형 점화식이므로, 행렬의 거듭제곱을 이용해서 O(logn)에 푸는 것이 효율적인 방법이다.

피사노 주기(pisano period)를 이용하면 F(n) % mod 를 구하는 것을, mod에 대한 피사노 주기 π(mod)를 구한 다음에 F(n%π(mod))%mod 로 계산할 수 있다.

이렇게 피사노 주기를 이용하면, n번째 피보나치수 대신에, n%π(mod) 번째 피보나치수를 구하면 되므로, 시간복잡도가 O(logn)에서 O(log(π(mod)))로 줄어들기는 한다. 하지만, 그냥 O(logn)으로 구하더라도 어지간히 큰 n에 대해서도 매우 빠르게 계산해주기 때문에 굳이 꼭 필요한 경우는 거의 없다.

피보나치 수들의 최대공약수도 피보나치수로 표현된다. 두 피보나치 수의 서로소 여부도 쉽게 알수 있다

위키피디아 참고

합: $ {\displaystyle \sum _{k=0}^{n}F_{k}=F_{n+2}-1} $

교대합: $ {\displaystyle \sum _{k=0}^{n}(-1)^{k+1}F_{k}=(-1)^{n+1}F_{n-1}+1} $

제곱합: $ {\displaystyle \sum _{k=0}^{n}F_{k}^{2}=F_{n}F_{n+1}} $

홀수항의 합: $ {\displaystyle \sum _{k=1}^{n}F_{2k-1}=F_{2n}} $

짝수항의 합: $ {\displaystyle \sum _{k=0}^{n}F_{2k}=F_{2n+1}-1} $

증명은 https://mono-cake.coffee/2019-08-02-GCD-of-fibonacci/ 참고

증명이나 자세한 내용은 https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem 참고. 아래는 요약.