Path: csiph.com!aioe.org!.POSTED.Ro+/3SGCnLl6Rfl/sX1m+Q.user.gioia.aioe.org!not-for-mail From: Robert Girault Newsgroups: comp.programming Subject: Re: on solving recurrences Date: Mon, 15 Jul 2019 15:16:09 -0300 Organization: Aioe.org NNTP Server Lines: 101 Message-ID: <86pnmbf9jq.fsf@dev.null> References: <86y3vyh292.fsf@toledo.com> <86v9wagdz1.fsf@dev.null> NNTP-Posting-Host: Ro+/3SGCnLl6Rfl/sX1m+Q.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.9.2 Cancel-Lock: sha1:Eq9S/5K+LTo2VQPPY2GoAT8X+4Y= Xref: csiph.com comp.programming:10066 David Brown writes: > On 10/07/2019 16:29, Daniel Bastos wrote: >>> 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! >> >> There's section 5.3, ``Solving Recurrences'', in ``Discrete >> Mathematics'' by James L. Heine, Jones and Bartlett Publishers, 1996, >> page 279. It shows a straightforward technique for solving >> recurrences such as the one discussed in this thread. If you have no >> technique at all, solving these simpler types of recursion will >> definitely mean something to you. >> >>>> (*) Problem >>>> >>>> Solve >>>> >>>> T(n) = 1 if n = 0 >>>> = 2 T(n - 1) + 1 if n > 0 >> >> Rewriting it to: >> >> a(0) = 1 >> a(n) = 2 a(n - 1) + 1 >> >> --8<---------------cut here---------------start------------->8--- >> Notation. Note that ``a'' is a function whose argument is the index >> of the sequence. So a(n) is the nth element of the sequence. >> --8<---------------cut here---------------end--------------->8--- >> >> An easy way to expose the construction of the technique is to consider >> a particular case of the recurrence and generalize. So consider a(5): >> >> a(5) = 2 a(4) + 1 >> >> Now write an equation for 2 a(4): >> >> 2 a(4) = 2(2a(3) + 1) >> = 2^2 a(3) + 2 >> >> Now write an equation for 2^2 a(3): >> >> 2^2 a(3) = 2^2 (2a(2) + 1) >> = 2^3 a(2) + 2^2 >> >> Now write an equation for 2^3 a(2): >> >> 2^3 a(2) = 2^3 (2a(1) + 1) >> = 2^4 a(1) + 2^3 >> >> No write an equantion for 2^4 a(1): >> >> 2^4 a(1) = 2^4 (2a(0) + 1) >> = 2^5 a(0) + 2^4 >> >> Since a(0) is the base case of the recurrence, we're done. Now add >> all the left hand side of these equations and add all the right hand >> sides. We get >> >> a(5) + 2 a(4) + 2^2 a(3) = 2^3 a(2) + 2^4 a(1) = 2 a(4) + 1 + >> 2^2 a(3) + 2 + 2^3 a(2) + 2^2 + 2^4 a(1) + 2^3 + 2^5 a(0) + 2^4 >> >> Notice now that all terms of the left hand side cancel out, except >> a(5). So we get >> >> a(5) = 1 + 2 + 2^2 + 2^3 + 2^4 >> = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 >> = Sum 2^i from i = 0 to i= 5 - 1 >> >> This sum on the right hand side is (2^{5 + 1} - 1) / (2 - 1). So >> >> a(5) = 2^6 - 1 = 63. >> >> The computation of this particular case makes it clear that in >> general >> >> a(n) = 2^(n + 1) - 1 >> >> is the desired answer. > > > No, it most certainly does not. > > What you have done here is found a likely candidate for an answer. Now > you can use that and prove it works, by induction. Until then, you only > have a guess that looks good in some tests, but you have no confirmed > and proven answer. I described an illustration of a technique. ``An easy way to expose the construction of the technique [...]'' However, you bring an interesting point. If you use the method above with perfect generality and are able to get a closed form formula for a(n), then you have a proof --- no need to show it by induction. See his section 5.3, page 279, first edition. If you disagree, I'll appreciate getting a clear exposition of how this can fail. Thanks! [...]