Path: csiph.com!news.swapon.de!aioe.org!.POSTED!not-for-mail From: Daniel Bastos Newsgroups: comp.programming Subject: Re: on solving recurrences Date: Thu, 23 Mar 2017 19:06:25 -0300 Organization: Aioe.org NNTP Server Lines: 95 Message-ID: <86mvcbfy1q.fsf@toledo.com> References: <86y3vyh292.fsf@toledo.com> <9bb8bad8-bf15-4422-889d-1e482b1059b8@googlegroups.com> NNTP-Posting-Host: BuEqJTf8bEmpZhBIUMG+Zw.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain X-Complaints-To: abuse@aioe.org User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt) X-Notice: Filtered by postfilter v. 0.8.2 Cancel-Lock: sha1:NrapILaUuIuskwNqzS/++/r3lIc= Xref: csiph.com comp.programming:7622 Ed Prochak writes: > On Tuesday, March 21, 2017 at 3:13:37 PM UTC-4, Daniel Bastos wrote: >> Can you suggest a book that concerns precisely on solving recurrences >> given my background? You'll see my background as I try my best at this >> one. (I know Concrete Mathematics by Knuth et al, but as much I liked >> their presentation of the Josephus problem, I think that book is too >> advanced for me.) Thank you! >> >> (*) Problem >> >> Solve >> >> T(n) = 1 if n = 0 >> = 2 T(n - 1) + 1 if n > 0 >> >> Remark. The only way I know how to solve this is by guessing. Here's >> how I do it. >> >> Solution. First I look at say T(8). >> >> T(8) = 2 T(7) + 1 >> = 2 (2 T(6) + 1) + 1 >> = 2 (2 (2 T(5) + 1) + 1) + 1 >> = 2 (2 (2 (2 T(4) + 1) + 1) + 1) + 1 >> >> So I see a pattern emerging. I ``went down 4 levels'' and I found this: >> >> = 2 (2 (2^2 T(4) + (1*2 + 1)) + 1) + 1 >> = 2 (2^3 T(4) + (1*2*2 + 1*2) + 1) + 1 >> = 2^4 T(4) + 1*2*2*2 + 1*2*2 + 1*2 + 1 >> = 2^4 T(4) + 2^3 + 2^2 + 2^1 + 2^0 >> >> So I must now discover what is Sum(2^i for i=0..n-1). Programming >> verification (see below) makes clear that we don't actually need to find >> that because it gets easy to see --- numerically --- that we have a case >> for 2^n - 1. >> >> Somehow >> >> 2^n - 1 = 2^n + Sum(2^i for i=0..n-1). Something must be wrong here. Otherwise -1 = Sum(2^i for i=0..n-1). And I don't know where I went wrong, but there's something wrong here. >> Thank you. >> >> (*) Programming verification >> >> def xrange(beg, end): >> # Python's range(x,y) goes up to y - 1. We usually want to be >> # inclusive. >> return range(beg, end + 1) >> >> def T0(n): >> if n == 0: >> return 1 >> elif n == 1: >> return 3 >> else: >> return 2**n + sum([2**i for i in xrange(0, n - 1)]) >> >> def T0r(n): >> if n == 0: >> return 1 >> else: >> return 2 * T0r(n - 1) + 1 >> >> >>> [(t0(i), t0r(i)) for i in range(8)] >> [(1, 1), (3, 3), (7, 7), (15, 15), (31, 31), (63, 63), (127, 127), (255, 255)] > > I am not sure what your question is. My question was the first sentence. I showed my struggle to resolve problems like this in order to help someone suggest me a book. I lack strategies to resolve recurrences. My only strategy is to unfold the recursion and see a pattern. That's all I can do. I'm getting the feeling that it all boils down to solving a lot of sums, products and things like that. So it's the kind of work that involves studying discrete mathematics, calculus and whatnot. > You did a nice analysis. Thank you! > Both versions T0r() and T0() are recursive. Both? T0() is not recursive. It doesn't mention T0 in its body. > I note you unrolled the loop one step only in the T0r() method >> elif n == 1: >> return 3 That was an accident. In one of my attempts I used (n - 2), so I had to worry about not going negative. Thanks for pointing it out.