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

Groups > comp.programming > #10074

Re: on solving recurrences

Show all headers | View raw

On 16/07/2019 16:40, Daniel Bastos wrote:
> 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.

Yes, that is correct.  I don't think there are mistakes in what you have
written, it is simply that it is missing the parts that make it a proof
rather than a "this seems to work" answer.  (Don't misunderstand me here
- sometimes "this looks right" is all you need.)

>  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.

It is the "..." part that is not rigorous.

> 
> --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---

In all these steps, you are progressing from one step to the next.
Clearly you need to know that the steps are valid.  It is not trivial to
prove that you can "miraculously attach an integral sign to both sides",
but that would require a separate and substantial proof, so it's
reasonable to take it as read here.

But you can't jump over the "..." lines quite as lightly as you do.

> 
> 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.

Yes, that is a fair way to put it.

> 
> 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.
> 

I am not sure how much help I can be with books - it's over 30 years
since I learned this stuff.

But please, look back at the "proof by induction" method I posted at the
start of this thread, a year and a half ago:


"""
At this point, it should be rather obvious that the solution involves
2^n.  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.

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.
"""

This is simpler, and IMHO clearer, than the method you were showing -
and it is a rigorous proof.


So while I can't recommend any particular book for you, it seems I can
recommend a book for you to avoid - the one you have been using.


It might also help if you gave a little background about what stage you
are at, and where you are aiming.  Are you a student learning
mathematics?  Is this a hobby?  (Some people consider the idea of maths
as a hobby to be very odd - I think it's fun.)  Are you trying to use
this in software of some kind - or trying to use software to see results
from the maths?

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