数列通项公式之二

〇〇

一下子看不明白

mathe

如果用u(k,i)表示满足以下条件的n的个数（其中$i<=k$
056254628 发表于 2010-1-13 12:15

没有注意其中$i<=k$的条件,应该是对的

mathe

现在可以证明这个结论.
我们可以看到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)在$[2^{k-1},2^k]$中相邻的数构成的数对,有如下性质:
i)任意数对中两个数(a,b)互素.
ii)$[2^{k-1},2^k]$中的所有数对(a,b)正好为u(a,b)=k的所有数对

mathe

现在余下的就很容易可以证明了,
首先,对于任意(a,k),其中$gcd(a,k)=1,1<=a<k$,必然有$u(a,k)<=k$
其次$u(a+k,k)=u(a,k)+1$

056254628

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)

mathe

2^(k-1)
056254628 发表于 2010-1-13 16:54

这样是不行的,没有证明不会重复,而且所有的组合都会出现,而且也是不合适的,有些i是从2^(k-2)<n<2^(k-1)中复制过来,有些是从它们两个之和构成的.

056254628

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层
1  5  4  7  3  8  5  7  2  7  5  8  3  7  4  5  1                第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都必定成立。

mathe

还是错误的,不知道性质1要说明什么

056254628

mathe大师，真不知性质1说明什么吗？ 在a和b是互质的条件下。
性质1说明在2^(k-1)<n<2^k之间， 有序数对(a,b),不可能有重复。因为a/b 的值呈增大趋势。

056254628

看一下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