피보나치수열은 초등학생도 흔히 접하는 매우 간단한 형태의 수열이다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...
그런데 이 간단한 수열에도 파고들면 수많은 수학적 의미를 찾을 수 있다. 한번 그 의미를 알아보자.
참고로 FnFn이 의미하는 바는 nn번째 피보나치 수로 F1=1F1=1, F2=1F2=1, F3=2F3=2이다.
홀짝성(기우성)
아주 간단한 성질이다. 피보나치수열의 원소는 홀수, 홀수, 짝수, 그리고 반복을 이룬다.
이가 성립하는 이유는 다음과 같다.
F1=1F1=1 (홀수), F2=1F2=1 (홀수)이다.
홀수+홀수=짝수이므로 다음 F3F3은 짝수이고
F4F4는 홀수+짝수=홀수가 되어 홀수
F5F5는 짝수+홀수=홀수가 되어 홀수
F6F6는 홀수+홀수=짝수가 되어 짝수
반복...
이를 수학적으로 일반화하면 다음과 같이 쓸 수 있다.
F3n≡0(mod2)F3n≡0(mod2)
F3n+1≡F3n+2≡1(mod2)F3n+1≡F3n+2≡1(mod2)
n∈N
인접한 두 원소의 최대공약수
피보나치수열에서 인접한 두 원소는 서로소이다(최대공약수가 1이다). 이는 유클리드 호제법으로 증명할 수 있다.
우선 Fn=Fn−1+Fn−2, Fn−1=Fn−2+Fn−3이므로 gcd(Fn,Fn−1)=gcd(Fn−1+Fn−2,Fn−1)이다. 이를 가지고 유클리드 호제법을 사용하면 다음과 같다.
|Fn−1+Fn−2Fn−1Fn−1Fn−2Fn−1|
혹은
Fn−1+Fn−2=1×(Fn−1)+Fn−2
유클리드 호제법의 결과로부터 다음과 같은 결론을 내릴 수 있다.
gcd(Fn,Fn−1)=gcd(Fn−1+Fn−2,Fn−1)=gcd(Fn−1,Fn−2)
따라서 gcd(Fn,Fn−1)=gcd(Fn−1,Fn−2)이다.
이 결론을 임의의 Fn과 Fn−1에 반복해서 적용하면 이 둘의 최대공약수는 F1과 F2의 최대공약수와 같다는 결론이 나온다.
1과 1의 최대공약수는 1, 즉 인접한 모든 피보나치수의 최대공약수는 1로 서로소이다.
'수학 > 대수학' 카테고리의 다른 글
피보나치수열의 일반항 (0) | 2021.08.22 |
---|---|
동차점화식의 일반항 (0) | 2021.07.29 |
원주율의 근사방법 (0) | 2021.07.14 |
유클리드 호제법과 디오판토스 방정식 (0) | 2021.06.26 |
일반항과 점화식 (0) | 2020.12.31 |