Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #7626
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: on solving recurrences |
| Date | 2017-03-24 09:53 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <ob2mkp$70q$1@dont-email.me> (permalink) |
| References | <86y3vyh292.fsf@toledo.com> <9bb8bad8-bf15-4422-889d-1e482b1059b8@googlegroups.com> <86mvcbfy1q.fsf@toledo.com> <8660izfxlj.fsf@toledo.com> |
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.
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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