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

Groups > comp.programming > #7616

Re: on solving recurrences

Show all headers | View raw

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

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