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

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

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

이번 글에서는 피보나치 수열을 행렬이론(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*{$\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*} \]

즉, 식 $\myblue{(\ast)}$의 우변이 피보나치 수열의 점화식을 만족하므로 원하는 정리를 얻는다.$ $

$ $

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

$ $

$ $

따라서 식 $\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)$이 성립한다.$ $

$ $