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

Groups > comp.programming > #10059

Re: on solving recurrences

Show all headers | View raw

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

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