home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 12864 < prev    next >
Encoding:
Internet Message Format  |  1992-10-07  |  1.3 KB
  1. Path: sparky!uunet!paladin.american.edu!darwin.sura.net!wupost!waikato.ac.nz!comp.vuw.ac.nz!cc-server4.massey.ac.nz!TMoore@massey.ac.nz
  2. Newsgroups: sci.math
  3. Subject: Re: Looking for a slick proof
  4. Message-ID: <1992Oct7.195233.16373@massey.ac.nz>
  5. From: news@massey.ac.nz (USENET News System)
  6. Date: Wed, 7 Oct 92 19:52:33 GMT
  7. References: <1aterkINNj4f@matt.ksu.ksu.edu> <hunt.718423655@shy.umd.edu> <Bvr85r.26E@watdragon.uwaterloo.ca>
  8. Organization: Massey University
  9. Lines: 23
  10.  
  11. In article <Bvr85r.26E@watdragon.uwaterloo.ca>, deghare@daisy.uwaterloo.ca (Dave Hare) writes:
  12. > 
  13. > In article <hunt.718423655@shy.umd.edu> hunt@shy.umd.edu (Brian Hunt) writes:
  14. > >bubai@matt.ksu.ksu.edu (P.Chatterjee) writes:
  15. > >>How does one prove that 2^n divides n*(n+1)*(n+2)*......*(2n) without     
  16. > >>having to resort to the 'odd' and 'even' induction? Any ideas?
  17. > >
  18. > >In fact 2^n divides (n+1)(n+2)...(2n), and it's the largest power of 2
  19. > >to do so.
  20.  
  21. This can be done by an ordinary induction. I'll prove more, that for
  22. prime p, p^n | f(n) = (n+1)(n+2)...(pn) and is the largest power of p
  23. to do so.
  24.  
  25. Clearly true for n=0.
  26. Now f(n+1) = f(n)(pn+1)(pn+2)...(pn+p)/(n+1) = pf(n)(pn+1)(pn+2)...(pn+p-1)
  27. and p divides none of the factors after f(n).
  28.  
  29. Exercise, what happens if p is not prime?
  30. Clearly, divisibility by p^n still holds, but
  31. what is the highest power of p which works?
  32.  
  33. Terry Moore
  34.