home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10267 < prev    next >
Encoding:
Internet Message Format  |  1992-08-14  |  1.5 KB
  1. Path: sparky!uunet!wupost!usc!rpi!masscomp!usenet.ccur.com!catfish!ocpt!tinton.ccur.com!cjh
  2. From: cjh@tinton.ccur.com (Christopher J. Henrich)
  3. Newsgroups: sci.math
  4. Subject: Re: Binomial like recurrence
  5. Message-ID: <1992Aug13.230245.13244@tinton.ccur.com>
  6. Date: 13 Aug 92 23:02:45 GMT
  7. References: <1992Aug12.100933.13400@aifh.ed.ac.uk> <1992Aug12.171516.24574@menudo.uh.edu>
  8. Sender: news@tinton.ccur.com (News)
  9. Organization: Concurrent Computer Corp., Tinton Falls, NJ
  10. Lines: 41
  11.  
  12. In article <1992Aug12.171516.24574@menudo.uh.edu> rmverma@cs.uh.edu (Dr. R.M. Verma) writes:
  13. >In article <1992Aug12.100933.13400@aifh.ed.ac.uk> tw@aisb.ed.ac.uk (Toby Walsh) writes:
  14. >>
  15. >>The binomial recurrence,
  16. >>
  17. >>    c(n,k) = c(n-1,k-1) + c(n-1,k)
  18. >>
  19. >>is well known. Has the related recurrence,
  20. >>
  21. >>    u(n,k) = 2.u(n-1,k-1) + u(n-1,k)
  22. >>
  23. >>been studied? Does it have a closed form?
  24. >>What is its asymptotic behaviour?
  25. >>
  26. >>And more generally, how about,
  27. >>
  28. >>    v(n,k) = a.v(n-1,k-1) + b.v(n-1,k)
  29. >>
  30. >>for integer a and b?
  31. >>
  32. >>toby
  33. >
  34. >Yes, they have been studied and there are answers to some of your
  35. >questions in the literature. 
  36. >
  37. >See the paper by Monier in Journal of ALgorithms 1980, and
  38. >Ch. 8 of The Analysis of Algorithms by Purdom and Brown (more references
  39. >can be found here).
  40.  
  41. Dr. Verma's answer sounds like a response to a harder problem than
  42. the one Mr. Walsh proposed.  As far as I can see,
  43.  
  44.      u(n,k) = 2^k . c(n,k).
  45.  
  46. More generally,
  47.  
  48.      v(n,k) = a^k . b^(n-k) . c(n,k).
  49.  
  50. Regards,
  51. Chris Henrich
  52.