是否任意自然數都能被不相同的斐波那契數之和表示?

12-03

附加題: 怎樣的線性遞推數列能表示所有自然數?

主問題：是否任意自然數都能被不相同的斐波那契數之和表示?

答案：是。

可以參考 Zeckendorf"s theorem。

該定理指出：任意正整數都可表示為一個或多個不同的斐波那契數之和。

即，對任意的正整數 $N$ ，存在正整數 $c_igeq2$ ，且滿足 $c_{i+1}geq c_i+1$ ，有：

$N=sum_{i=0}^{m}{F_{a_i}}$

$F_{a_i}$ 表示第 $a_i$ 個斐波那契數。

證明：數學歸納法。

求解：貪心演算法。

上面說的是存在性，其實 Zeckendorf"s theorem 還提出了唯一性：

任意正整數 $N$ 的 Zeckendorf"s representation 都是唯一的。

概念解釋：如果幾個斐波那契數和為 $N$ ，且這些斐波那契數彼此不相鄰，那麼將這幾個數之和稱作 $N$ 的 Zeckendorf"s representation。

唯一性的潛台詞是：任意正整數不但可以表示成一個或多個斐波那契數之和，而且必定擁有一個 Zeckendorf"s representation。

附加題：怎樣的線性遞推數列能表示所有自然數？

補充：這句話含義有些模糊，題主是不是想表達：從一個數列取不同的數，其和能組成任意自然數（限定為正整數似乎更好），這樣的數列具備什麼樣的形式？

答案：這樣的數列需要滿足的形式非常簡單。

此類數列被稱為 complete sequence。

假如一個數列為 $c_n$ ，那麼只需滿足如下性質，該數列就是一個 complete sequence：

① $c_0 = 1$

② 對任意正整數 $kgeq 1$ ，有 $s_{k-1} geq c_k -1$ ，其中 $s_k = sum_{i=0}^{m}{c_i}$

並且這兩個條件是充分必要的。

由上面兩個條件可以得到推論：

① $c_0 =1$

② 對任意正整數 $kgeq 1$ ，有 $2 c_k geq c_{k+1}$

即滿足這兩個性質的數列也是一個 complete sequence。

不過這個推論只是 complete sequence 的充分條件，而不是必要條件。數列 A203074 即為一個反例。

證明從略。

顯然斐波那契數列一定是一個 complete sequence。

Update： @靈劍的答案給出了部分證明過程，我就不贅述了。

這個應該不難證明吧，用數學歸納法，顯然k = 1時命題成立，假定任意k &<= N都能表示為不同的斐波那契數之和，考慮k = N +1，如果它是斐波那契數那結論成立，否則一定存在相鄰的兩個斐波那契數 $a_m < k < a_{m+1}$ ，則 $0 < k - a_m < a_{m + 1} - a_{m} = a_{m-1}$ ，按照歸納法假設 $k - a_m$ 可以表達為不同的斐波那契數之和，而它又小於 $a_m$ （因為 $a_m ge a_{m-1}$ ），所以這不同的數中並不包含 $a_m$ ，所以k=N+1也能表示為不同斐波那契數之和。

從證明過程來看，如果正整數數列的起始項為1，而且滿足 $a_{m-1} < a_m le 2a_{m-1}$ ，那麼都是可以符合條件的。不按順序的可以考慮重新排序之後的數列。

從必要性上來說，對於一個嚴格遞增的序列，如果存在 $S_{m-1} + 1 < a_m$ ，其中 $S_n$ 是 $a_n$ 的前n項和，則 $S_{m-1} + 1$ 顯然無法表示為不相同的項之和，所以必須有 $S_{m-1} + 1 ge a_m$ ，這和我們剛才的充分條件中間好像還差了一點點，所以充要條件等其他人補充吧

===================================================

不用其他人補充了，我們來證明對於任意嚴格遞增的數列 $a_n$ ， $a_1 = 1$ 且 $S_{m-1} + 1 ge a_m$ 就是個充要條件。還是一樣的方法，不過我們需要加強一下這個命題，我們現在證明：

如果數列滿足： $a_1 = 1$ ， $S_{m-1} + 1 ge a_m$ ，則對於任意正整數k，k總能表示為若干不同的 $a_m$ 的和，且：如果 $k le S_m$ ，則k總能表示為 ${a_1, a_2, ..., a_m}$ 中若干不同的數的和。

顯然命題對k = 1成立。

如果命題對k &<= N成立，當k = N+1時，存在 $S_{m-1} le k < S_{m}$ ， $k = S_{m-1}$ 時顯然成立，當 $k > S_{m-1}$ 時， $a_m le k$ ，若 $k = a_m$ ，則命題也成立；否則 $a_m < k < S_{m}$ ， $0 < k - a_m < S_{m-1}$ ，所以根據歸納假設， $k - a_m$ 可以被 ${a_1, a_2, ..., a_{m-1}}$ 中的數的和表示，再加上 $a_m$ ，就可以表示k。