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

피보나치 수에 관한 여러 가지 성질은 7677번 문제에서 예를 들었듯이 행렬과, 그리고 크게 상관은 없어 보이지만 황금비와도 큰 연관이 있다.

이번 포스트에서는 그 쪽과 관련하여 다루어 볼 예정이다.

 

먼저 피보나치 수의 일반항부터 시작하도록 하자.

일반항을 구하기 위해서 점화식을 이런 등비수열 닮은 꼴의 식으로 나타내 보자. $F_{n+2}-a{F}_{n+1}=b(F_{n+1}-a{F}_n)$의 형태로 말이다.

그러면 $F_{n+2}=F_{n+1}+F_n$과 비교해 보면 $a+b=1,ab=-1$이 된다. $a>b$라고 둔다면, $a=\frac{1+\sqrt{5}}{2}$가 되고, 이것은 황금비이다!

자, 그럼 지금부터는 $a=\varphi ,b=\psi$로 나타내 보자. $\varphi$는 황금비를 나타내는 고전적인 기호이다.

그러면 $F_{n+1}-\varphi F_n=\psi (F_n-\varphi F_n-1)={\psi }^2(F_{n-1}-\varphi F_{n-2})=\cdots ={\psi }^n(F_1-\varphi F_0)={\psi }^n$이 성립한다.

$\varphi$와 $\psi$의 역할을 반대로 두고 방금과 같은 과정을 되풀이한다면, $F_{n+1}-\psi F_n={\varphi }^n$이 성립한다.

두 식의 차이를 구한 뒤 정리하게 되면, 다음과 같이 피보나치 수의 일반항을 얻을 수 있다.

$$F_n=\frac{{\varphi }^n-{\psi }^n}{\varphi -\psi }=\frac{{\varphi }^n-{\psi }^n}{\sqrt{5}}$$

 

바로 여기서, $\psi =-0.618033988749\cdots$라는 것을 떠올려 보자. 그러면 ${\psi }^n$은 충분히 n이 클 때 0에 가까워진다.

사실 $\left|\frac{\psi }{\sqrt{5}}\right|<\frac{1}{2}$가 임의의 자연수 n에 대해서 성립하기 때문에, $F_n=\text{round}\left(\frac{{\varphi }^n}{\sqrt{5}}\right)$이 성립한다. 여기서 round는 반올림을 나타내는 함수.

어떤 수의 반올림을 구하려면, 그 수에 0.5를 더한 다음에 정수 부분만 구해도 무방하다. 그걸 이용하면 $F_n=\lfloor \frac{{\varphi }^n}{\sqrt{5}}+\frac{1}{2}\rfloor$임을 구할 수도 있다.

그에 더 나아가서, 어떤 수 F가 피보나치인 건 확실할 때, 몇 번째 피보나치 수인지도 구해 버릴 수가 있다. 방금 식을 적당하게 변환한다면 다음과 같은 결과가 나오게 된다.

$$n=\lceil \frac{\log (F\sqrt{5}-\frac{1}{2})}{\log \varphi }\rceil$$

F가 매우매우 커질 때는 식 내부의 ½가 별 의미가 없어지므로, 해당 항을 생략한 채 풀면 된다. 이는 10425번 문제의 어려운 풀이에 해당한다.

 

선형 점화식을 가지고 있는 다른 수열들도 행렬의 곱을 통하여 표현할 수 있지만, 피보나치 수는 대칭행렬로 놀라울 만큼 깔끔하게 표현할 수 있어서 행렬 곱셈과 분할 정복을 합친 프로그래밍 연습문제로 자주 활용된다.

7677번 문제의 그 식을 다시 한 번 가지고 왔다.

$$\left[\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n$$  

 

이것으로 카시니 항등식을 증명할 수 있다.

우선, $\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]=A$라고 두자. 2×2 행렬식으로, $detA=-1$임을 알 수 있다.

그 다음으로, 두 행렬의 곱의 행렬식은 두 행렬의 행렬식의 곱과 같으므로, 다음 식이 성립한다.

$$F_{n+1}{F}_{n-1}-F_n^2=det\left[\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right]=det{\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n=(detA{)}^n=(-1{)}^n$$

이게 바로 카시니 항등식이다.

 

뤼카 수열은 피보나치 수열과 완전히 동일한 점화식을 지니지만, $L_0=2,L_1=1$을 만족하는 수열이다.

이 수열의 일반항 $L_n={\varphi }^n+{\psi }^n$과 피보나치 수 간의 관계식 $L_{2n}=5F_n^2+2(-1{)}^n$을 이용하면 방금 전 증명한 카시니 항등식과 쏙 닮은 꼴의 식을 하나 얻을 수 있다.

$5(F_n^2-F_{n+r}{F}_{n-r})=({\varphi }^n-{\psi }^n{)}^2-({\varphi }^{n+r}-{\psi }^{n+r})({\varphi }^{n-r}-{\psi }^{n-r})={\varphi }^n{\psi }^n(\frac{{\varphi }^r}{{\psi }^r}+\frac{{\psi }^r}{{\varphi }^r}-2)$이 성립하게 된다.

여기서 $\varphi \psi =-1$을 사용하면, 방금 그 식은 $(-1{)}^{n-r}({\varphi }^{2r}+{\psi }^{2r})-2(-1{)}^n=(-1{)}^{n-r}{L}_{2r}-2(-1{)}^n$으로 변형.

방금 이용한 뤼카 수열의 일반항을 이용한다면 그 식은 다시 $5(-1{)}^{n-r}{F}_r^2+2(-1{)}^r(-1{)}^{n-r}-2(-1{)}^n=5(-1{)}^{n-r}{F}_r^2$로 변형이 된다.

양변을 5로 나누고 식을 정리하면, 다음과 같은 꼴의 카탈란 항등식을 얻을 수 있다.

$$F_n^2-F_{n+r}{F}_{n-r}=(-1{)}^{n-r}{F}_r^2$$

 

여기서 뇌절의 뇌절을 거치면, 더 일반화된 항등식인 바흐다 항등식을 증명할 수가 있다.

카시니 항등식은 어느 정도 알려져 있고 카탈란 항등식은 적은 수의 사람이어도 일단은 알고 있는 사람이 있기는 하지만, 이 바흐다 항등식은 거의 알려진 바가 없다. 카시니 항등식과 카탈란 항등식으로도 어느 정도는 계산이 되니 어쩌면 당연하다.

하지만 알아두어 나쁠 것은 없다. 증명을 진행해 보도록 하자.

우선 지난 포스트에서 증명한 도가뉴 항등식의 식을 다시 한 번 적어보도록 하자. 이 식을 상당히 자주 활용하기 때문에 다시 되새길 필요가 있다.

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

그러면 방금 그 도가뉴 항등식을 그대로 이용해서 $N=F_{n+i}{F}_{n+j}-F_n{F}_{n+i+j}=(F_n{F}_{i-1}+F_{n+1}{F}_i)F_{n+j}-F_n(F_{i-1}{F}_{n+j}+F_i{F}_{n+j+1})$로 만들 수 있다.

겹치는 항을 지우고 묶으면 방금 그 식은 $F_i(F_{n+1}{F}_{n+j}-F_n{F}_{n+j+1})=(-1{)}^{n+j+1}{F}_i((-1{)}^{n+j}{F}_n{F}_{n+j+1}-(-1{)}^{n+j}{F}_{n+1}{F}_{n+j})$로 변형이 되고.

묶인 괄호 안쪽 식을 자세히 보면, 이전 포스트에서 다룬 음의 피보나치 수열을 활용하면 $(-1{)}^{n+j}{F}_{n+j+1}=F_{-n-j-1}$이고, $-(-1{)}^{n+j}{F}_{n+j}=F_{-n-j}$이 성립하게 된다.

따라서 $N=(-1{)}^{n+j+1}{F}_i(F_{-n-j-1}{F}_n+F_{n+1}{F}_{-n-j})=(-1{)}^{n+j+1}{F}_i{F}_{-j}=(-1{)}^n{F}_i{F}_j$이 성립하게 된다.

완전히 다시 써 보면, 깔끔히 정리된 바흐다 항등식을 얻을 수가 있다.

$$F_{n+i}{F}_{n+j}-F_n{F}_{n+i+j}=(-1{)}^n{F}_i{F}_j$$

여기서 $j=-i$를 대입하게 되면 카탈란 항등식이, $i=1,j=-1$을 대입하게 되면 카시니 항등식이 얻어지게 되는 것이다.

 

아직도 피보나치 수에 관한 항등식은 산더미처럼 있으나, 이 정도로도 필요한 만큼은 채웠다고 생각한다.

코딩 관련된 게시글에서 다시 보도록 하자.