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

Groups > comp.programming > #10069

Re: on solving recurrences

Show key headers only | View raw

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.

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