回復 1# tsyr 的帖子
若依照 \( a_n \) 的值將，\( a_n \) 由小排到大，並寫出 \( n \) 的話，會得到
1,
2,
4,3,
8,5,6,
16,9,10,12,7,
32,17,18,20,11,24,13,14,
64,33,34,36,19,40,21,22,48,25,26,28,15,
...
下列和上列的關係為：
(1) 若 \( k \) 為上列中的偶數，則下列有 \( 2k,k+1\) 的連續兩項
(2) 若 \( k \) 為上列中的奇數，則下列有 \( 2k \)
(3) 並且保持順序，如上列中 \( a \) 在 \( b \) 之前，則 \( 2a \) 在 \( 2b \) 之前
上下列的關係主要是由 \( a_{4n} = a_{2n} + a_n \) 所維持的，
比如說 第五列的 16,10 和第六列的 32,20，\( a_{16} = 8, a_{32} = 13, a_{10} = a_{16} +2, a_{20} = a_{32} +3 \)
便使得 \( a_{40} = a_{10} + a_{20} = a_{16} + a_{32} + 2 +3 = a_{64} +5 \)
走這條路似乎可以說明(證明)出來，但細節麻煩，除非寫成數學歸納法的形式
--------------------補證明??--------------------
上面可看到一點二進位與費波那契進位的端倪。
費波那契進位：例 \( 12 = 8 + 3 + 1 = F_6 + F_4 + F_2 = (10101)_{fib}\), \( 20 = 13 + 5 +2 = F_7 + F_5 + F_3 = (101010)_{fib}\)
如果限定 \( F_2, F_3, \ldots \) ( \(F_1 =F_2 \) 只用一個 \( F_2 \) ) 至多使用一次且不使用相鄰兩項 (因 \( F_{n+2} = F_{n+1} +F_n \) 可以進位)，則每個正整數都可唯一分解成 \( F_2, F_3, \ldots \) 的和。
即於每一個正整數 \( n \)，存在且唯一 \( I \subset \{ 2,3,4,\ldots, \} \) 且 \( I \) 中沒有相鄰的正整數，使得 \( n = \sum_{i\in I} F_i \)
定義 \( n^+ = \sum_{i\in I} F_{i+1} \)
Claim2: \( a_{2n}=a_{n}^{+}, a_{2n+1}=a_{2n}^{+}+1 \).
(Claim 2 刻劃如何遞迴計算 \( a_n \) 的值)
Claim1: \( a_{k2^{n+1}}=a_{k2^{n}}^{+} \), for any \( k\in\mathbb{N} , n\in\mathbb{N}_{0} \)
(其實就是 \( a_{2n}=a_{n}^{+} \)，為了方便使用數學歸納證明，所以先改寫形式)
Proof of claim1: For \( k=1 \), 由 \( a_{1}=1, a_{2}=2 \) 及 \( a_{4n}=a_{2n}+a_{n} \) 可得 \( a_{2^{n+1}}=a_{2^{n}}^{+} \)。
Suppose that \( a_{k2^{n+1}}=a_{k2^{n}}^{+} \) for all \( n\in\mathbb{N}_{0} \) is true for any \( k\leq m \) (m is some positive integer).
When \( k=m+1 \) : If k is even, then \( a_{k2^{n+1}}=a_{\frac{k}{2}2^{n+2}}=a_{\frac{k}{2}2^{n+1}}^{+}=a_{k2^{n}}^{+} \).
Therefore, \( a_{k2^{n+1}}=a_{k2^{n}}^{+} \) is also true for this k.
If k is odd, then \( k=2k'+1 \), for some \( k'\in\mathbb{N} \) and \( k'\leq m \).
\( a_{2k}=a_{4k'+2}=a_{4k'+1}+1=a_{8k'}+2 \)
\( a_{k}=a_{2k'+1}=a_{4k'}+1=a_{k'}^{++}+1 \) by induction hypothesis
\( a_{k}^{+}=a_{k'}^{+++}+1^{+}=a_{8k'}+2=a_{2k} \). by induction hypothesis.
∵ \( a_{4n}=a_{2n}+a_{n} \) and \( a_{2k}=a_{k}^{+} \) ∴ \(a_{k2^{n+1}}=a_{k2^{n}}^{+} \) for all \(n\in\mathbb{N}_{0} \)
By mathematical induction, we get \( a_{k2^{n+1}}=a_{k2^{n}}^{+} \), for any \( k\in\mathbb{N} \), \( n\in\mathbb{N}_{0} \)
Proof of claim2
Claim1 \( \Rightarrow a_{2n}=a_{n}^{+} \).
\( a_{2n+1}=a_{4n}+1 =a_{2n}^{+}+1 \) by (2) and claim 1. □
For any \( I\subset\mathbb{N} \), define \( I'=\{n+1\mid n\in I\,\wedge\, n\mbox{ is even}\}, 2I=\{2n\mid n\in I\}, A_{I}=\{a_{n}\mid n\in I\} \).
Let \( I_{1}=\{1\}, I_{k+1}=(2I_{k})\cup I_{k}' \), for \( k\in\mathbb{N} \). (其實是 disjoint uion)
以費波那契進位看 \( A_k \)，會看到 \( A_1 = \{1\}, A_2=\{10\}, A_3=\{100,101\}, A_4=\{1000,1001,1010\}, A_5 = \{10000,10001,10010,10100,10101\} \)，
\( A_k \) 為所有 \( k \) 位的費波那契進位數(可由 claim 2 +數學歸納法證之)。
所以 \( a_n \) 的值遍佈了所有正整數。實際上若將 \( n \) 和 \( a_n \) 分別寫成 2 進位和費波那契進位，
它們的關係就是靠近的兩個 1之間多了 1 個 0。例如 \( a_{5}=a_{(101)_{2}}=(1001)_{fib}=1+5=6 \), \( a_{12}=a_{(1100)_{2}}=(10100)_{fib}=3+8=11 \)，因為 \( n\mapsto a_n \) 其實是把二位進的正整數，每個1前方加入1個0，看作費波那契進位，這樣子在 \( \mathbb N \to \mathbb N \) 的1-1 onto map，所以數列 \( a_n \) 為正整數 \( \mathbb{N} \) 的一個排序
以上，還有一些細節可能不是交待的很清楚，但本質上，就是觀察出遞迴式 claim2，證明它。再從 claim2 寫出?一般式? \( a_n \)
完完全全的暴力破解 \( a_n \)，應該會有其它漂亮的證明吧？！
[ 本帖最後由 tsusy 於 2015-7-3 03:43 PM 編輯 ]
