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

Groups > comp.programming > #10066

Re: on solving recurrences

Show key headers only | View raw

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

> On 10/07/2019 16:29, Daniel Bastos wrote:
>>> On 21/03/17 20:13, Daniel Bastos wrote:
>>>> Can you suggest a book that concerns precisely on solving recurrences
>>>> given my background?  You'll see my background as I try my best at this
>>>> one.  (I know Concrete Mathematics by Knuth et al, but as much I liked
>>>> their presentation of the Josephus problem, I think that book is too
>>>> advanced for me.)  Thank you!
>> 
>> There's section 5.3, ``Solving Recurrences'', in ``Discrete
>> Mathematics'' by James L. Heine, Jones and Bartlett Publishers, 1996,
>> page 279.  It shows a straightforward technique for solving
>> recurrences such as the one discussed in this thread.  If you have no
>> technique at all, solving these simpler types of recursion will
>> definitely mean something to you.
>> 
>>>> (*) Problem
>>>>
>>>> Solve
>>>>
>>>>   T(n) = 1                if n = 0
>>>>        = 2 T(n - 1) + 1   if n > 0
>> 
>> Rewriting it to:
>> 
>>   a(0) = 1
>>   a(n) = 2 a(n - 1) + 1
>> 
>> --8<---------------cut here---------------start------------->8---
>> Notation.  Note that ``a'' is a function whose argument is the index
>> of the sequence.  So a(n) is the nth element of the sequence.
>> --8<---------------cut here---------------end--------------->8---
>> 
>> An easy way to expose the construction of the technique is to consider
>> a particular case of the recurrence and generalize.  So consider a(5):
>> 
>>   a(5) = 2 a(4) + 1
>> 
>> Now write an equation for 2 a(4):
>> 
>>   2 a(4) = 2(2a(3) + 1)
>>          = 2^2 a(3) + 2
>> 
>> Now write an equation for 2^2 a(3):
>> 
>>   2^2 a(3) = 2^2 (2a(2) + 1)
>>            = 2^3 a(2) + 2^2
>> 
>> Now write an equation for 2^3 a(2):
>> 
>>   2^3 a(2) = 2^3 (2a(1) + 1)
>>            = 2^4 a(1) + 2^3
>> 
>> No write an equantion for 2^4 a(1):
>> 
>>   2^4 a(1) = 2^4 (2a(0) + 1)
>>            = 2^5 a(0) + 2^4
>> 
>> Since a(0) is the base case of the recurrence, we're done.  Now add
>> all the left hand side of these equations and add all the right hand
>> sides.  We get
>> 
>>   a(5) + 2 a(4) + 2^2 a(3) = 2^3 a(2) + 2^4 a(1) =   2 a(4) + 1 + 
>>   2^2 a(3) + 2 + 2^3 a(2) + 2^2 + 2^4 a(1) + 2^3 + 2^5 a(0) + 2^4
>> 
>> Notice now that all terms of the left hand side cancel out, except
>> a(5).  So we get
>> 
>>   a(5) = 1   + 2   + 2^2 + 2^3 + 2^4
>>        = 2^0 + 2^1 + 2^2 + 2^3 + 2^4
>>        = Sum 2^i from i = 0 to i= 5 - 1
>> 
>> This sum on the right hand side is (2^{5 + 1} - 1) / (2 - 1).  So 
>> 
>>   a(5) = 2^6 - 1 = 63.
>> 
>> The computation of this particular case makes it clear that in
>> general
>> 
>>   a(n) = 2^(n + 1) - 1
>> 
>> is the desired answer.  
>
>
> 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!

[...]

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