[알고리즘] 피보나치 수열의 성질

피보나치 수는 많은 성질을 가지고 있다.

이 포스트에서 소개하고자 한다.

 

여기서 살펴볼 피보나치수열은 다음과 같다.

$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은 피사노 주기로 알려져 있다.