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

Groups > comp.programming > #7625

Re: on solving recurrences

Show all headers | View raw

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.

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