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

Groups > comp.programming > #7606

on solving recurrences

Show all headers | View raw

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)]

Back to comp.programming | Previous | Next — 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

csiph-web