Back   Contents

單堆遊戲

費氏數和之證明

         每一個正整數n均可表示為某些不相鄰的費氏數之和：

n = ++ … +,
其中 …，
而且k₁k₂+2,  k₂k₃+2, … , k_r–1k_r+2。

<證明>

1. 當n為費氏數時，表示n =，滿足此定理。
    

2. 當n不為費氏數時

(1)          當n = 4（不為費氏數的最小正整數）

因為4 = 3 + 1
所以 n =+，其中,為兩個不相鄰的費氏數

(2)     假設所有小於m的正整數n都可用不相鄰的費氏數之和表示，

而且m不是費氏數，則找出小於m之最大費氏數，則
(i)     0 < m－< m
(ii)    m－<

因為若 m－
則 =+
                  (m－) + 
                 = m
   大於又小於m，
但是小於m之最大費氏數，我們得到矛盾。

例如：

m = 19，則 = 13 =
而 19－13 = 6 < 8 =

由(i)及假設知，m－可用不相鄰的費氏數之和表示
即 m－= ++ … +,
其中 >> … >，
且 k₁k₂+2, （因為(ii)）
      k₂k₃+2, …… , k_r–1k_r+2
所以 m = +++ … +

由(1)(2)及數學歸納法得證。