피보나치 수열 심화과정3 -모든 자연수는 피보나치 수의 합으로 유일하게 분해할 수 있다(제켄도르프의 정리)-

1. 피보나치 수

 

피보나치 수열 $F_{n}$을 다음과 같이 정의하고, $F_{n}$을 피보나치 수라고 하자.

 

$F_{0} = 0, F_{1} = F_{2} = 1$, $F_{n} = F_{n-1} + F_{n-2}, n \geq 2$

 

두 피보나치 수 $F_{m}$과 $F_{n}$에 대하여 m = n+1 혹은 m = n-1이면 두 피보나치 수가 인접하다고 한다.

 

즉, $F_{n+1}$과 $F_{n}$은 인접한 피보나치 수이며 $F_{n}$과 $F_{n-1}$은 인접한 피보나치 수이다.

 

 

2. 제켄도르프의 정리(Zeckendorf's theorem)

 

"모든 자연수는 인접하지 않은 피보나치 수($F_{0}$, $F_{1}$을 제외한)들의 합으로 표현할 수 있으며, 그 표현 방법이 유일하다"

 

예를 들어 n = 100이라고 한다면..

 

$$100 = F_{11} + F_{6} + F_{4} = 89 + 8 + 3$$과 같이 유일하게 분해할 수 있다.

 

물론 $100 = F_{10} + F_{9} + F_{6} + F_{4} = 55 + 34 + 8 + 3$과

 

$100 = F_{11} + F_{6} + F_{3} + F_{2} = 89+8+2+1$으로 표현도 가능하지만, 

 

전자는 $F_{10}$과 $F_{9}$로 인접한 피보나치 수를 사용했으며 후자는 $F_{3}$과 $F_{2}$로 인접한 피보나치 수를 사용했다.

 

수학적으로 다음과 같이 기술할 수 있다.

 

양의 정수 N이 주어졌다고 하자. 그러면 $n_{i} \geq 2$이고 $n_{i+1} - n_{i} \geq 2$를 만족하는 양의 정수

 

$n_{1} < n_{2} < ... < n_{k} (k \geq 1)$들이 유일하게 존재하여,

 

$$N = \sum_{i = 1}^{k} F_{n_{i}} = F_{n_{1}} + F_{n_{2}} + ... + F_{n_{k}}$$와 같이 나타낼 수 있다.

 

이를 N에 대한 제켄도르프 표현(Zeckendorf representation)이라고 부른다.

 

 

3. 증명

 

까다롭긴 한데, 증명하는 방법을 이해해야 구현까지 가능할것 같아서

 

따라가보긴 해야할듯

 

3-1) 존재성에 대한 증명

 

임의의 양의 정수에 대해 제켄도르프 표현이 존재함을 수학적 귀납법을 이용해 먼저 증명한다

 

우선 N = 1,2,3에 대하여 $1 = F_{2}$, $2 = F_{3}$, $3 = F_{4}$이므로 제켄도르프 표현이 존재한다.

 

이제 N이하의 모든 양의 정수에 대해 제켄도르프 표현이 존재한다고 가정하자.

 

N+1이 피보나치 수라면, 그 자체로 제켄도르프 표현이며 따라서 자명하게 제켄도르프 표현이 가능하다.

 

그러면 N+1이 피보나치 수가 아닌 경우에 제켄도르프 표현이 가능한지만 보이면 된다.

 

N+1이 피보나치 수가 아니라면, 어떠한 피보나치 수 $F_{j}$와 $F_{j+1}$ 사이에 존재해야하므로,

 

$F_{j} < N+1 < F_{j+1}$로 나타낼 수 있다. (단, 정리에서 j는 0이 아니라고 가정했다)

 

이제 $M = (N+1)-F_{j}$라고 정의하자. $M \leq N$이므로, M은 N이하의 양의 정수이고, 수학적 귀납법 가정에 의해

 

M에 대한 제켄도르프 표현이 존재한다. 

 

또한, $$M = N+1 - F_{j} < F_{j+1} - F_{j}$$이다.

 

그런데, $F_{j+1} = F_{j} + F_{j-1}$이므로, $$M = N+1-F_{j} < F_{j-1}$$이다.

 

그러므로, M에 대한 제켄도르프 표현에 $F_{j-1}$은 포함되지 않는다.

 

왜냐하면 제켄도르프 표현이라는건 M이하의 피보나치 수의 합으로 분해하는 것인데, $F_{j-1}$이 M보다 크기 때문이다.

 

이제 $N + 1 = M + F_{j}$에 대해 생각해보자.

 

$M$이 $F_{j-1}$을 포함하지 않는, $F_{j-2}$이하의 피보나치 수에 의해 제켄도르프 분해가 가능하므로,

 

$N+1 = (M에 대한 제켄도르프 분해) + F_{j}$이고,

 

(M에 대한 제켄도르프 분해)가 $F_{j}$와 인접하지 않은 피보나치 수만을 포함하므로,

 

$N+1$의 제켄도르프 분해가 반드시 존재한다.

 

따라서, 수학적 귀납법에 의해 모든 양의 정수 N에 대한 제켄도르프 분해가 반드시 존재한다.

 

 

3-2) 유일성에 대한 증명

 

이제 제켄도르프 표현이 유일하다는 것을 보이면 된다.

 

Z(N)이 N에 대한 서로 다른 제켄도르프 표현 방법의 개수라고 정의하자.

 

모든 양의 정수 N에 대해 제켄도르프 분해가 존재한다는 것을 위에서 보였으므로, $Z(N) \geq 1$

 

이 증명의 목적은 $Z(N) = 1$임을 보이는 것이다.

 

우선 Z(1) = 1임은 자명하다. 1은 피보나치 수 1로만 표현할 수 있으니까

 

이제, $N \geq 2$의 제켄도르프 표현이 다음과 같다고 해보자.

 

$$N = F_{n_{1}} + F_{n_{2}} + ... + F_{n_{k}}$$

 

여기서 각 피보나치 수는 인접하지 않아야하므로, $n_{i} \geq 2$이고 $n_{i+1} - n_{i} \geq 2$이다.

 

-----------------------------------------------------------------------------------------------------------

 

**보조정리

 

피보나치 수열 $F_{n}$의 짝수항의 합과 홀수항의 합은 아주 간단하게 구할 수 있는데

 

$$\sum_{k = 1}^{n} F_{2k-1} = F_{2n}$$

 

$$\sum_{k=1}^{n} F_{2k} = F_{2n+1} - 1$$

 

피보나치 수열 - 나무위키 (namu.wiki)

피보나치 수열 - 나무위키

 

(증명)

 

1) 홀수항의 합은 수학적 귀납법으로 증명해보자.

 

n = 1이면 $F_{1} = F_{2} = 1$로 자명하다.

 

자연수 n = m에서 성립한다고 가정해보자. n = m+1에서 성립함을 보여야한다.

 

$\sum_{k = 1}^{m+1} F_{2k-1} = \sum_{k=1}^{m} F_{2k-1} + F_{2m+1} = F_{2m} + F_{2m+1} = F_{2m+2}$

 

즉, $\sum_{k=1}^{m+1} F_{2k-1} = F_{2m+2}$이다.

 

그러므로 모든 자연수 n에 대하여, 홀수항의 합은 $\sum_{k=1}^{n} F_{2k-1} = F_{2n}$이다.

 

 

2) 짝수항의 합은 수식적으로 증명해보자.

 

$F_{n+2} = F_{n+1} + F_{n}$에서 n 대신 2n-1을 대입하면, $F_{2n+1} = F_{2n} + F_{2n-1}$

 

그래서, $F_{2n} = F_{2n+1} - F_{2n-1}$

 

그러므로, $\sum_{k = 1}^{n} F_{2k} = \sum_{k=1}^{n}(F_{2k+1} - F_{2k-1})$

 

수식을 풀어 써보면, 망원급수임을 알 수 있다.

 

$$(F_{3} - F_{1}) + (F_{5} - F_{3}) + (F_{7} - F_{5}) + ... (F_{2n-1} - F_{2n-3}) + (F_{2n+1} - F_{2n-1}) = F_{2n+1} - F_{1} = F_{2n+1} - 1$$

 

-------------------------------------------------------------------------------------------------------------------------------------

 

보조정리로부터 다음이 성립함을 알 수 있다.

 

$$F_{3} + F_{5} + ... + F_{2n-1} = F_{2n} - 1 , (n \geq 2)$$

 

$$F_{2} + F_{4} + ... + F_{2n} = F_{2n+1} - 1 , (n \geq 1)$$

 

그러면 N - 1의 제켄도르프 표현은 $n_{1}$의 값에 따라 다음과 같이 표현할 수 있다.

 

$$N - 1 = (F_{n_{1}} - 1) + F_{n_{2}} + ... + F_{n_{k}} = F_{n_{2}} + ... + F_{n_{k}}, (n_{1} = 2)$$

 

$$N - 1 = (F_{3} + F_{5} + ... + F_{n_{1} - 1}) + (F_{n_{2}} + ... + F_{n_{k}}) , (n_{1} > 2, 짝수)$$

 

$$N - 1 = (F_{2} + F_{4} + ... + F_{n_{1} - 1}) + (F_{n_{2}} + ... + F_{n_{k}}) , (n_{1} > 2, 홀수)$$

 

이 사실은, N에 대한 제켄도르프 표현 $N = F_{n_{1}} + F_{n_{2}} + ... +F_{n_{k}}$로부터

 

반드시 N-1의 제켄도르프 표현을 적어도 1가지 이상은 얻을 수 있음을 말한다.

 

즉, 임의의 $N \geq 2$에 대하여, $Z(N) \leq Z(N-1)$이다.

 

-----------------------------------------------------------------------------------------------------------------------------------------------

 

한편, 임의의 $N \geq 2$에 대하여, $N \leq F_{N+1}$인데, 직관적으로 너무 당연하지만

 

수학적 귀납법으로 생각해보면 N = 2이면, 2는 $F_{3} = 2$ 이하이니 부등식이 참이고

 

2보다 큰 $N = k$에서 부등식이 성립한다고 하면, $k \leq F_{k+1}$이고, 양변에 1을 더하면,

 

$k + 1 \leq F_{k+1} + 1$

 

이 때, k는 2보다 크므로, $1 \leq F_{k}$이고, $k+1 \leq F_{k+1} + 1 \leq F_{k+1} + F_{k} = F_{k+2}$

 

따라서, 2 이상의 자연수 N에 대하여, $N \leq F_{N+1}$

 

---------------------------------------------------------------------------------------------------------------------------------

 

이제, 피보나치 수 $F_{N+1}$의 제켄도르프 표현은 $F_{N+1}$로 유일하므로, $Z(F_{N+1}) = 1$이다.

 

따라서, 부등식 $Z(N) \leq Z(N-1)$을 이용해서, F_{N+1}에 1을 빼가면 다음과 같은 부등식을 얻는다.

 

$$1 = Z(F_{N+1}) \leq Z(F_{N+1} - 1) ... \leq Z(N) \leq ... \leq Z(2) \leq Z(1) = 1$$

 

그러므로, $Z(N) \leq 1$이다.

 

따라서, 2 이상의 자연수 N에 대하여 $Z(N)\geq1$이고, $Z(N)\leq1$이므로, $Z(N) = 1$이다.

 

즉, 모든 자연수 N에 대하여 제켄도르프 표현은 유일하다. (N = 1인 경우는 자명하다)

 

-----------------------------------------------------------------------------------------------------------------------------------------

 

임의의 자연수 $N \geq 2$에 대해, 부등식 $Z(N) \leq Z(N-1)$은 N에 대한 제켄도르프 표현이 존재하는지에 관계없이 성립한다.

 

이를 바탕으로 임의의 $N \geq 2$에 대하여, $Z(N) = 1$임을 보였으므로, 제켄도르프 표현의 유일성과 존재성을 한번에 증명한 셈이다.

 

(그런가??)

 

-----------------------------------------------------------------------------------------------------------------------------------------

 

4. 제켄도르프 표현을 어떻게 구해야하는가

 

제켄도르프 표현의 존재성에 대한 증명을 보면 어떻게 구해야할지 알 수 있다.

 

증명에서, ""$M = N+1 - F_{j} < F_{j-1}$이므로 M에 대한 제켄도르프 표현은 $F_{j-1}$이 포함되지 않고,

 

그러므로 $N+1 = M + F_{j}$의 제켄도르프 표현이 존재함을 알 수 있고""

 

이 부분을 잘 보면, N+1 대신에 N이라고 생각해도 표현이 참이다.

 

즉, $M = N - F_{j} < F_{j-1}$이므로, M에 대한 제켄도르프 표현은 $F_{j-1}$이 포함되지 않는다. 

 

그러므로, $N = M + F_{j}$의 제켄도르프 표현이 반드시 존재하며...

 

바꿔말하면 무슨 말일까..?

 

N보다 크지 않은 피보나치 수 중에서 가장 큰 피보나치 수 $F_{j}$를 택하고, 그 수를 N에서 빼주면 $M = N - F_{j}$이며,

 

다시 M보다 크지 않은 피보나치 수 중에서 가장 큰 피보나치 수(이 수는 적어도 $F_{j-1}$보다 작다)를 택하여 그 수가 $F_{j-k}$라고 한다면...

 

$L = M - F_{j-k} = N - F_{j} - F_{j-k}$...

 

이러한 과정을 반복하면 N의 제켄도르프 분해를 얻을 수 있음을 말하고 있다.

 

예를 들어 N = 100이면, 100보다 작은 피보나치 수중에서 가장 큰 피보나치 수는 $F_{11} = 89$이고

 

100 - 89 = 11보다 작은 피보나치 수중에서 가장 큰 피보나치 수는 $F_{6} = 8$이며,

 

11 - 8 = 3은 그 자체가 피보나치 수 $F_{4} = 3$이므로,

 

$$100 = F_{11} + F_{6} + F_{4} = 89 + 8 + 3$$이 N = 100의 제켄도르프 표현이다.

 

5. 구현 예시 - 제켄도르프 분해 알고리즘

 

1) 주어진 자연수 N보다 작거나 같은 피보나치 수열의 수들 적절하게 생성

 

2) 그 수열을 뒤에서부터 순회해서

 

3) 현재 N보다 작거나 같은 피보나치 수 중에 가장 큰 피보나치 수를 찾고,

 

4) 그 수는 N의 제켄도르프 분해

 

5) 그 수를 N에서 뺀 값을 N으로 갱신

 

6) N이 0이 될때까지 반복

 

def zeckendorf(n):
    
    #find fibonacci sequence
    #n보다 작거나 같은 모든 피보나치 수를 찾는다.
    #현재 O(N) 다이나믹 프로그래밍이지만, 
    #필요에 따라 더 빠른 알고리즘을 선택
    fib = [1,1]

    i = 2

    while 1:
        
        x = fib[i-1] + fib[i-2]

        if x <= n:

            fib.append(x)
            i += 1
        
        else:
            
            break
    
    len_f = len(fib)
    
    #find zeckendorf representation
    
    zeck = []
    
    #n은 반드시 0이 될 수 있으며, 0이 될때까지 반복
    while n > 0:
        
        #가장 큰 피보나치 수부터 순회해서,
        for i in range(len_f-1,-1,-1):
            
            #n보다 작거나 같다면, 그것이 제켄도르프 분해이며,
            if n >= fib[i]:
                
                zeck.append(fib[i])
                
                #제켄도르프 분해를 뺀 값을 새로운 n으로 갱신
                n -= fib[i]
                break
    
    return zeck

print(zeckendorf(100))
[89, 8 ,3]

 

 

참조

 

https://mathstorehouse.com/archives/mathematics/algebra/arithmetic/5943/

피보나치 수열(Fibonacci sequence)을 이용한 자연수의 분할 - Math Storehouse