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

Groups > comp.programming > #7624

Re: on solving recurrences

Show all headers | View raw

Daniel Bastos <dbastos@toledo.com> writes:

> Ed Prochak <edprochak@gmail.com> writes:
>
>> On Tuesday, March 21, 2017 at 3:13:37 PM UTC-4, 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!
>>> 
>>> (*) 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).
>
> Something must be wrong here.  Otherwise -1 = Sum(2^i for i=0..n-1).
> And I don't know where I went wrong, but there's something wrong here.

After seeing David Brown's message: I must have got my counters wrong
since I thought I verified the result numerically.  It's not 2^n - 1.
It's 2^(n+1) - 1.  The equation is therefore

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

Thanks.

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

csiph-web