피보나치 수는 많은 성질을 가지고 있다.
이 포스트에서 소개하고자 한다.
여기서 살펴볼 피보나치수열은 다음과 같다.
$F_1 = 1, F_2 = 1, F_n = F_{n-1} + F_{n-2} \ (n\ge3)$
1. $\sum_{k=1}^n F_k = F_{n+2} - 1$
정의에 따라
$F_1 = F_3 - F_2$
$F_2 = F_4 - F_3$
...
$F_n = F_{n+2} - F_{n+1}$
이다.
그럼 식을 다음과 같이 변형할 수 있다.
$F_1+F_2+...+F_n$
$= (F_3-F_2)+(F_4-F_3)+...+(F_{n+2}-F_{n+1})$
$= F_{n+2} - F_2$
$= F_{n+2} - 1$
이를 통해
$\sum_{k=a}^b F_k $
$= \sum_{k=1}^b F_k - \sum_{k=1}^{a-1} F_k$
$= F_{b+2}-F_{a+1}$
가 된다.
2. $\sum_{k=1}^n F_{2k - 1} = F_{2 n}$
3. $\sum_{k=1}^n F_{2k} = F_{2 n + 1}-1$
4. $\sum_{k=1}^n {F_k}^2 = F_nF_{n+1}$
5. $gcd(F_a,F_b) = F_{gcd(a, b)}$
6. $M = 10^k \ (k \ge 3)$일 때 $F_n \equiv a \pmod {M}$
2, 3, 4의 증명은 1과 같은 방식으로 할 수 있다.
(5, 6의 증명은 공부를 더한 후 올려야겠다..)
6은 피사노 주기로 알려져 있다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] 이분탐색 (0) | 2021.12.23 |
---|---|
[알고리즘] 알고리즘 문제를 풀 때 알면 좋은것들 (0) | 2021.12.05 |
[알고리즘] 모듈러 연산과 페르마의 소정리 (0) | 2021.12.02 |
[알고리즘] 분할 정복을 이용한 거듭제곱 (0) | 2021.12.02 |
[알고리즘] 피보나치 수 구하기 (0) | 2021.12.02 |