魔方吧·中文魔方俱乐部

标题: 调和级数一定不是整数 [打印本页]

作者: yang_bigarm 时间: 2009-3-30 22:37:22 标题: 调和级数一定不是整数

第一次听到这个问题是在我一个同学参加研究生免试保送的时候。他的导师是一个刚从美国回来的的
一个很年轻的教授，他导师说我不看你的考试成绩，因为既然是系里面推荐，成绩单自然不会差啦。
我就出一个问题，不需要你当场就回答，给你一天的时间，你自己回去思考或者到图书馆查书，反正
明天的这个时候我在同样的地方等你，告诉我你的答案。
很有点那种武侠小说上某个人去学武艺，师傅考验他的那种感觉啊！到了最后，虽然他没有给出答案但是
迫于学校的某些规定，那个老师还是要了他了。

---------------------------------probelm----------------------------------------
调和级数定义如下
            1 1 1 1          1
s(n) = 1 + -  + -  + - + - + .... + -
            2 3 4 5          n
如果 n>1 的时候，证明它一定不可能是一个整数。
----------------------------------end-------------------------------------------

我们知道调和级数的增长速度是和对数函数差不多的，那么就是说他会增长到无穷大，但是
增长的又十分缓慢，难道他真的不会等于任何一个整数吗？

作者: 鞍山老于 时间: 2009-3-30 22:43:15

一起等答案,边顶边学!

作者: Cielo 时间: 2009-3-30 23:02:46

楼主的题果然有难度啊！先想想！

作者: 乌木 时间: 2009-3-30 23:22:55

1楼说了在n趋于无穷大时s(n)趋于无穷大，也就是说s(n)不存在（意思指不是一个确定的数），也就谈不上它是整数不整数的了。问题是，n为n>1的有限的值时，此时的s(n)是该级数的部分和，题目应该是问这样的部分和为什么不是整数，对吗？
我这样认识对吗？对后一问题，我不会回答。

－－－－－－－－－－－－－－－－－－－

笨办法想想，对于1/2，它等待另一个1/2来“补整”；对于1/3，等待1/（3/2）来“补整”；对于1/4，等待着1/（4/3）；…………1/n等待着1/（n / (n-1)）。显然，都是等不来的，故部分和s(n)不会是整数。
可以这样论证吗？

[ 本帖最后由乌木于 2009-3-30 23:56 编辑 ]

作者: lulijie 时间: 2009-3-31 00:09:57

有个想法：
给每个分子通分，通分后的分母为n！
那么第i个分数的分子就是  n!/i，
所有分子相加  得到数S
那么所求的调和级数=S/n！
若能证明  S中含的2的因子比n!中的2的因子少，就能证明二者不能整除，也就是说所求的调和级数不可能是整数。

作者: lulijie 时间: 2009-3-31 00:15:59

S中的2的因子比n!中的2的因子少，那么 a（n）=S/n! 就可写成分子是奇数，分母是偶数。
a(2)=3/2，显然成立。
假设 a（n）能写成分子是奇数，分母是偶数。
若能通过数学归纳法证明 a（n+1）也能写成分子是奇数，分母是偶数。
那么命题就得证。

作者: lulijie 时间: 2009-3-31 00:54:31

假设a(n)=p/(q*2^k)    p、q都是奇数，
那么1. 如果  n+1是奇数 =r，
那么 a(n+1)==p/(q*2^k)+1/r  =( p*r+q*2^k)/( q*r * 2^k ) 照样是 p/(q*2^k)  的形式，也就是说
若a(n)的分母的2的因子个数比分子的2的因子个数多k个，那么，加上  奇数的倒数后还是一样。
   2. 如果  n+1是偶数表示成 r*2^m。
      那么 a(n+1)=p/(q*2^k)+1/（r*2^m)
   只要k不等于m，那么  a(n+1)最后可表示成 p/(q*2^L)       L等于k和m中大的数，p和q都是奇数。
---------------------------------------------------------------------
a(2)=3/2  ,表示成p/(q*2^k)  的形式，k=1                                  只有k=0，a(n)才有可能是整数。
a(3)  =a(2)+1/3 ，由于3是奇数，所有  a(3)的k不变，同a(2)。
n=4 时，  a(3) 的k=1，4的k=2，所以 a(4)的k等于2。
在k等于3的n=8出来之前，即n=5、6、7的k都比 a(4)的k小，所以 a(5)、a(6）、a(7)的k都是2，
a(8) =a(7)+1/8  属于k =2  加 k=3 ，所以  a(8) 的k 等于  3，
同样在n=16 的k=4 出来之前， n=9、10、11、12、13、14、15  的k都比3小，所以不影响a(n) 的k  ，都是3
然后 a(16) 的k=4
。。。。。。。。
这样一直进行下去，无论n多大，最后  a(n) 都可表示成 p/(q*2^k)  的形式，其中 p、q是奇数。
                  k值满足    2^k<=n<2^(k+1)
  所以k永远大于0，且随着n的增加，而增加或保存不变。
所以a(n)永远不可能是整数。

[ 本帖最后由 lulijie 于 2009-3-31 01:00 编辑 ]

作者: lulijie 时间: 2009-3-31 01:08:25

楼主的题目都很有难度，做楼主的题头发都要掉很多，脑细胞都要死好多。你的题都是哪里出来的？

作者: lulijie 时间: 2009-3-31 01:18:41

上述是我的思路：
我再总结一下，应该可以用数学归纳法证明楼主的论断。
证明：a(n)  都可表示成 p/(q*2^k)  的形式。其中 p、q是奇数，k值满足  2^k<=n<2^(k+1)。
1.    n=2时，a(2)=3/2  ，k=1，  显然成立。
2. 假设 a(n)  可表示成 p/(q*2^k)  的形式。其中 p、q是奇数，k值满足  2^k<=n<2^(k+1)。
那么  a(n+1) 也可表示成  p/(q*2^k)  的形式。其中 p、q是奇数，k值满足  2^k<=n+1<2^(k+1)。
----------------------------------------------------------------

[ 本帖最后由 lulijie 于 2009-3-31 01:19 编辑 ]

作者: R'cube 时间: 2009-3-31 08:15:38

记得好像以前学过，当n值很大的时候有这么个近似求和公式S(n)≈ln(n)+c
c是欧拉常数，好像是0.577什么的。。。
LZ貌似是数学系的，题目都很有难度啊~~~

作者: kexin_xiao 时间: 2009-3-31 14:13:28

做地上学习，数学知识很长时间不用了，退化的太厉害了。

作者: 金眼睛 时间: 2009-3-31 21:51:21

初始的想法一定是通分了，呵呵！让分母等于n！

通分后注意，分母可以整除1到n的任意整数，而分子如果做不到这一点，调和级数的部分和就不能是整数。

假设分子不能整除m，由于分子的每一项（除了第m项，其结果为n!/m ）都有m因子，都是m整数倍，所以只能是n!/m 不能整除m，m很可能是一个质数。

不过2*m一定能整数m，所以就变成了证明n要小于2*m，这样m应该是n当中的最大质数。

经过上面分析，原题等价于证明在n中最大的质数要大于n/2，换句话说也就是n及2*n之间必有一个质数（n大于2）。

关于这个定理的证明教科书上有，有兴趣的朋友可以去翻翻书。

作者: yang_bigarm 时间: 2009-3-31 22:53:54

原帖由 lulijie 于 2009-3-31 01:08 发表
楼主的题目都很有难度，做楼主的题头发都要掉很多，脑细胞都要死好多。你的题都是哪里出来的？

平时喜欢积累一些这样的问题。

作者: yang_bigarm 时间: 2009-3-31 23:06:40

原帖由乌木于 2009-3-30 23:22 发表
1楼说了在n趋于无穷大时s(n)趋于无穷大，也就是说s(n)不存在（意思指不是一个确定的数），也就谈不上它是整数不整数的了。问题是，n为n>1的有限的值时，此时的s(n)是该级数的部分和，题目应该是问这样的部分和为什么 ...

当然是问前n项的和啦，我在1/n后面没有写省略号啊。

作者: 乌木 时间: 2009-3-31 23:26:18 标题: 回复 14# 的帖子

那么，1楼的倒数第二行说“……那么就是说他会增长到无穷大……”，读者别像我一样误解为式子有省略号。这句话其实是脱开那式子说的；或者，不脱开那式子的话，是指那式子的n趋于无限大时，“那么就是说他会增长到无穷大”。这样一来，该和值就不存在一个确定值，就谈不上整数不整数了。

[ 本帖最后由乌木于 2009-4-1 09:22 编辑 ]

作者: lulijie 时间: 2009-4-1 16:28:35

楼主，原题是怎么证明的，我觉得我前面的用数学归纳法来证明也非常简单啊。
通分以后分子是奇数，分母是偶数，当然不可能是整数。

作者: yang_bigarm 时间: 2009-4-1 19:18:01

原帖由乌木于 2009-3-31 23:26 发表
那么，1楼的倒数第二行说“……那么就是说他会增长到无穷大……”，读者别像我一样误解为式子有省略号。这句话其实是脱开那式子说的；或者，不脱开那式子的话，是指那式子的n趋于无限大时，“那么就是说他会增长到无 ...

多谈一些相关的背景知识嘛，我为了不引起误会，两条线之间的才是问题，其他的可以算作是乱弹的。

作者: yang_bigarm 时间: 2009-4-1 19:20:18

原帖由 金眼睛 于 2009-3-31 21:51 发表
原题等价于证明在n中最大的质数要大于n/2，换句话说也就是n及2*n之间必有一个质数（n大于2）。

你提的这个问题太大了，“n及2*n之间必有一个质数（n大于2）”这个量级的问题可以做一篇博士论文了，
这个不是我说的，是伟大的Erdos的导师对他说的。

作者: yang_bigarm 时间: 2009-4-1 19:31:40

原帖由 lulijie 于 2009-4-1 16:28 发表
楼主，原题是怎么证明的，我觉得我前面的用数学归纳法来证明也非常简单啊。
通分以后分子是奇数，分母是偶数，当然不可能是整数。

觉得归纳法对分母从2^k跳变2^(k+1)的时候说得不是很清楚

作者: 金眼睛 时间: 2009-4-1 19:38:43 标题: 回复 18# 的帖子

这个是已经被证明过的定理了，拿来说明你提出的问题就可以了啊，呵呵！否则要推到数学的源头去了。

作者: lulijie 时间: 2009-4-1 20:43:39

我来完整的用数学归纳法来证明，其实我在前面的思路中已经提到了证明。
证明：若n值满足  2^k<=n<2^(k+1)，那么a(n)  都可表示成 p/(q*2^k)  的形式。其中 p、q是奇数。
   换句话说，a(n)可表示成 p/(q*2^k) ，其中 p、q是奇数，k=  [ ln(n)/ln2 ]    ，[ ]  表示取整函数。
1.    n=2时，a(2)=3/2  ，k=1，  显然成立。
2. 假设n值满足  2^k<=n<2^(k+1)时，  a(n)  可表示成 p/(q*2^k)  的形式。其中 p、q是奇数。
那么， 2^k<n+1<=2^(k+1) ，把它分为两个情况
第一种情况：2^k<n+1<2^(k+1)
第二种情况：n+1=2^(k+1)。
对于第一种情况：不等式都除以2^k，得到  1<(n+1)/2^k<2。
   所以(n+1)/2^k 不是整数，即n+1 中含2的因子个数小于k。所以n+1可表示成 r*2^m，其中r是奇数，m<k。
   这样，a(n+1)=a(n)+1/(n+1)=p/(q*2^k)+1/( r*2^m)= ( p*r+q*2^(k-m) ) /  (q*r*2^k) 。很显然分子为奇数，分母为奇数和2^k的  乘积。因为 2^k<n+1<2^(k+1) ，当然满足2^k<=n+1<2^(k+1) ，即a(n+1)也可表示成  p/(q*2^k)  的形式。
对于第二种情况：
   a(n+1)=a(n)+1/(n+1)=p/(q*2^k)+1/(2^(k+1))=(2*p+q) / (q*2^(k+1)) ，分子为奇数，分母为奇数和2^(k+1)的乘积。
   因为  n+1=2^(k+1)，我们设k‘=k+1，  所以  2^k'<=n+1<2^(k’+1)条件满足，而a(n+1)显然可表示成 p’/(q‘*2^k‘)  的形式。其中 p’、q‘是奇数。
------------------------------------------------------
综上所述，假设 n值满足  2^k<=n<2^(k+1)时，  a(n)  可表示成 p/(q*2^k)  的形式。其中 p、q是奇数。
  那么可推出a(n+1)也成立。
所以命题得证。

[ 本帖最后由 lulijie 于 2009-4-1 21:26 编辑 ]

作者: lulijie 时间: 2009-4-1 21:37:55

从上述数学归纳法证明的过程中很明显的看出：
a(n)的k值，从n=2^i开始，随着n的增加，k值保持不变（等于i），直到n增加到等于2^(i+1)为止，k值跳到i+1，
接着又是重复上面的循环。
所以从n=2^1开始，n逐渐增大，a(n)的k值从等于1开始，保持不变或加1，
所以无论n增到多大，a(n)通分后的分子是奇数，分母是偶数，永远不可能是整数。

作者: yang_bigarm 时间: 2009-4-1 22:11:57

原帖由 lulijie 于 2009-4-1 20:43 发表
我来完整的用数学归纳法来证明，其实我在前面的思路中已经提到了证明。
证明：若n值满足 2^k

OK，这个证明就很完整了

作者: Cielo 时间: 2009-4-1 23:04:28

我的想法其实和金眼睛差不多，也是考虑 1~n 中最大的那个素数 p，只要 p 大于 n/2 或者 n/3 或者类似的就行。但发现这其实也不容易证明。

没想到反而是考虑最小的素数 2，lulijie 厉害啊！

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)