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

피보나치 수열은 $F_{1} = F_{2} = 1$, $F_{n+2} = F_{n+1} + F_{n}$으로 귀납적으로 정의되는 수열로서 전혀 관련이 없는듯 보이는 수학의 여러가지 분야에서 심심치 않게 등장하고는 한다. 아래 글은 피보나치 수열의 수학의 여러 분야로의 활용에 대해 다루고 있다.

• 피보나치 수(Fibonacci number) 판별법
• 피보나치 수열(Fibonacci sequence)과 역코탄젠트(arccotangent) 함수

이번 글에서는 피보나치 수열을 행렬이론_{(matrix theory)}과 조합론_{(graph theory)}의 두가지 관점에서 바라보고자 한다. 우선 다음과 같이 $4 \times 4$행렬 $M$을 정의하자. \[ M = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \] 또한 $\{e_1,\, e_2,\, e_3,\, e_4\}$를 $\R^4$의 기본기저_{(standard basis)}라 하고, $e = e_1 + e_2 + e_3 + e_4$로 정의하자. 즉, $e_i$는 $i$번째 원소만 $1$이고 나머지 모든 원소는 $0$인 열벡터이고, $e$는 모든 원소가 $1$인 열벡터이다. 이번 글의 최종 목적은 식 $F_{n+1} = e^{\T} M^{n} e_{1}$을 행렬이론과 조합론의 두가지 관점으로 각각 증명해 보는 것이다.

 

보조정리.

임의의 자연수 $k \in \N$에 대하여, $e^{\T}M^{k}e_{1} = e^{\T}M^{k}e_{4}$, $e^{\T}M^{k}e_{2} = e^{\T}M^{k}e_{3}$가 성립한다.

증명. 우선 다음과 같이 $4 \times 4$ 행렬 $R$을 정의하자. \[ R = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \] 그러면 간단한 계산을 통해서 $R^2 = I$, $M = RMR$이 성립함을 확인할 수 있다. 따라서 임의의 $k \in \N$에 대하여, \[ M^{k} = (RMR)^{k} = (RMR)(RMR) \cdots (RMR) = RM^{k}R \] 이 성립한다. 한편, $Re_{1} = e_{4}$, $Re_{2} = e_{3}$, $e^{\T}R = e^{\T}$ 이므로, \[ e^{\T}M^{k}e_{1} = e^{\T}(RM^{k}R)e_{1} = (e^{\T}R)M^{k}(Re_{1}) = e^{\T}M^{k}e_{4} \] 를 얻는다. 마찬가지 방법으로 $e^{\T}M^{k}e_{2} = e^{\T}M^{k}e_{3}$임을 보일 수 있다.$ $

정리.

$F_n$을 피보나치 수라 하자. 그러면 임의의 음이 아닌 정수 $n \geq 0$에 대하여, \[ F_{n+1} = e^{\T} M^{n} e_{1} = \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}^{n} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} \tag*{$\textcolor{myblue}{(\ast)}$}\] 가 성립한다. (단, $M^{0} = I$로 정의한다.)

증명 1. 먼저 $n = 0,\, 1$일 때, $F_1 = 1$, $F_2 = 1$임은 간단히 확인할 수 있다. 한편, $Me_{1} = e_{2}$이고, $Me_{2} = e_{1} + e_{3}$이므로 $M^{2}e_{1} = e_{1} + e_{3}$가 성립한다. 따라서 위 보조정리에 의해서 \[ \begin{align*} F_{n+2} &= e^{\T} M^{n+1} e_{1} \\[5px] &= e^{\T} M^{n-1} (M^2 e_{1}) \\[5px] &= e^{\T} M^{n-1} (e_{1} + e_{3}) \\[5px] &= e^{\T} M^{n-1} e_{3} + e^{\T} M^{n-1} e_{1} \\[5px] &= e^{\T} M^{n-1} e_{2} + e^{\T} M^{n-1} e_{1} \\[5px] &= e^{\T} M^{n}e_{1} + e^{\T} M^{n-1} e_{1} \\[5px] &= F_{n+1} + F_{n} \end{align*} \] 즉, 식 $\textcolor{myblue}{(\ast)}$의 우변이 피보나치 수열의 점화식을 만족하므로 원하는 정리를 얻는다.$ $

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

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

이제 $i = 2,\, 3,\, 4$에 대하여, 점 $v_i$에서 출발하고 길이가 $n$인 모든 보행의 경우의 수를 $w_i(n)$으로 각각 정의하자. 그러면 대칭성에 의해 $w_1(n) = w_4(n)$, $w_2(n) = w_3(n)$이 성립한다. 한편, 점 $v_1$에서 출발하는 보행은 첫번째 단계에 점 $v_2$를 지나야 하므로, $w_1(n+1) = w_2(n)$이 된다는 사실을 알 수 있다. 비슷한 이유로 점 $v_2$에서 출발하는 보행은 첫번째 단계에 점 $v_1$ 또는 점 $v_3$를 지나야 하므로, $w_2(n+1) = w_1(n) + w_3(n)$이 성립한다. 이를 종합하면, \[ w_1(n+2) = w_2(n+1) = w_3(n) + w_1(n) = w_2(n) + w_1(n) = w_1(n+1) + w_1(n) \] 을 얻는다. 즉, $w_1(n)$은 피보나치 수열의 점화식을 만족하고 $F_{n+1} = w_1(n)$이 성립한다.$ $