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

Groups > comp.programming > #10071

Re: on solving recurrences

Show all headers | View raw

David Brown <david.brown@hesbynett.no> writes:

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

What's the flaw in the argument?  I'd be very interested seeing it.

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

The first message was asking for a method since the only thing I could
do then was try to guess the result.  I never claimed that was a proof,
of course.  Nor did I claim so when I presented for the first time in
this thread the technique exposed by James Hein --- it was an
illustration of the technique.  In my previous message, however, I do
claim I have a perfectly valid argument for that particular recurrence.

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

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!

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