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

Groups > comp.programming > #10067

Re: on solving recurrences

Show all headers | View raw

On 15/07/2019 20:16, Robert Girault wrote:
> David Brown <david.brown@hesbynett.no> 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.

All I can say is that a technique of "spot a pattern from some samples 
and figure out a formula matching it" is a very useful step for solving 
many kinds of problems, but it is not in any way a mathematical proof.

If you have first proved, for example, that for all problems of the form:

	a(0) = c_0
	a(n) = c_1 * a(n - 1) + c_2

there is a solution of the form:

	a(n) = d_0 ^ (n + d_1) + d_2

/then/ you can use the pattern to figure out what d_0, d_1 and d_2 must 
be, and have a proven closed formula.


But if you don't have such a general proof on hand, then "generalising 
from a pattern" is not a proof.

Imagine you hung out your washing on Monday, and it rained, then you 
hung it out on Tuesday, and it rained, but on Wednesday when you didn't 
hang out washing, it was sunny.  There is a clear pattern - is that 
proof that hanging out your washing causes rain?

The same applies here.

Mathematics is full of patterns that look good, and survive lots of 
testing, but are wrong in general.  Look at the numbers generated by 
"n^2 - n + 41" as n goes from 0 upwards.  They are all primes!  Until 
you get to n = 41, that is.

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