6. 피보나치 수에 관한 (거의) 모든 것 1

피보나치 수는 막 배우기 시작하는 초보 프로그래머와 뗄래야 뗄 수 없는 관계이다.

범위가 아주 작을 때는 재귀함수, 어느 정도 커질 때는 다이나믹 프로그래밍, 그리고 감당할 수 없을 정도로 커지면 분할 정복을 이용한 거듭제곱까지.

피보나치 수열에 관한 문제는 7677번 문제뿐만이 아니다. 대충 세어도 백준에만 50개가 넘는 피보나치 수열 관련 문제가 있다.

그렇게나 자주 나오는 피보나치 수열인 만큼, 단순히 N번째 피보나치 수를 계산하는 것에서 그치지 않고 피보나치 수열의 합이라거나, 제곱 합이라거나, 최대공약수라거나 이것저것 (뇌절로 읽힐 수도 있는) 바리에이션을 보여 준다.

그 중 간단하게 증명 가능한 것들을 하나씩 증명해 보자. 간단한 녀석들은 두어 줄로 끝이 나니 편하게, 편하게 보자.

 

우선 2086번 문제와 연관된 피보나치 수의 합부터 시작을 해 보자.

$S_n=\sum _0^n{F}_i$라고 두자. 그러면 당연히 $S_0=0=F_2-1$이 된다.

또한 $S_n=F_{n+2}-1$이 $n=k$일 때 성립한다면, $S_{k+1}=S_k+F_{k+1}=F_{k+2}-1+F_{k+1}=F_{k+3}-1$이 되므로, 수학적 귀납밥에 의해서 임의의 n에 대해서 다음 식이 성립한다.

$$\sum _0^n{F}_i=S_n=F_{n+2}-1$$

 

다음은 1788번 문제와 연관된 음의 피보나치 수열을 살펴 보도록 하자.

$F_{-1}=F_1-F_0=1$이고, $F_{-2}=F_0-F_{-1}=-1$이니, $n<3$일 때 $F_{-n}=(-1{)}^{n+1}{F}_n$이 성립하게 된다.

$n<k$일 시 $F_{-n}=(-1{)}^{n+1}{F}_n$이 성립한다고 치자. 그러면 $F_{-n}=F_{-n+2}-F_{-n+1}=(-1{)}^{n-1}{F}_{n-2}-(-1{)}^n{F}_{n-1}=(-1{)}^{n-1}(F_{n-2}+F_{n-1})=(-1{)}^{n+1}{F}_n$이 되어버린다.

따라서, 수학적 귀납법에 의해 임의의 n에 대해서 다음 식이 성립한다.

$$F_{-n}=(-1{)}^{n+1}{F}_n$$

 

다음은 11443번 문제와 관련된 짝수 번째 피보나치 수의 합을 살피자. 다행히 이건 귀납법 없이 다음과 같은 식을 이용하여 바로 증명할 수 있다.

$$\sum _0^n{F}_{2i}=\sum _1^n{F}_{2i}=\sum _1^n(F_{2i-2}+F_{2i-1})=\sum _0^{2n-1}{F}_i=F_{2n+1}-1$$

마찬가지로 11442번 문제와 관련된 홀수 번째 피보나치 수의 합도 귀납법 없이 빠르게 증명이 된다.

$$\sum _0^n{F}_{2i+1}=\sum _0^{2n+1}{F}_i-\sum _0^n{F}_{2i}=(F_{2n+3}-1)-(F_{2n+1}+1)=F_{2n+2}$$

 

다음은 11440번 문제와 관련된 피보나치 수의 제곱의 합을 살피자. 이건 아쉽게도 귀납법을 사용한다.

$S_n=\sum _0^n{F}_i^2$로 둘 시 $S_0=0=F_0{F}_1$이 성립한다. $n=k$일 시 $S_n=F_n{F}_{n+1}$이라고 두면, $S_{k+1}=S_k+F_{k+1}^2=(F_k+F_{k+1})F_{k+1}=F_{k+1}{F}_{k+2}$.

따라서 수학적 귀납법에 의해서 다음 식이 임의의 n에 대해서 성립하게 된다.

$$\sum _0^n{F}_i^2=F_n{F}_{n+1}$$

 

다음은 도가뉴 항등식이다. 뭐가 끝도 없이 튀어나온다.

우선 $F_n=F_n{F}_1+F_{n-1}{F}_0$이 성립한다. 또한 $m<k$일 때 $F_{n+m}=F_n{F}_{m+1}+F_{n-1}{F}_m$이 성립한다고 가정하자.

그렇다면 $F_{n+m}=F_{n+m-1}+F_{n+m-2}=(F_n{F}_m+F_{n-1}{F}_{m-1})+(F_n{F}_{m-1}+F_{n-1}{F}_{m-2})=F_n{F}_{m+1}+F_{n-1}{F}_m$이 성립하게 된다.

따라서, 수학적 귀납법에 의해서 다음 식이 임의의 n, m에 대해서 성립하게 된다.

$$F_{n+m}=F_n{F}_{m+1}+F_{n-1}{F}_m$$

 

이 도가뉴 항등식을 통해서 우선 $n\mid N\Rightarrow F_n\mid F_N$임을 보일 수 있다.

당연히 $k=1$일 때 $F_m\mid F_{km}$이다. $k<n$일 시 $F_m\mid F_{km}$이라고 가정을 해 보자.

그럼 방금 증명한 도가뉴 항등식을 통해서 $F_{mn}=F_{m(n-1)}{F}_{m+1}+F_{m(n-1)-1}{F}_m$이다. $F_m,F_{m(n-1)}$ 모두 $F_m$의 배수이므로, $F_{mn}$ 또한 그러하다.

따라서 수학적 귀납법에 의해서 $F_m\mid F_{mn}$임을 보일 수가 있고, 이는 조금 세련되게 다음과 같이 쓸 수 있다. 이는 특정 소수의 배수인 피보나치 수를 모두 찾을 때 상당히 강력하게 쓰인다.

$$n\mid N\Rightarrow F_n\mid F_N$$

 

다음으로는 두 피보나치 수의 최대공약수를 구하여 보자. 이것은 11778번 문제와 무려 다이아몬드에 달하는 난이도를 가진 17372번 문제에서 요긴하게 사용된다!

유클리드 호제법은 알고 있으리라 믿는다.

우선 유클리드 호제법을 반복적으로 적용하면, 임의의 자연수 n에 대해서 $(F_{n+1},F_n)=(F_n,F_{n-1}=\cdots =(F_3,F_2)=(F_2,F_1)=1$이 성립한다. 서로 이웃하는 두 피보나치 수는 반드시 서로소라는 것이다.

 

인접하지 않은 두 피보나치 수의 최대공약수를 구하려면 도가뉴 항등식을 이용하면 된다.

그러면 $(F_{i+k},F_i)=(F_{i+1}{F}_k+F_{k-1}{F}_i,F_i)=(F_{i+1}{F}_k,F_i)=(F_i,F_k)$가 만족을 한다.

유클리드 호제법을, 피보나치 수의 번호 수로 할 수 있다는 것이다. 이해가 안 된다고?

$(n,m)=(m,r)=(r,s)=\cdots =(d,0)=d$의 꼴로 유클리드 호제법이 작동을 하게 된다면, 두 피보나치 수 $F_n,F_m$에 대해서도 똑같은 방식으로 유클리드 호제법이 작동을 한다는 소리이다!

바로 다음과 같이 말이다. $(F_n,F_m)=(F_m,F_r)=(F_r,F_s)=\cdots =(F_d,F_0)=F_d$

그러니, 다음과 같은 매우 아름다운 공식이 성립하게 된다.

$$gcd(F_n,F_m)=F_{gcd(n,m)}$$

 

피보나치 수에 관한 항등식은 이것 말고도 한참이 더 있다. 아마 글로 한두 개 정도는 더 만들어질 것 같다.

시간과 지면이 부족하니, 일단 이 글은 이쯤에서 마치도록 하자.