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

Groups > comp.programming > #7606 > unrolled thread

on solving recurrences

Back to article view | Back to comp.programming

Contents

  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

#7606 — on solving recurrences

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

[toc] | [next] | [standalone]

#7615

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

You did a nice analysis.
Both versions T0r() and T0() are recursive.
I note you unrolled the loop one step only in the T0r() method
>     elif n == 1:
>         return 3

So is there something you think is wrong here?

Ed

[toc] | [prev] | [next] | [standalone]

#7622

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.

[toc] | [prev] | [next] | [standalone]

#7624

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.

[toc] | [prev] | [next] | [standalone]

#7626

On 23/03/17 23:16, Daniel Bastos wrote:
> 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.
> 

I can't understand why you keep wanting to put this "Sum(...)" bit in.
It does not simplify anything - it leaves the result as a mess.

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

This is a very well known result, and is easily verified.  If you don't
see it, write out a table of the first 4 or 5 values here.  Then do the
same, but write the numbers in binary rather than decimal.  The pattern
will leap out at you.  And you can practice your proof by induction
skills by proving it.

[toc] | [prev] | [next] | [standalone]

#7616

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!
> 
> (*) 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
> 

That's good so far.

At this point, it should be rather obvious that the solution involves
2^n.  Let's look at some actual values:

n	t(n)	2^n
-------------------
0	1	1
1	3	2
2	7	4
3	15	8
4	31	16


It is rather obvious now that t(n) = 2^(n + 1) - 1.

Obvious is not a proof, of course, but it's a lot easier to prove a
result if you know what you want to prove!

Prove the assertion by induction.  It is easy to see that the result
works for 0.

Assume that it works for i up to n-1, where n > 0.  Then

t(n) = 2 * t(n - 1) + 1
     = 2 * (2^(n - 1 + 1) - 1) + 1	// By induction assumption
     = 2 * 2 ^ n - 2 + 1
     = 2 ^ (n + 1) - 1

QED.


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

[toc] | [prev] | [next] | [standalone]

#7623

David Brown <david.brown@hesbynett.no> writes:

> 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!
>> 
>> (*) 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
>> 
>
> That's good so far.
>
> At this point, it should be rather obvious that the solution involves
> 2^n.  

Yes.

> Let's look at some actual values:
>
> n	t(n)	2^n
> -------------------
> 0	1	1
> 1	3	2
> 2	7	4
> 3	15	8
> 4	31	16
>
>
> It is rather obvious now that t(n) = 2^(n + 1) - 1.

Okay. :-)

> Obvious is not a proof, of course, but it's a lot easier to prove a
> result if you know what you want to prove!
>
> Prove the assertion by induction.  It is easy to see that the result
> works for 0.
>
> Assume that it works for i up to n-1, where n > 0.  Then
>
> t(n) = 2 * t(n - 1) + 1
>      = 2 * (2^(n - 1 + 1) - 1) + 1	// By induction assumption
>      = 2 * 2 ^ n - 2 + 1
>      = 2 ^ (n + 1) - 1
>
> QED.

I like constructions.  Guessing and proving requires insight.  I don't
have a whole lot of that.  Thanks for your attention.

[toc] | [prev] | [next] | [standalone]

#7625

On 23/03/17 23:11, Daniel Bastos wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> 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!
>>>
>>> (*) 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
>>>
>>
>> That's good so far.
>>
>> At this point, it should be rather obvious that the solution involves
>> 2^n.  
> 
> Yes.
> 
>> Let's look at some actual values:
>>
>> n	t(n)	2^n
>> -------------------
>> 0	1	1
>> 1	3	2
>> 2	7	4
>> 3	15	8
>> 4	31	16
>>
>>
>> It is rather obvious now that t(n) = 2^(n + 1) - 1.
> 
> Okay. :-)
> 
>> Obvious is not a proof, of course, but it's a lot easier to prove a
>> result if you know what you want to prove!
>>
>> Prove the assertion by induction.  It is easy to see that the result
>> works for 0.
>>
>> Assume that it works for i up to n-1, where n > 0.  Then
>>
>> t(n) = 2 * t(n - 1) + 1
>>      = 2 * (2^(n - 1 + 1) - 1) + 1	// By induction assumption
>>      = 2 * 2 ^ n - 2 + 1
>>      = 2 ^ (n + 1) - 1
>>
>> QED.
> 
> I like constructions.  Guessing and proving requires insight.  I don't
> have a whole lot of that.  Thanks for your attention.
> 

It may look like guessing, but it is a matter of knowing the type of
difference equation - a difference equation that involves multiplying by
k at each step is going to involve k^n somewhere, just as one that
involves adding k at each step is going to involve k*n somewhere.  So
you can start with that term, with some flexibility on the multiplier,
and pull that bit out.  Then you can work on the parts that are left,
and see what extras are needed to make everything correct.  You don't
have to start with a lucky guess of the correct answer.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web