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:11:20 -0300 Organization: Aioe.org NNTP Server Lines: 73 Message-ID: <86d1d7fxtj.fsf@toledo.com> References: <86y3vyh292.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) Cancel-Lock: sha1:vai/so/w2ZW0RSDkJB1Vx+Rtc94= X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming:7623 David Brown writes: > On 21/03/17 20:13, 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 >> > > That's good so far. > > At this point, it should be rather obvious that the solution involves > 2^n. Yes. > Let's look at some actual values: > > n t(n) 2^n > ------------------- > 0 1 1 > 1 3 2 > 2 7 4 > 3 15 8 > 4 31 16 > > > It is rather obvious now that t(n) = 2^(n + 1) - 1. Okay. :-) > Obvious is not a proof, of course, but it's a lot easier to prove a > result if you know what you want to prove! > > Prove the assertion by induction. It is easy to see that the result > works for 0. > > Assume that it works for i up to n-1, where n > 0. Then > > t(n) = 2 * t(n - 1) + 1 > = 2 * (2^(n - 1 + 1) - 1) + 1 // By induction assumption > = 2 * 2 ^ n - 2 + 1 > = 2 ^ (n + 1) - 1 > > QED. I like constructions. Guessing and proving requires insight. I don't have a whole lot of that. Thanks for your attention.