home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 12972 < prev    next >
Encoding:
Internet Message Format  |  1992-10-09  |  1.6 KB
  1. Path: sparky!uunet!mcsun!sunic!dkuug!diku!torbenm
  2. From: torbenm@diku.dk (Torben AEgidius Mogensen)
  3. Newsgroups: sci.math
  4. Subject: Re: Looking for a slick proof
  5. Message-ID: <1992Oct9.155336.3455@odin.diku.dk>
  6. Date: 9 Oct 92 15:53:36 GMT
  7. References: <1aterkINNj4f@matt.ksu.ksu.edu> <1992Oct9.92304.1850@ms.uky.edu>
  8. Sender: torbenm@freke.diku.dk
  9. Organization: Department of Computer Science, U of Copenhagen
  10. Lines: 40
  11.  
  12. cyeomans@ms.uky.edu (Charles Yeomans) writes:
  13.  
  14. >In article <1aterkINNj4f@matt.ksu.ksu.edu> bubai@matt.ksu.ksu.edu (P.Chatterjee) writes:
  15. >>Hi,
  16. >>
  17. >>How does one prove that 2^n divides n*(n+1)*(n+2)*......*(2n) without     
  18. >>having to resort to the 'odd' and 'even' induction? Any ideas?
  19.  
  20. >It looks to me like half of those 2n numbers are even.
  21.  
  22. Yes, but that only proves that 2^(n/2) divides the product. However,
  23. you can use that 4 divides every fourth number etc. Thus we have
  24.  
  25. (n+1) div 2 numbers where 2 is a divisor
  26. (n+1) div 4 numbers where 4 is a divisor
  27. (n+1) div 8 numbers where 8 is a divisor
  28. etc.
  29.  
  30. All divisions round down. The numbers that divide by 2 also divide by
  31. 4 etc., so we get only one power of two for each number in each list.
  32. Now,
  33.  
  34. n <= (n+1) div 2 + (n+1) div 4 + (n+1) div 8 + ... + (n+1) div log2(n)
  35.   <= n+1-log2(n+1)
  36.  
  37. so 2^n divides the product above.
  38.  
  39. In order to see that the sum is at least n, consider how we round the
  40. fractions. In the worst case, we round every fraction down, so we lose
  41.  
  42. 1/2 + 1/4 + 1/8 + ... 1/log2(n+1) = 1-log2(n+1)
  43.  
  44. from the best case, where we always have exact divisions (when (n+1)
  45. is a power of 2), so at worst we get
  46.  
  47. n+1-log2(n+1) - (1-log2(n+1)) = n
  48.  
  49. Q.E.D.
  50.  
  51.     Torben Mogensen (torbenm@diku.dk)
  52.