피보나치수열의 성질

피보나치수열은 초등학생도 흔히 접하는 매우 간단한 형태의 수열이다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...

 

그런데 이 간단한 수열에도 파고들면 수많은 수학적 의미를 찾을 수 있다. 한번 그 의미를 알아보자.

 

참고로 $F_n$이 의미하는 바는 $n$번째 피보나치 수로 $F_1=1$, $F_2=1$, $F_3=2$이다.

---

홀짝성(기우성)

아주 간단한 성질이다. 피보나치수열의 원소는 홀수, 홀수, 짝수, 그리고 반복을 이룬다.

이가 성립하는 이유는 다음과 같다.

$F_1=1$ (홀수), $F_2=1$ (홀수)이다.
홀수+홀수=짝수이므로 다음 $F_3$은 짝수이고
$F_4$는 홀수+짝수=홀수가 되어 홀수
$F_5$는 짝수+홀수=홀수가 되어 홀수
$F_6$는 홀수+홀수=짝수가 되어 짝수
반복...

이를 수학적으로 일반화하면 다음과 같이 쓸 수 있다.

$F_{3n} \equiv 0(\mathrm{mod}\;2)$

$F_{3n+1}\equiv F_{3n+2}\equiv 1(\mathrm{mod}\;2)$

$n \in \mathbb{N}$

 

---

인접한 두 원소의 최대공약수

피보나치수열에서 인접한 두 원소는 서로소이다(최대공약수가 1이다). 이는 유클리드 호제법으로 증명할 수 있다.

 

우선 $F_n=F_{n-1}+F_{n-2}$, $F_{n-1}=F_{n-2}+F_{n-3}$이므로 $\gcd(F_n,\;F_{n-1})=\gcd(F_{n-1}+F_{n-2},\:F_{n-1})$이다. 이를 가지고 유클리드 호제법을 사용하면 다음과 같다.

 

$\begin{vmatrix}F_{n-1}+F_{n-2}&F_{n-1}\\F_{n-1}&\\F_{n-2}&F_{n-1}\end{vmatrix}$

혹은

$F_{n-1}+F_{n-2}=1\times (F_{n-1})+F_{n-2}$

 

유클리드 호제법의 결과로부터 다음과 같은 결론을 내릴 수 있다.

$\gcd(F_n,\;F_{n-1})$$=\gcd(F_{n-1}+F_{n-2},\:F_{n-1})$$=\gcd(F_{n-1},\:F_{n-2})$

 

따라서 $\gcd(F_n,\:F_{n-1})=\gcd(F_{n-1},\:F_{n-2})$이다.

 

이 결론을 임의의 $F_n$과 $F_{n-1}$에 반복해서 적용하면 이 둘의 최대공약수는 $F_1$과 $F_2$의 최대공약수와 같다는 결론이 나온다.

1과 1의 최대공약수는 1, 즉 인접한 모든 피보나치수의 최대공약수는 1로 서로소이다.