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

Groups > comp.programming > #10070

Re: on solving recurrences

Show all headers | View raw

On 15/07/2019 23:35, Daniel Bastos wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> 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.
> 
> 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.  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".

Again, let me say that "spotting a pattern" is useful.  Checking by code 
is useful.  But it is not mathematical proof.

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