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

Groups > comp.programming > #10060

Re: on solving recurrences

Show all headers | View raw

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.

> The method is called ``the cancellation
> technique'' by James L. Hein.  It works for any recurrence of the form
> 
>   a(0) = P(0)
>   a(n) = Q(n) a(n - 1) + P(n),
> 
> where P(n) and Q(n) are constants.
> 

I don't know it by name, but it is extremely common with any kind of
recurrence relation to tabulate a few values, and try to spot a pattern.
 Once you have spotted it, you then have to /prove/ that it is correct.

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