Path: csiph.com!aioe.org!.POSTED!not-for-mail
From: Daniel Bastos <dbastos@toledo.com>
Newsgroups: comp.programming
Subject: on solving recurrences
Date: Tue, 21 Mar 2017 16:13:29 -0300
Organization: Aioe.org NNTP Server
Lines: 64
Message-ID: <86y3vyh292.fsf@toledo.com>
NNTP-Posting-Host: BuEqJTf8bEmpZhBIUMG+Zw.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:Y9R4DlRIcFM3ShE32pceE5txQv4=
X-Notice: Filtered by postfilter v. 0.8.2
Xref: csiph.com comp.programming:7606

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!

(*) Problem

Solve

  T(n) = 1                if n = 0
       = 2 T(n - 1) + 1   if n > 0

Remark.  The only way I know how to solve this is by guessing.  Here's
how I do it.

Solution.  First I look at say T(8).

  T(8) = 2 T(7) + 1
       = 2 (2 T(6) + 1) + 1
       = 2 (2 (2 T(5) + 1) + 1) + 1
       = 2 (2 (2 (2 T(4) + 1) + 1) + 1) + 1

So I see a pattern emerging.  I ``went down 4 levels'' and I found this:

       = 2 (2 (2^2 T(4) + (1*2 + 1)) + 1) + 1
       = 2 (2^3 T(4) + (1*2*2 + 1*2) + 1) + 1
       = 2^4 T(4) + 1*2*2*2 + 1*2*2 + 1*2 + 1
       = 2^4 T(4) + 2^3 + 2^2 + 2^1 + 2^0

So I must now discover what is Sum(2^i for i=0..n-1).  Programming
verification (see below) makes clear that we don't actually need to find
that because it gets easy to see --- numerically --- that we have a case
for 2^n - 1.

Somehow 

  2^n - 1 = 2^n + Sum(2^i for i=0..n-1).

Thank you.

(*) Programming verification

def xrange(beg, end):
    # Python's range(x,y) goes up to y - 1.  We usually want to be
    # inclusive.
    return range(beg, end + 1)

def T0(n):
    if n == 0:
        return 1
    elif n == 1:
        return 3
    else:
        return 2**n + sum([2**i for i in xrange(0, n - 1)])

def T0r(n):
    if n == 0:
        return 1
    else:
        return 2 * T0r(n - 1) + 1

>>> [(t0(i), t0r(i)) for i in range(8)]
[(1, 1), (3, 3), (7, 7), (15, 15), (31, 31), (63, 63), (127, 127), (255, 255)]