home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / sci / math / 10165 < prev    next >
Encoding:
Internet Message Format  |  1992-08-12  |  1.2 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!zaphod.mps.ohio-state.edu!menudo.uh.edu!rmverma
  2. From: rmverma@cs.uh.edu (Dr. R.M. Verma)
  3. Newsgroups: sci.math
  4. Subject: Re: Binomial like recurrence
  5. Message-ID: <1992Aug12.171516.24574@menudo.uh.edu>
  6. Date: 12 Aug 92 17:15:16 GMT
  7. References: <1992Aug12.100933.13400@aifh.ed.ac.uk>
  8. Sender: usenet@menudo.uh.edu (USENET News System)
  9. Organization: Computer Science dept.,  Univ. of Houston (Main Campus)
  10. Lines: 31
  11. Nntp-Posting-Host: goedel.cs.uh.edu
  12.  
  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. I would like to know your reason for studying them.
  42.  
  43. R.M. Verma
  44.