正整數數列遞迴

設數列 {a_n} 滿足如下性質：
(1) a_1=1,a_2=2 。
(2) a_(2n+1)=a_(4n)+1 。
(3) a_(4n+2)=a_(4n+1)+1 。
(4) a_(4n)=a_(2n)+a_n 。
證明所有正整數都出現在 {a_n} 中恰一次。

稍微列個十幾項，發現根本亂跳，找不到規律==

求救

[ 本帖最後由 tsyr 於 2015-7-3 10:29 AM 編輯 ]

右下標可否寫清楚點
有點亂
a_2n+1是指a_(2n) 加1
還是a_(2n+1)
a_4n+1+1這些也是不清楚

抱歉，已修改

若依照 an 的值將，an 由小排到大，並寫出 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 為上列中的偶數，則下列有 2kk+1 的連續兩項
(2) 若 k 為上列中的奇數，則下列有 2k
(3) 並且保持順序，如上列中 a 在 b 之前，則 2a 在 2b 之前

上下列的關係主要是由 a4n=a2n+an 所維持的，
比如說 第五列的 16,10 和第六列的 32,20，a16=8a32=13a10=a16+2a20=a32+3
便使得 a40=a10+a20=a16+a32+2+3=a64+5

走這條路似乎可以說明(證明)出來，但細節麻煩，除非寫成數學歸納法的形式
--------------------補證明??--------------------
上面可看到一點二進位與費波那契進位的端倪。
費波那契進位：例 12=8+3+1=F6+F4+F2=(10101)fib, 20=13+5+2=F7+F5+F3=(101010)fib

如果限定 F2F3 ( F1=F2 只用一個 F2 ) 至多使用一次且不使用相鄰兩項 (因 Fn+2=Fn+1+Fn 可以進位)，則每個正整數都可唯一分解成 F2F3 的和。

即於每一個正整數 n，存在且唯一 I234 且 I 中沒有相鄰的正整數，使得 n=iIFi 

定義 n+=iIFi+1 

Claim2: a2n=an+a2n+1=a+2n+1.
(Claim 2 刻劃如何遞迴計算 an 的值)

Claim1: ak2n+1=a+k2n, for any kNnN0
(其實就是 a2n=an+，為了方便使用數學歸納證明，所以先改寫形式)

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 編輯 ]

哇!雖然有點暴力，但的確看出了一些端倪~

十分感謝，我要好好消化一下