home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 12845 < prev    next >
Encoding:
Text File  |  1992-10-07  |  1.4 KB  |  39 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watdragon.uwaterloo.ca!daisy.uwaterloo.ca!deghare
  3. From: deghare@daisy.uwaterloo.ca (Dave Hare)
  4. Subject: Re: Looking for a slick proof
  5. Message-ID: <Bvr85r.26E@watdragon.uwaterloo.ca>
  6. Sender: news@watdragon.uwaterloo.ca (USENET News System)
  7. Organization: University of Waterloo
  8. References: <1aterkINNj4f@matt.ksu.ksu.edu> <hunt.718423655@shy.umd.edu>
  9. Date: Wed, 7 Oct 1992 13:58:38 GMT
  10. Lines: 27
  11.  
  12. In article <hunt.718423655@shy.umd.edu> hunt@shy.umd.edu (Brian Hunt) writes:
  13. >bubai@matt.ksu.ksu.edu (P.Chatterjee) writes:
  14. >>How does one prove that 2^n divides n*(n+1)*(n+2)*......*(2n) without     
  15. >>having to resort to the 'odd' and 'even' induction? Any ideas?
  16. >
  17. >In fact 2^n divides (n+1)(n+2)...(2n), and it's the largest power of 2
  18. >to do so.  Let [x] be the greatest integer less than or equal to x.
  19. >Then the largest power of 2 which divides n! is
  20. >
  21. >[n/2] + [n/4] + [n/8] + ...
  22. >
  23. >(above is {# of multiples of 2 <= n} + {# of multiples of 4 <= n} + ...)
  24. >while the largest power of 2 which divides (2n)! is
  25. >
  26. >[n] + [n/2] + [n/4] + ...
  27. >
  28. >so the largest power of 2 which divides (2n)!/n! is [n] = n.
  29. >
  30. >Brian Hunt
  31. >hunt@ipst.umd.edu
  32.  
  33. I think this is easier:  (2n)! = 1*3*5*...*(2n-1)*2*4*6*...*(2n)
  34.                                = 1*3*5*...*(2n-1)*2^n*n!
  35.                    so (2n)!/n! = (n+1)*(n+2)*...*(2n) 
  36.                                = 2^n * 1*3*5*...*(2n-1)
  37.  
  38. Dave Hare
  39.