피보나치 수열_{(Fibonacci sequence)} $F_n$은 다음과 같이 귀납적으로 정의되는 수열이다.

이제 피보나치 수열 $F_n$에 나타나는 모든 음이 아닌 정수들을 피보나치 수_{(Fibonacci number)}라 정의하자. 또한 두 피보나치 수 $F_m$과 $F_n$에 대하여 $m = n \pm 1$의 관계가 성립하면, (즉, 두 피보나치 수가 피보나치 수열의 두 인접한 항이면) $F_m$과 $F_n$은 인접한 피보나치 수라 한다.

$ $

벨기에의 수학자 제켄도르프는 "모든 양의 정수는 인접하지 않은 ($F_{0}$와 $F_{1}$을 제외한) 피보나치 수들의 합으로 표현할 수 있고, 그 표현 방법은 유일하다." 라는 내용의 제켄도르프의 정리_{(Zeckendorf's theorem)}를 증명하였다. 예를 들어 $N = 100$인 경우 \[ 100 = F_{11} + F_{6} + F_{4} = 89 + 8 + 3 \] 와 같이 유일하게 표현 가능하다. 물론 \[ \begin{align*} 100 & = F_{10} + F_{9} + F_{6} + F_{4} = 55 + 34 + 8 + 3 \\[5px] 100 & = F_{11} + F_{6} + F_{3} + F_{2} = 89 + 8 + 2 + 1 \end{align*} \] 등과 같이 $100$을 피보나치 수들의 합으로 나타내는 방법은 여러가지가 있을 수 있지만, 위 두 표현 중 첫번째 표현은 $55$와 $34$가, 두번째 표현은 $2$와 $1$이 각각 인접한 피보나치 수들이므로, 제켄도르프의 정리에 위배되지 않는다.

$ $

제켄도르프의 정리를 수학적인 용어를 빌어 표현하면 다음과 같이 정리할 수 있다.

$ $

$ $

증명. 주어진 임의의 양의 정수에 대한 제켄도르프 표현이 존재함을 먼저 보이도록 하자. 수학적 귀납법을 이용할 것이다. 우선 $1 = F_{2}$, $2 = F_{3}$, $3 = F_{4}$이므로 $N = 1,\, 2,\, 3$에 대해서는 제켄도르프 표현이 존재한다. 이제 $N$ 이하의 모든 양의 정수에 대하여 제켄도르프 표현이 존재한다고 가정해 보자. 만약 $N+1$이 피보나치 수라면 자명하게 제켄도르프 표현이 가능하다. 반면 $N+1$이 피보나치 수가 아닌 경우 어떤 인접한 피보나치 수 사이에 존재해야 하므로, $F_{j} < N+1 < F_{j+1}$와 같이 나타낼 수 있다. 이제 $\hat{N} := N + 1 - F_{j}$로 정의하자. 그러면 $\hat{N} \leq N$이므로 귀납법 가정에 의해 $\hat{N}$에 대한 제켄도르프 표현이 존재한다. 또한 \[ \hat{N} = N + 1 - F_{j} < F_{j+1} - F_{j} = F_{j-1} \] 이 성립하므로, $\hat{N}$의 제켄도르프 표현은 $F_{j-1}$이 포함되지 않음을 알 수 있다. 그러므로 $N+1 = \hat{N} + F_{j}$의 제켄도르프 표현이 존재함을 알 수 있고, 수학적 귀납법에 의해 임의의 양의 정수에 대한 제켄도르프 표현이 존재한다.

$ $

이제 제켄도르프 표현의 유일성을 증명하도록 하자. 이를 위해 $Z(N)$을 $N$에 대한 서로 다른 제켄도르프 표현 방법의 개수로 정의하자. 위에서 제켄도르프 표현의 존재성을 보였으므로, 모든 양의 정수 $N$에 대하여 $Z(N) \geq 1$임을 알 수 있고, 우리의 목적은 실제로 $Z(N) = 1$임을 보이는 것이다.

우선 $Z(1) = 1$임은 자명하다. 이제 $N \geq 2$의 제켄도르프 표현이 다음과 같이 주어졌다고 가정하자. \[ N = F_{n_1} + F_{n_2} + \cdots + F_{n_{k}}. \] 여기서 $n_i \geq 2$이고 $n_{i+1} - n_{i} \geq 2$을 만족한다. 이제 다음의 사실을 증명 없이 받아들이기로 하자. (아래 사실은 수학적 귀납법등을 통해 간단히 증명 가능하다.) \[ \left\{ \begin{align*} F_{3} + F_{5} + \cdots + F_{2n-1} = F_{2n} - 1, \; (n \geq 2) \\[5pt] F_{2} + F_{4} + \cdots + F_{2n} = F_{2n+1} - 1, \; (n \geq 1) \\[5pt] \end{align*} \right. \] 그러면 위 사실로부터 \[ \begin{align*} N - 1 & = (F_{n_1} - 1) + F_{n_2} + \cdots + F_{n_{k}} \\[5pt] & = \begin{cases} F_{n_2} + \cdots + F_{n_{k}} & \text{if $n_1 = 2$}, \\[5pt] F_{3} + F_{5} + \cdots + F_{n_1-1} + F_{n_2} + \cdots + F_{n_{k}} & \text{if $n_1 > 2$ and even}, \\[5pt] F_{2} + F_{4} + \cdots + F_{n_1-1} + F_{n_2} + \cdots + F_{n_{k}} & \text{if $n_1 > 2$ and odd}. \\[5pt] \end{cases} \end{align*} \] 이 $N-1$의 제켄도르프 표현이 된다. 즉, $N$의 제켄도르프 표현으로 부터 $N-1$의 제켄도르프 표현을 언제나 얻을 수 있고, 이는 임의의 $N \geq 2$에 대하여 $Z(N) \leq Z(N-1)$이 성립함을 의미한다. 한 편, 임의의 $N \geq 2$에 대하여, $N \leq F_{N+1}$이 성립하고, $Z(F_{N+1}) = 1$이므로, \[ 1 = Z(F_{N+1}) \leq \cdots \leq Z(N) \leq \cdots \leq Z(2) \leq Z(1) = 1 \] 를 얻고, 따라서 $Z(N) = 1$임을 알 수 있다.$ $

$ $

참고. 제켄도르프 표현의 유일성 증명을 보면, 임의의 $N \geq 2$에 대하여 부등식 $Z(N) \leq Z(N-1)$한다는 사실은 $N$에 대한 제켄도프르 표현의 존재성의 여부에 상관 없이 항상 성립함을 알 수 있다. 이를 바탕으로 임의의 $N \geq 2$에 대하여 $Z(N) = 1$을 보였으므로, 사실은 제켄도르프 표현의 유일성과 존재성을 한번에 모두 증명한 셈이 된다. 하지만 이 사실만으로는 주어진 양의 정수 $N$에 대한 제켄도르프 표현이 실제로 어떻게 구성되는지는 알 수 없으므로, 제켄도르프 표현의 존재성에 대한 구성적 증명을 추가하였다.$ $

$ $

참고. 제켄도르프 표현의 존재성 증명을 보면 양의 정수 $N$이 주어졌다고 할 때, $N$보다 크지 않은 피보나치 수 중에서 가장 큰 피보나치 수를 택하고, 그 수를 $N$에서 빼준 뒤, 다시 그 수보다 크지 않은 피보나치 수 중에서 가장 큰 피보나치 수를 택하여 빼주는 과정을 반복하면, $N$의 제켄도르프 표현을 얻을 수 있음을 알 수 있다. 예를 들어 $N = 100$인 경우, $100$보다 작은 피보나치 수 중에서 가장 큰 피보나치 수는 $F_{11} = 89$이고, $100 - 89 = 11$보다은 피보나치 수 중에서 가장 큰 피보나치 수는 $F_{4} = 8$이며, 마지막으로 $11 - 8 = 3$은 그 자체가 피보나치 수 $F_{4}$이므로, \[ 100 = F_{11} + F_{6} + F_{4} = 89 + 8 + 3 \] 가 $N = 100$의 제켄도르프 표현이 된다.$ $