Path: csiph.com!aioe.org!.POSTED.RoyQLB9OfVD/sGfJH+3Mhw.user.gioia.aioe.org!not-for-mail From: Daniel Bastos Newsgroups: comp.programming Subject: Re: on solving recurrences Date: Tue, 16 Jul 2019 11:40:03 -0300 Organization: Aioe.org NNTP Server Lines: 87 Message-ID: <86muhe82m4.fsf@toledo.com> References: <86y3vyh292.fsf@toledo.com> <86v9wagdz1.fsf@dev.null> <86pnmbf9jq.fsf@dev.null> <865zo3aslz.fsf@dev.null> <86v9w39bff.fsf@toledo.com> NNTP-Posting-Host: RoyQLB9OfVD/sGfJH+3Mhw.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:68JkUtltrCqLaWbVYdEkxlOG0SU= Xref: csiph.com comp.programming:10073 David Brown writes: > On 16/07/2019 00:32, Daniel Bastos wrote: > >> 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! > > I really don't want to sound patronising here, but do you understand > what "proof by induction" means, and how it works? Your answer here seems unconnected to the passage you quote. Induction is not the problem here. If a step in a mathematical argument is incorrect, you have to show it leads to trouble. I was hoping you'd show that. I think you see nothing as incorrect, but something lacking rigor. I'm trying to guess what it is that lacks rigor here. Perhaps you consider invalid the n applications of the definition of the recurrence. For example, the recurrence is defined as r(0) = 1 r(n) = 2 r(n - 1) + n James Hein applies the definition n times when he writes r(n) = 2 r(n - 1) + n -- 1st application 2 r(n - 1) = 2 (2 r(n - 2) + (n - 1)) -- 2nd application ... 2^(n - 1) r(1) = 2^n r(0) + 2^(n - 1) * 1 -- nth application From these n equations, he derives another where r(n) is isolated at the left hand side. Perhaps you think that /can be/ equivalent to a proof by induction, but, not being rigorously shown, cannot be considered equivalent. --8<---------------cut here---------------start------------->8--- Perhaps the situation is analogous to solving a first-order separable differential equation such as dy/dx = y. One considers the left hand side as a fraction of different variables and manipulates it to get 1/y dy = dx then some integral sign is miraculously attached to both sides int 1/y dy = int dx and each side is integrated with respect to y, x, respectively, yielding ln |y| + c(1) = x + c(2) ln |y| = x + c(3) y = c(4) e^x. The step where integral signs are attached is very strange to me and until someone explains to me how that makes sense, I consider it invalid, but the fact is that there's a theorem that states that you can go from dy/dx = y to int 1/y dy = int dx. So the steps written in that solution can be seen as an informal way to remember what the theorem says. --8<---------------cut here---------------end--------------->8--- So perhaps the writing of n equations to add them up afterwards is a mnemonic that lets us get the desired result, but it can only be considered a legal step if shown by induction --- despite it probably being impossible to produce an incorrect answer. But then again, I don't know if that is the problem you see. It's not clear. I can only conclude your problem is in the lack of rigor in the powerful ellipsis. You could illustrate such dangers by presenting the all horses are of the same color argument, but that would be a radical change of subject: the thread began with a request for help on solving the most basic types of recurrences, pointing out a good book on the topic that was too advanced for helping at that point. [...]