Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #10073

Re: on solving recurrences

Show all headers | View raw

David Brown <david.brown@hesbynett.no> 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.

[...]

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

on solving recurrences Daniel Bastos <dbastos@toledo.com> - 2017-03-21 16:13 -0300
  Re: on solving recurrences Ed Prochak <edprochak@gmail.com> - 2017-03-22 06:35 -0700
    Re: on solving recurrences Daniel Bastos <dbastos@toledo.com> - 2017-03-23 19:06 -0300
      Re: on solving recurrences Daniel Bastos <dbastos@toledo.com> - 2017-03-23 19:16 -0300
        Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2017-03-24 09:53 +0100
  Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2017-03-22 14:58 +0100
    Re: on solving recurrences Daniel Bastos <dbastos@toledo.com> - 2017-03-23 19:11 -0300
      Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2017-03-24 09:48 +0100
    Re: on solving recurrences Daniel Bastos <dbastos@toledo.com> - 2019-07-10 11:29 -0300
      Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2019-07-10 17:25 +0200
        Re: on solving recurrences Robert Girault <r@dev.null> - 2019-07-15 15:16 -0300
          Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2019-07-15 21:23 +0200
            Re: on solving recurrences Daniel Bastos <dbastos@toledo.com> - 2019-07-15 18:35 -0300
              Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2019-07-16 00:00 +0200
                Re: on solving recurrences Daniel Bastos <dbastos@toledo.com> - 2019-07-15 19:32 -0300
                Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2019-07-16 09:32 +0200
                Re: on solving recurrences Daniel Bastos <dbastos@toledo.com> - 2019-07-16 11:40 -0300
                Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2019-07-16 17:36 +0200
                Re: on solving recurrences Horizon68 like Menz <cdalten@gmail.com> - 2019-07-17 05:15 -0700

csiph-web