피보나치 수열(Fibonacci sequence)과 그래프(graph)

written by jjycjn   2019. 7. 17. 16:21
피보나치 수열은 F1=F2=1, Fn+2=Fn+1+Fn으로 귀납적으로 정의되는 수열로서 전혀 관련이 없는듯 보이는 수학의 여러가지 분야에서 심심치 않게 등장하고는 한다. 아래 글은 피보나치 수열의 수학의 여러 분야로의 활용에 대해 다루고 있다. 이번 글에서는 피보나치 수열을 행렬이론(matrix theory)과 조합론(graph theory)의 두가지 관점에서 바라보고자 한다. 우선 다음과 같이 4×4행렬 M을 정의하자. M=[0100101001010010] 또한 {e1,e2,e3,e4}R4의 기본기저(standard basis)라 하고, e=e1+e2+e3+e4로 정의하자. 즉, eii번째 원소만 1이고 나머지 모든 원소는 0인 열벡터이고, e는 모든 원소가 1인 열벡터이다. 이번 글의 최종 목적은 식 Fn+1=eTMne1을 행렬이론과 조합론의 두가지 관점으로 각각 증명해 보는 것이다.
 
보조정리. 임의의 자연수 kN에 대하여, eTMke1=eTMke4, eTMke2=eTMke3가 성립한다.

증명.
우선 다음과 같이 4×4 행렬 R을 정의하자. R=[0001001001001000] 그러면 간단한 계산을 통해서 R2=I, M=RMR이 성립함을 확인할 수 있다. 따라서 임의의 kN에 대하여, Mk=(RMR)k=(RMR)(RMR)(RMR)=RMkR 이 성립한다. 한편, Re1=e4, Re2=e3, eTR=eT 이므로, eTMke1=eT(RMkR)e1=(eTR)Mk(Re1)=eTMke4 를 얻는다. 마찬가지 방법으로 eTMke2=eTMke3임을 보일 수 있다.


정리. Fn을 피보나치 수라 하자. 그러면 임의의 음이 아닌 정수 n0에 대하여, ()Fn+1=eTMne1=[1111][0100101001010010]n[1000] 가 성립한다. (단, M0=I로 정의한다.)

증명 1.
먼저 n=0,1일 때, F1=1, F2=1임은 간단히 확인할 수 있다. 한편, Me1=e2이고, Me2=e1+e3이므로 M2e1=e1+e3가 성립한다. 따라서 위 보조정리에 의해서 Fn+2=eTMn+1e1=eTMn1(M2e1)=eTMn1(e1+e3)=eTMn1e3+eTMn1e1=eTMn1e2+eTMn1e1=eTMne1+eTMn1e1=Fn+1+Fn 즉, 식 ()의 우변이 피보나치 수열의 점화식을 만족하므로 원하는 정리를 얻는다.

증명 2. 위 정리를 조합론적인 방법으로 증명해 보자. 우선 식 () 우변의 행렬 M은 아래와 같은 그래프의 인접행렬(adjacency matrix)로 이해할 수 있다.



따라서 식 ()의 우변은 위 그래프의 점 v1에서 출발하고 길이가 n인 모든 보행(walk)의 경우의 수를 나타낸다. 이 경우의 수를 w1(n)으로 정의하자. 그러면 위 정리는 Fn+1=w1(n)이 성립함을 보이는 것과 같다. 실제로 n=0,1,2,3,4일 때 w1(n)의 값을 직접 계산해 보면 다음과 같이 각각 1,1,2,3,5임을 알 수 있다. (점의 개수가 4개 뿐이기 때문에, w1(4)6임에 주의하자.)


이제 i=2,3,4에 대하여, 점 vi에서 출발하고 길이가 n인 모든 보행의 경우의 수를 wi(n)으로 각각 정의하자. 그러면 대칭성에 의해 w1(n)=w4(n), w2(n)=w3(n)이 성립한다. 한편, 점 v1에서 출발하는 보행은 첫번째 단계에 점 v2를 지나야 하므로, w1(n+1)=w2(n)이 된다는 사실을 알 수 있다. 비슷한 이유로 점 v2에서 출발하는 보행은 첫번째 단계에 점 v1 또는 점 v3를 지나야 하므로, w2(n+1)=w1(n)+w3(n)이 성립한다. 이를 종합하면, w1(n+2)=w2(n+1)=w3(n)+w1(n)=w2(n)+w1(n)=w1(n+1)+w1(n) 을 얻는다. 즉, w1(n)은 피보나치 수열의 점화식을 만족하고 Fn+1=w1(n)이 성립한다.


  ::  
  • 공유하기  ::