NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/sci/math/17335

Internet Message Format | 1992-12-22 | 2.8 KB

Path: sparky!uunet!zaphod.mps.ohio-state.edu!rpi!batcomputer!cornell!uw-beaver!cs.ubc.ca!unixg.ubc.ca!unixg.ubc.ca!israel
From: [e-mail] (Robert B. Israel)
Newsgroups: sci.math
Subject: Re: Sums of reciprocals
Date: 22 Dec 92 21:32:35 GMT
Organization: The University of British Columbia
Lines: 53
Distribution: sci
Message-ID: <[e-mail]>
References: <[e-mail]>
NNTP-Posting-Host: unixg.ubc.ca

In <[e-mail]> [e-mail] (Allan Adler) writes:


>Let f(n)=1/n for every positive integer n. Let x be a positive
>real number. Let g(n,x) be defined as follows:

>(1) g(n,x) is a strictly increasing sequence of positive integers, possibly
>     a terminating sequence.
>(2) for all n, g(n,x) is the smallest integer consistent with (1)
>    such that the sum of the reciprocals of g(k,x) for k=1,...,n
>    does not exceed x.

>I have been told that if x is rational then this leads to a way of writing
>x as a finite sum of reciprocals of distinct positive integers. Let the number
>of terms in this sum be N=N(x). I have been told that N is also the number of
>terms in a minimal representation of x as a sum of reciprocals of positive
>integers allowing repetitions.

>Is this true and if so how or where is it proved?

>Allan Adler
>[e-mail]

It does lead to a finite representation.  To save typing, I'll write g(n,x)
as g(n) and 1/g(n) as h(n).  Let r(n) = x - sum_{i=1}^n h(n).  Thus
r(0) = x, and r(n+1) = r(n) - h(n+1).  Moreover,
        g(n+1) = max(g(n)+1,ceil(1/r(n)))
(where ceil(y) = least integer >=y).  I claim that for sufficiently large
n we have g(n+1) > g(n)+1.  For suppose g(n) > 2 and g(n+1) = g(n)+1.  Then
r(n-1) = r(n+1) + h(n) + h(n+1) >= 1/g(n) + 1/(g(n)+1) > 1/(g(n)-1).
The only reason why g(n)-1 was not chosen instead of g(n) is that
g(n)-1 = g(n-1).  Thus if g(n+1) = g(n), we must have g(k) = g(k-1) + 1
whenever k <= n and g(k) > 2.  Thus x >= sum_{k=2}^n 1/k.  By the
divergence of the harmonic series, this can't happen for large n.

Now suppose n is large enough that g(n+1) > g(n) + 1.  Let r(n) = p/q
with p and q positive integers.  For some integers k and r,
0 <= r < p, q = kp + r.  If r = 0, the representation ends with
g(n+1) = k.  Otherwise, 1/(k+1) < r(n) < 1/k so g(n+1) = k+1.  Then
r(n+1) = p/(kp+r) - 1/(k+1) = (p-r)/((kp+r)(k+1)).  But this has
a smaller numerator than does r(n).  Therefore after at most p
further terms, the representation must terminate.


It is not true, on the other hand, that N is minimal.  For example,
take x = 1/4 + 1/5, a sum of two reciprocals.  The representation
using g(n,x) is 1/3 + 1/9 + 1/180.

--
Robert Israel                            [e-mail]
Department of Mathematics             or [e-mail]
University of British Columbia
Vancouver, BC, Canada V6T 1Y4