Conference rusure::math

Hallyburton, you idiot, you want the sum of the first I(n) to be >= n,
not simply equal to n.  Other than that, it looks like an interesting
problem.

						John

In fact, once you get beyond 1, the sum is NEVER = n for any n. That's
not difficult to prove - I leave it as an Exercise For The Reader.

Lynn Yarbrough

I don't beleive the answer can be expressed in closed form.
I think this can be proven using the Calculus of Finite Differences
but I am not an expert on the subject so I can't make a definitive
statement.

	re .0, .1

>>	We all know the harmonic series
>>
>>		1   1   1   1   1   1
>>	        - + - + - + - + - + - + ...   
>>		1   2   3   4   5   6
>>
>>	diverges.  Hence for every n there is a (minimal)  I(n) such that:
>>
>>		 ----- I
>>		  \		 -1
>>		  /		i	>=   n
>>		 ----- i = 1
>>
>>	Is there a closed form for I(n)?  I(1) = 1, I(2) = 4, etc.
>>
>>	It's easy to find upper bounds on I(n), but I can't find an exact solution.

	I thought that for large enough n, the harmonic sum
	was approximately ln n plus some constant called
	Euler's number or Euler's constant, written as gamma,
	and between 0.5 and 0.6.  Does anyone remember the
	precise formula or have a reference to it handy?
	It would seem to make I(n) close to e^(n - gamma).

	Dan

    The asymptotic expanson goes like this (using Euler-Maclurin
    summation).
			    1	            B[2 k]
    H[n] = Ln(n) + Gamma + --- - Sum(1,m) ----------- + Remainder
		           2 n		  2 k n^(2 k)

    Basically, it comes from approximating the integral of 1/x by
    discrete sums (the trapezoidal rule) and an asymptotic error
    estimate involving the odd derivatives of 1/x.  The trapezoidal
    rule is the harmonic sum, so we turn this around to get the sum
    in terms of the integral...

    You can markedly improve the accuracy by summing the first few
    terms of H "by hand" and using the above style expansion to estimate
    the tail of the sum only.

    See Knuth (naturally!) for more info.

    - Jim

    Prove that for any real numbers a and b with a < b, there exists an
    integer n and c[i] in {-1,1}, i = 1,...,n such that
    
    a < c[1] + c[2]/2 + ... + c[n]/n < b

    >Prove that for any real numbers a and b with a < b, there exists an
    >integer n and c[i] in {-1,1}, i = 1,...,n such that
    >
    >a < c[1] + c[2]/2 + ... + c[n]/n < b

    this is really asking to show that ANY real number can be expressed
    as  c[1] + c[2]/2 + ... + c[n]/n .

    first we know this series is convergent, (since finite sum), so 
    its sum is a number.

    next we have to show that by changing the n and the set C[i], any
    real number of any accuracy can be reached as the sum of this series.
 
                c[1] + c[2]/2 + ... + c[n]/n .

    it is obvious that any number less than 1 can be reached by
    just picking n = 1 and c[1] to be that number. (example .5 = .5/1)
    where c[i]={.5} (i=1)

    next we need to show that ANY real number > |1| can also be expressed as
    this series sum.

    isn't there a theory that says any real number can be written as the
    some of rational numbers? that is the one we need !


    \nasser

    re .7
    
    I don't think I made it clear that each c[i] is drawn from the set
    {-1,1}, not the interval [-1,1] or similar i.e. each c[i] is either +1
    or -1.
    
    Example: If c[i] = +1 for all i then the infinite series diverges,
    similarly if c[i] = -1 for all i. If the c[i]s alternate +1, -1, +1,
    etc. then (from memory) the infinite series converges.

    opps, thanks for clarifying that, i read it differently.

    this below just shows that what you said about divergence is correct:

    >Example: If c[i] = +1 for all i then the infinite series diverges,

    show that this is diivergent in the limit:
    
       1 +1/2 + 1/3 + 1/4 + 1/5 + ........+ 1/n   

    lets see, since series is of +ve terms, i can use ratio test:

                                      1/n+1        n
    ratio test:   c[n+1]/c[n] =     --------- = --------- -->1 an n-->oo
                                      1/n        n+1

    so, ratio test failes, we are undecided. need another test, try integral 
    test, since all c[i]>0 :

          oo
         /
         |   1/x dx = ln(oo)-ln(1) = oo  , a divergent integral
         /
         1

    so, the series diverges. as said.  

    \nasser

    re .-1
    
    A more elementary proof uses a bracketing of the terms as follows
    
    (1/1) + (1/2) + (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + 1/8) + ...

    Each bracketted item is greater than or equal to 1/2 and thus an upper
    bound on the number of terms needed to reach a partial sum of N is
    2^(2N-1). [This bound can no doubt be improved upon!]

        So to get the sum to lie between a and b, assuming a < b, let
        the initial sum be zero (obviously), and if the current sum is
        <= a, then let the next c[n] be 1; if the current sum is >= b,
        then let the next c[n] be -1.  Since the harmonic series
        diverges, if a current sum is <= a this will eventually get it
        above a; if a current sum is >= b this will get it below b. 
        Eventually n becomes such that 1/n < (b-a), and after that
        when you next step from <= a to above a, or from >= b to below
        b, you must land in (a,b).
        
        Dan

    Suppose we rephrase the problem so that you MUST take the sum over
    the entire harmonic series using coefficients from {+1,-1}.  That is,
    an infinite series, not a finite one.
    
    Having landed in (a,b) you also need to show that you can stay there.
    
    It seems possible that if you are at x, a<x<b, the next step in the
    series forces you "outside".  And if you are to later land back in 
    (a,b) you will not likely land at the same "x" as before.  So it's not
    obvious to me that this is doable.
    
      John

        But by following the rules of selecting c[n] = +1 when
        the current sum is <= a, and selecting c[n] = -1 when
        the current sum is >= b, then you can always return to
        (a,b) no matter how many times you may have been there
        (and left) earlier.
        
        So return to (a,b) after 1/n becomes less than (b-a)/3,
        then start alternating + - + - etc. if in the lower third,
        otherwise alternate - + - + etc.  This will keep you in
        (a,b) forever after (and will converge to a point in (a,b)).
        
        Dan

    re .-1
    
    Can someone refresh my memory as to what the series
    
    1 - 1/2 + 1/3 - 1/4 + 1/5 - ...
    
    converges to?
    
    (Convergence is obvious by comparison with sigma 1/n�.)

    Maple says it converges to ln(2).  Just checked a reference for some
    identities for ln, and one of them is:

		       2      3
	ln(1+x) = x - x /2 + x /3 - ...  for -1 < x <= 1

    Let x=1, and you get the result MAPLE gave.

					Topher

    Sounds like maybe we could come up with a "Science & Math" category
    for Trivial Pursuit ...
    
      John

re .14 (me)
    
>    (Convergence is obvious by comparison with sigma 1/n�.)
    
    This is true but overkill for the series in question. Easier is to use
    the theorem that
    
    If {a[n]} is a sequence that converges to 0 and is monotonically decreasing
    
    Then the alternating series, {s[n]}, converges
        where s[n] = sigma(i=0,...,n) (-)^i a[i]
    
    EFTR or POA

Here's an approximate answer to John's original question that I scrawled
on a paper before bed a few nights ago:

Suppose we want

	100 = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 ...

John's question asks how many terms total are needed to exceed 100.

Well, consider 2 bounding sequences:

	< 100 =	1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/16..(7 more 1/16's)
 
	100 =	1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 ...

	> 100 =	1/1 + 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8..(7 more 1/8's)

The one that's > 100 is clearly TWICE as large exactly as the one that's
< 100.  (Each term of <100 series is HALF the corresponding term of <100 one).

Now, here's where I make a BAD assumption, but the best I can think of
for now.  That BAD assumption is that the middle sequence is approximately
halfway between the 2 bounds, rather than embarrassingly close to one
bound or the other.

But, the middle one is DEFINITELY between the 2 bounds.

I want to choose the <100 value and the >100 value to be equal distance
from 100, with the >100 twice the value of the <100 one.  Call the <100 one
S (for "small").  We have

	L = 2S		(larger is twice the smaller)
	(L+S)/2 = 100	(the 2 bounds AVERAGE to 100, i.e. 100 is in MIDDLE)

The closest integer solutions to these equations (why integer?) is

	3S/2 = 100 or 3S = 200 or S = 66, L = 132.

We therefore want


	66 =	1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/16..(7 more 1/16's)
 
	100 =	1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 ...

	132 =	1/1 + 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8..(7 more 1/8's)


What's left is to calculate how many terms in the bottom sequence.  This
will EXACTLY equal the number of terms in the upper sequence, so will
approximately equal the number of terms in the middle sequence.

In the bottom sequence, we have

	132 = 1 + 1 + 1... total of 132 1's

where the second 1 is comprised of two 1/2's and four 1/4's and 2^3
1/8's and 2^4 1/16's and hence 2^132 1/132's.

So, the total number of terms is

	n(100) = 2^1 + 2^2 + 2^3 ... + 2^132.

where n(100) is EXACTLY how many terms of the bottom sequence to add to
132, and EXACTLY how many terms of the top sequence to add to 66, and
we're assuming (how BAD an assumption?) is APPROXIMATELY how many terms
of the middle sequence to add to 100.

Writing this in binary, it looks like

	n = 10 + 100 + 1000 ... which adds to

	11111....1111110

which if we add 2 to, becomes

	10000....0000

which is 2 to the something, so n(100) is 2^k - 2 and we just have to be
a bit careful in calculating k.  Each term contributed a 1, so we have
132 1's followed by a 0.

Suppose we only had two 1's instead of 132 of them, then we'd have

	110

which is 6 or 2^3 - 2.  So by induiction (or intuction, or intuuction), we
can say that k is one more than the number of 1's.  So, we have

	n(100) = 2^133 - 2.

Generalizing this for any desired total t, we get the approximate number
of terms (n) of the harmonic series necessary to read t as

	n(t) = 2^(4t/3) - 2


How good or bad is this approximation ?

/Eric

    re .18
    
    .10 contains the most elementary bound (and also a very poor one - as I
    remarked at the time).
    
    .5 contains a good bound. (You can get an approximation like it using the
    connection between a series and an integral.)
    
    Based on .5 it should be simple to express e^n in terms of 2^n and
    hence compare your bound directly with that in .5.

    Suppose we create an "almost harmonic" series by flipping the sign
    of every k-th entry. Thus for k=3 we have:
    
    H(3) = 1 + 1/2 - 1/3 + 1/4 + 1/5 - 1/6 + 1/7 + 1/8 - 1/9 + 1/10 + ���
    
    H(1) is just -H, the negative of the harmonic series, and diverges.
    H(2) is the alternating harmonic series, which converges to ln(2)
    
    Question: for what values of i does H(i) converge? Here's a few
    sample runs summed over 10M terms (in reverse order):
    
    	 i	 H(i)		status
    -----------------------------------------
    	 1	 -infinity  -H, diverges
    	 2	  .693147   converges to ln(2)
    	 3	 6.29763	?
    	 4	 9.04365	?
    	 5	10.6607		?
    	 6	11.7289		?
    	 7	12.4838		?
    	 8	13.0364		?
    	 9	13.4715		?
    	10	13.8123		?
    
    An interesting observation is that as i increases, H(i) appears to
    converge. But as i increases, we have fewer and fewer minus signs
    in the sum, so are actually approaching H, which diverges.
    
    My guess is H(n) diverges for n != 2
    
      John

Each negative term appears after a positive one that is larger in magnitude.  So
drop them; for k>2, what remains is at least

1/1 + 1/(k+1) + 1/(2k+1) + ... > 1/k + 1/2k + 1/3k + ... = 1/k times a divergent
series.

Pretty clever!  but of course it took me some writing to figure out
what you meant...  /Eric

   You can follow the experimental approach in .20 by summing
   the series in "chunks" from n to 2n, for n = 1, 2, 4, 8, 16, ...

   Then each chunk, for a "gap" of k between the minus signs,
   approaches (1 - 2/k)log(2), by estimating the sum as an integral,
   and there are an infinity of those chunks.

   - Jim

Does the chunky series hit any integers on its way to divergence ?

/Eric