Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Daniel Bastos Newsgroups: comp.programming Subject: Re: on solving recurrences Date: Thu, 23 Mar 2017 19:16:08 -0300 Organization: Aioe.org NNTP Server Lines: 54 Message-ID: <8660izfxlj.fsf@toledo.com> References: <86y3vyh292.fsf@toledo.com> <9bb8bad8-bf15-4422-889d-1e482b1059b8@googlegroups.com> <86mvcbfy1q.fsf@toledo.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:33XZfirm+jouB3gAYdp/BDskKwU= Xref: csiph.com comp.programming:7624 Daniel Bastos writes: > 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. After seeing David Brown's message: I must have got my counters wrong since I thought I verified the result numerically. It's not 2^n - 1. It's 2^(n+1) - 1. The equation is therefore 2^(n + 1) - 1 = 2^n + Sum(2^i for i=0..n-1). Thanks.