Path: csiph.com!aioe.org!.POSTED.FC3R3RclhwVbyGOLJeQr/Q.user.gioia.aioe.org!not-for-mail
From: Daniel Bastos <dbastos@toledo.com>
Newsgroups: comp.programming
Subject: Re: on solving recurrences
Date: Wed, 10 Jul 2019 11:29:22 -0300
Organization: Aioe.org NNTP Server
Lines: 86
Message-ID: <86v9wagdz1.fsf@dev.null>
References: <86y3vyh292.fsf@toledo.com> <oatvp6$n6r$1@dont-email.me>
NNTP-Posting-Host: FC3R3RclhwVbyGOLJeQr/Q.user.gioia.aioe.org
Mime-Version: 1.0
Content-Type: text/plain
X-Complaints-To: abuse@aioe.org
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt)
Cancel-Lock: sha1:kPnhKw8WiT/+ryZFKwrXWayBRSI=
X-Notice: Filtered by postfilter v. 0.9.2
Xref: csiph.com comp.programming:10059

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