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

Groups > comp.programming > #7622

Re: on solving recurrences

Show key headers only | View raw

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.

>> 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)]
>
> I am not sure what your question is.

My question was the first sentence.  I showed my struggle to resolve
problems like this in order to help someone suggest me a book.  I lack
strategies to resolve recurrences.  My only strategy is to unfold the
recursion and see a pattern.  That's all I can do.  I'm getting the
feeling that it all boils down to solving a lot of sums, products and
things like that.  So it's the kind of work that involves studying
discrete mathematics, calculus and whatnot.

> You did a nice analysis.

Thank you!

> Both versions T0r() and T0() are recursive.

Both?  T0() is not recursive.  It doesn't mention T0 in its body.

> I note you unrolled the loop one step only in the T0r() method
>>     elif n == 1:
>>         return 3

That was an accident.  In one of my attempts I used (n - 2), so I had to
worry about not going negative.  Thanks for pointing it out.

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