Path: csiph.com!aioe.org!.POSTED.5jsc9Gwf1W19zWSAcD/vGw.user.gioia.aioe.org!not-for-mail From: Daniel Bastos Newsgroups: comp.programming Subject: Re: on solving recurrences Date: Mon, 15 Jul 2019 19:32:04 -0300 Organization: Aioe.org NNTP Server Lines: 111 Message-ID: <86v9w39bff.fsf@toledo.com> References: <86y3vyh292.fsf@toledo.com> <86v9wagdz1.fsf@dev.null> <86pnmbf9jq.fsf@dev.null> <865zo3aslz.fsf@dev.null> NNTP-Posting-Host: 5jsc9Gwf1W19zWSAcD/vGw.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:vuHuPIkyRo/1UZREVTdwzc51JVM= Xref: csiph.com comp.programming:10071 David Brown writes: > On 15/07/2019 23:35, Daniel Bastos wrote: >> David Brown writes: >> >>> On 15/07/2019 20:16, Robert Girault wrote: >>>> David Brown writes: >>>>> >>>>> 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! >>> >>> I don't have the book, so I can't look at it. >> >> Here's a relevant passage. I'm not saying the technique proves a closed >> form formula for all recurrences of a certain form. I'm saying the >> technique can prove that a certain recurrence of a certain form does >> have a certain closed form formula. So let me show a concrete example >> (chapter 5, section 5.3, example 1, page 281, first edition). >> >> --8<---------------cut here---------------start------------->8--- >> Example 1. Suppose we have given the following recurrence: >> >> r(0) = 1 >> r(n) = 2 r(n - 1) + n. >> >> This recurrence fits [a certain form where this technique works], so we >> can solve it by cancellation. Starting with the general term, we obtain >> the following sequence of equations [...]: >> >> r(n) = 2 r(n - 1) + n >> >> 2 r(n - 1) = 2 (2 r(n - 2) + (n - 1)) >> = 2^2 r(n - 2) + 2 (n - 1) >> >> 2^2 r(n - 2) = 2^2 (2 r(n - 3) + (n - 2)) >> = 2^3 r(n - 3) + 2^2 (n - 2) >> >> ... >> >> 2^(n - 1) r(1) = 2^n r(0) + 2^(n - 1) * 1. >> >> Now add up all the equations, cancel like terms, and replace r(0) by its >> value, to get the following equation: >> >> r(n) = 2^n + n + 2(n - 1) + ... + 2^(n - 1) * 1. >> --8<---------------cut here---------------end--------------->8--- >> >> His example stops there with the remark that if we can now find a closed >> form formula for this ellipsis-expressions, we're done. This >> ellipsis-expression is >> >> (2^0) n + (2^1) (n - 1) + ... + (2^(n - 1)) * 1 >> >> which has closed form formula >> >> 2^(n + 1) - n - 2 >> >> So the recurrence in his example 1 has closed formula >> >> s(n) = 2^n + 2^(n + 1) - n - 2 >> >> We may now ask. Can we be sure /the recurrence r/ has this closed form >> formula s(n)? I say sure: we've derived it by a perfectly legal method, >> so the result must follow, that is, the recurrence >> >> r(0) = 1 >> r(n) = 2 r(n - 1) + n. >> >> must describe the same sequence as >> >> s(n) = 2^n + 2^(n + 1) - n - 2. >> >> I don't see any flaw in this argument. > > Expanding some rounds of the equation and spotting a pattern is /not/ > rigorous proof. What's the flaw in the argument? I'd be very interested seeing it. > It is not hard to turn this into a proper proof, but you do it by > induction - not by seeing it looks good for a few n, adding an > ellipsis, and saying "we're done". The first thread in this thread > was worse, since it started with the first couple of rounds and then > used "programming verification". The first message was asking for a method since the only thing I could do then was try to guess the result. I never claimed that was a proof, of course. Nor did I claim so when I presented for the first time in this thread the technique exposed by James Hein --- it was an illustration of the technique. In my previous message, however, I do claim I have a perfectly valid argument for that particular recurrence. > Again, let me say that "spotting a pattern" is useful. Checking by > code is useful. But it is not mathematical proof. I'm definitely not disputing that. The argument in the example presented in not spotting a pattern. It writes equations and adds them up and arrives at a conclusion. Perfectly valid as far as I can see. I'll be thankful if you can expose the flaw. Thanks!