Board logo

標題: 正整數數列遞迴 [打印本頁]
作者: tsyr    時間: 2015-7-3 09:07     標題: 正整數數列遞迴

設數列 {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 編輯 ]
作者: Ellipse    時間: 2015-7-3 10:00

引用:
原帖由 tsyr 於 2015-7-3 09:07 AM 發表
設數列 {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} 中恰一次。

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

求救 ...
右下標可否寫清楚點
有點亂
a_2n+1是指a_(2n) 加1
還是a_(2n+1)
a_4n+1+1這些也是不清楚
作者: tsyr    時間: 2015-7-3 10:29     標題: 回復 2# Ellipse 的帖子

抱歉，已修改
作者: tsusy    時間: 2015-7-3 11:55     標題: 回復 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 編輯 ]
作者: tsyr    時間: 2015-7-6 08:55     標題: 回復 4# tsusy 的帖子

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

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



歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/) 論壇程式使用 Discuz! 6.1.0