一下子看不明白
如果用u(k,i)表示满足以下条件的n的个数（其中$i<=k$
056254628 发表于 2010-1-13 12:15 http://bbs.emath.ac.cn/images/common/back.gif
没有注意其中$i<=k$的条件,应该是对的
现在可以证明这个结论.
我们可以看到g(n)函数在$1<=n<=2$时的值为1,1
对于一对互素的不小于1的正整数a,b,我们定义函数u(a,b)如下
$u(1,1)=1$
$u(a,b)={(u(a-b, b)+1,"when "a>b),(u(a, b-a)+1,"when "b>a):}$
也就是u(a,b)实际上是对a,b使用辗转相除法达到(1,0)需要的步数
而对于g(n)在$$中相邻的数构成的数对,有如下性质:
i)任意数对中两个数(a,b)互素.
ii)$$中的所有数对(a,b)正好为u(a,b)=k的所有数对
现在余下的就很容易可以证明了,
首先,对于任意(a,k),其中$gcd(a,k)=1,1<=a<k$,必然有$u(a,k)<=k$
其次$u(a+k,k)=u(a,k)+1$
本帖最后由 056254628 于 2010-1-13 16:57 编辑
2^(k-1)<n<2^k
那么g(n)都可以用a+b来表示，其中a和b是互质的正整数对。
那么满足 a+b=i 的a、b对的总对数(即u(k,i))就是满足
a和i互质的总可能数，其中a<i
也 就是 比i小的与i互质的总数（就是欧拉函数的定义）
所以 u(k,i)=φ(i) (i<=k)
2^(k-1)
056254628 发表于 2010-1-13 16:54 http://bbs.emath.ac.cn/images/common/back.gif
这样是不行的,没有证明不会重复,而且所有的组合都会出现,而且也是不合适的,有些i是从2^(k-2)<n<2^(k-1)中复制过来,有些是从它们两个之和构成的.
本帖最后由 056254628 于 2010-1-13 18:29 编辑
a、b对，所有的组合都会出现，确实需要严格证明。
实际上i<=k时，是成立的。而i>k,则是必有一些组合不出现，所以u(k,i)<φ(i) 当i>k时。
而所有的组合都不会重复,是很好证明的。
-------------------------------------------------------------------
已知g(n)的第2^(k-1)到2^k项的值。
因为g(2^k)=g(2^(k-1))
g(2^k+2)=g(2^(k-1)+1)
......
g(2^k+2^k)=g(2^k)
--------------------
g(2^k+1)=g(2^(k-1))+g(2^(k-1)+1)=g(2^k)+g(2^k+2)
g(2^k+3)=g(2^(k-1)+1)+g(2^(k-1)+2)=g(2^k+2)+g(2^k+4)
......
那么g(n)的第2^k到2^(k＋1)项的值可以这样得到。
先把g(n)的第2^(k-1)到2^k项的值全部抄下，再把每个相邻的两项值相加填入它们之间即可得到g(n)的第2^k到2^(k＋1)项。
具体如下：
写成如下就一目了然： 第k层
1 1 第1层
1 2 1 第2层
1 3 2 3 1 第3层
1 4 3 5 2 5 3 4 1 第4层
15473857275837451 第5层
所以数列g(n)的第2^(k-1)到2^k项之间的每一项，都可写成a*g(2)+b*g(1)=a+b的形式。其中a、b为正整数。
g(1)可以看成(0,1)对，g(2)可以看成(1,0)对.g(n)看成(a,b)对。
假设a/b都随着n的增大而增大, 2^(k-1)<n<2^k （性质1）
那么可以推出 a/b都随着n的增大而增大, 2^k<n<2^(k+1)
可以用归纳法证明：
k=1： (0,1)，(1,0) 显然成立。
k=p时假设成立， 设两个相邻的项为 (a1,b1) , (a2,b2) 那么 a1/b1<a2/b2
按照上面构造法：
抄下的项全部满足性质1.而中间添加的项为(a1+a2,b1+b2),显然满足$a_1/b_1<(a_1+a_2)/(b_1+b_2)<a_2/b_2$
因此k=p+1时，性质1也成立。
----------------------------------------------------
所以数列第2^k和2^(k+1)项之间不可能有相同的(a,b)对。
因此u(k,i)<=φ(i)对于任意的i都必定成立。
还是错误的,不知道性质1要说明什么
mathe大师，真不知性质1说明什么吗？ 在a和b是互质的条件下。
性质1说明在2^(k-1)<n<2^k之间， 有序数对(a,b),不可能有重复。因为a/b 的值呈增大趋势。
看一下http://bbs.emath.ac.cn/thread-2063-1-1.html第三楼贴就明白了
-----------------------------------------------------------
比如取k=4,
那么g(8)=1,g(16)=1
g(9)g(10)g(11) g(12)g(13)g(14)g(15) 刚好排成如下
4 3 5 2 5 3 4
1+3 1+2 2+3 1+1 3+2 2+1 3+1
1/3< 1/2 <2/3 < 1/1< 3/2 < 2/1< 3/1