Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #7623
| From | Daniel Bastos <dbastos@toledo.com> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: on solving recurrences |
| Date | 2017-03-23 19:11 -0300 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <86d1d7fxtj.fsf@toledo.com> (permalink) |
| References | <86y3vyh292.fsf@toledo.com> <oatvp6$n6r$1@dont-email.me> |
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.
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