home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 17885 < prev    next >
Encoding:
Internet Message Format  |  1993-01-09  |  3.3 KB
  1. Path: sparky!uunet!pipex!warwick!uknet!qmw-dcs!arodgers
  2. From: arodgers@dcs.qmw.ac.uk (Angus H Rodgers)
  3. Newsgroups: sci.math
  4. Subject: Re: Closed forms for sums
  5. Message-ID: <1993Jan9.163732.8881@dcs.qmw.ac.uk>
  6. Date: 9 Jan 93 16:37:32 GMT
  7. References: <964.165.uupcb@hal9k.ann-arbor.mi.us>
  8. Sender: usenet@dcs.qmw.ac.uk (Usenet News System)
  9. Organization: Computer Science Dept, QMW, University of London
  10. Lines: 66
  11. Nntp-Posting-Host: theoryc.dcs.qmw.ac.uk
  12.  
  13. In <964.165.uupcb@hal9k.ann-arbor.mi.us>
  14. james.jones@hal9k.ann-arbor.mi.us (James Jones)  writes:
  15.  
  16. >Some things I remember:
  17.  
  18. >1.      All closed forms had  n  and  (n + 1)  as a factors.
  19.  
  20. >                            2              2
  21. >2.      All odd j > 1 had  n   and  (n + 1)   as a factors.
  22.  
  23.  
  24. >3.      Add even j > 2 had interesting coefficients on the terms in
  25. >        the last factor.
  26. >        (at least the last factor the way Derive factored it)
  27.  
  28. > [...]  my question is, how does one go about determining a closed
  29. > form for a sum? [...]
  30.  
  31. >Any explanation or references (explanation preferred) would be
  32. >appreciated.
  33.  
  34. Perhaps this should be an FAQ?
  35.  
  36. I got interested in the problem when I was at school in the 60s,
  37. and wrote it up then. Unfortunately I later destroyed my notes,
  38. but I still kept copies of the general formulae for these
  39. factorisations, in terms of the Bernoulli numbers; and when the
  40. topic came up in sci.math recently, I reconstructed some of the
  41. proofs, and additionally reassured myself that the simplicity of
  42. the coefficients was at least partly a consequence of von Staudt's
  43. theorem on the Bernoulli numbers (see Hardy & Wright).
  44.  
  45. I've got a LaTeX file with most of this stuff in it, but it's a
  46. bit long to post to sci.math, and it still needs some work.
  47.  
  48. I've also got some pari-gp code which you can use to calculate
  49. enormous coefficients (expressed as products of powers of primes)
  50. to your heart's content.
  51.  
  52. Briefly, you need to prove, first, that the power sum, satisfying
  53. a 1st-order difference equation, is a polynomial in n, and second,
  54. that it is also an even or odd polynomial in n + (1/2). You can then
  55. get a pair of recurrence relations for the coefficients in the
  56. factorisation -- which is more neatly expressed in terms of n(n + 1)
  57. than in terms of n itself. (Something that Derive didn't notice.)
  58.  
  59. (I can't face trying to work through the messy details of this part
  60. of the work again; and in any case there may be some more elegant
  61. approach than the pedestrian route which I took, using only school
  62. algebra.)
  63.  
  64. The recurrence relations can be solved, in two ways. One way seems
  65. useful for estimating the numerical size of the coefficients (which 
  66. can be proved to alternate in sign, a fact which you didn't mention),
  67. but I haven't followed this up, and it may not be easy. The other
  68. solution is in terms of the Bernoulli numbers, and is useful for
  69. getting at the more number-theoretic properties of the coefficients.
  70.  
  71. I'll post the document to you when I've edited it a bit. I suppose
  72. it's not absolutely too long to post to sci.math, if there's enough
  73. interest.
  74. --
  75. Gus Rodgers,  Dept. of Computer Science, | Cinema's worst romantic dialogue? --
  76. Queen Mary & Westfield College, Mile End | "Mechagodzilla's brain is  installed
  77. Road, London, England.   +44 71 975 5241 | in my stomach!" "I don't care if you
  78. E-mail (JANET):   arodgers@dcs.qmw.ac.uk | are a cyborg  --  I still love you!"
  79.