

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


On Tuesday, March 21, 2017 at 3:13:37 PM UTC4, Daniel Bastos wrote:
[..] > else: > return 2 * T0r(n  1) + 1 > [(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 


On 21/03/17 20:13, Daniel Bastos wrote:
[..] > = 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 n1, 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. [..] 


Ed Prochak <edprochak> writes:
> On Tuesday, March 21, 2017 at 3:13:37 PM UTC4, Daniel Bastos wrote: Something must be wrong here. Otherwise 1 = Sum(2^i for i=0..n1). And I don't know where I went wrong, but there's something wrong here. > 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. 


David Brown <david.brown> writes:
> On 21/03/17 20:13, Daniel Bastos wrote: > 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 n1, 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. 


Daniel Bastos <dbastos> writes:
> Ed Prochak <edprochak> writes: > Something must be wrong here. Otherwise 1 = Sum(2^i for i=0..n1). > 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..n1). Thanks. 


On 23/03/17 23:11, Daniel Bastos wrote:
> David Brown <david.brown> writes: > Yes. > Okay. :) > 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. 


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


> 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! There's section 5.3, ``Solving Recurrences'', in ``Discrete Mathematics'' by James L. Heine, Jones and Bartlett Publishers, 1996, page 279. It shows a straightforward technique for solving recurrences such as the one discussed in this thread. If you have no technique at all, solving these simpler types of recursion will definitely mean something to you. >> (*) Problem >> Solve >> T(n) = 1 if n = 0 >> = 2 T(n  1) + 1 if n > 0 Rewriting it to: a(0) = 1 a(n) = 2 a(n  1) + 1 8<cut herestart>8 Notation. Note that ``a'' is a function whose argument is the index of the sequence. So a(n) is the nth element of the sequence. 8<cut hereend>8 An easy way to expose the construction of the technique is to consider a particular case of the recurrence and generalize. So consider a(5): a(5) = 2 a(4) + 1 Now write an equation for 2 a(4): 2 a(4) = 2(2a(3) + 1) = 2^2 a(3) + 2 Now write an equation for 2^2 a(3): 2^2 a(3) = 2^2 (2a(2) + 1) = 2^3 a(2) + 2^2 Now write an equation for 2^3 a(2): 2^3 a(2) = 2^3 (2a(1) + 1) = 2^4 a(1) + 2^3 No write an equantion for 2^4 a(1): 2^4 a(1) = 2^4 (2a(0) + 1) = 2^5 a(0) + 2^4 Since a(0) is the base case of the recurrence, we're done. Now add all the left hand side of these equations and add all the right hand sides. We get a(5) + 2 a(4) + 2^2 a(3) = 2^3 a(2) + 2^4 a(1) = 2 a(4) + 1 + 2^2 a(3) + 2 + 2^3 a(2) + 2^2 + 2^4 a(1) + 2^3 + 2^5 a(0) + 2^4 Notice now that all terms of the left hand side cancel out, except a(5). So we get a(5) = 1 + 2 + 2^2 + 2^3 + 2^4 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 = Sum 2^i from i = 0 to i= 5  1 This sum on the right hand side is (2^{5 + 1}  1) / (2  1). So a(5) = 2^6  1 = 63. The computation of this particular case makes it clear that in general a(n) = 2^(n + 1)  1 is the desired answer. The method is called ``the cancellation technique'' by James L. Hein. It works for any recurrence of the form a(0) = P(0) a(n) = Q(n) a(n  1) + P(n), where P(n) and Q(n) are constants. 


On 10/07/2019 16:29, Daniel Bastos wrote:
[..] > general > a(n) = 2^(n + 1)  1 > is the desired answer. No, it most certainly does not. What you have done here is found a likely candidate for an answer. Now you can use that and prove it works, by induction. Until then, you only have a guess that looks good in some tests, but you have no confirmed and proven answer. > The method is called ``the cancellation > technique'' by James L. Hein. It works for any recurrence of the form > a(0) = P(0) > a(n) = Q(n) a(n  1) + P(n), > where P(n) and Q(n) are constants. I don't know it by name, but it is extremely common with any kind of recurrence relation to tabulate a few values, and try to spot a pattern. Once you have spotted it, you then have to /prove/ that it is correct. 


David Brown <david.brown> writes:
> On 10/07/2019 16:29, Daniel Bastos wrote: > No, it most certainly does not. > What you have done here is found a likely candidate for an answer. Now > you can use that and prove it works, by induction. Until then, you only > have a guess that looks good in some tests, but you have no confirmed > and proven answer. I described an illustration of a technique. ``An easy way to expose the construction of the technique [...]'' However, you bring an interesting point. If you use the method above with perfect generality and are able to get a closed form formula for a(n), then you have a proof  no need to show it by induction. See his section 5.3, page 279, first edition. If you disagree, I'll appreciate getting a clear exposition of how this can fail. Thanks! [...] 


On 15/07/2019 20:16, Robert Girault wrote:
> David Brown <david.brown> writes: > I described an illustration of a technique. ``An easy way to expose the > construction of the technique [...]'' However, you bring an interesting > point. If you use the method above with perfect generality and are able > to get a closed form formula for a(n), then you have a proof  no need > to show it by induction. See his section 5.3, page 279, first edition. > If you disagree, I'll appreciate getting a clear exposition of how this > can fail. Thanks! I don't have the book, so I can't look at it. All I can say is that a technique of "spot a pattern from some samples and figure out a formula matching it" is a very useful step for solving many kinds of problems, but it is not in any way a mathematical proof. If you have first proved, for example, that for all problems of the form: a(0) = c_0 a(n) = c_1 * a(n  1) + c_2 there is a solution of the form: a(n) = d_0 ^ (n + d_1) + d_2 /then/ you can use the pattern to figure out what d_0, d_1 and d_2 must be, and have a proven closed formula. But if you don't have such a general proof on hand, then "generalising from a pattern" is not a proof. Imagine you hung out your washing on Monday, and it rained, then you hung it out on Tuesday, and it rained, but on Wednesday when you didn't hang out washing, it was sunny. There is a clear pattern  is that proof that hanging out your washing causes rain? The same applies here. Mathematics is full of patterns that look good, and survive lots of testing, but are wrong in general. Look at the numbers generated by "n^2  n + 41" as n goes from 0 upwards. They are all primes! Until you get to n = 41, that is. 


David Brown <david.brown> writes:
> On 15/07/2019 20:16, Robert Girault wrote: > I don't have the book, so I can't look at it. Here's a relevant passage. I'm not saying the technique proves a closed form formula for all recurrences of a certain form. I'm saying the technique can prove that a certain recurrence of a certain form does have a certain closed form formula. So let me show a concrete example (chapter 5, section 5.3, example 1, page 281, first edition). 8<cut herestart>8 Example 1. Suppose we have given the following recurrence: r(0) = 1 r(n) = 2 r(n  1) + n. This recurrence fits [a certain form where this technique works], so we can solve it by cancellation. Starting with the general term, we obtain the following sequence of equations [...]: r(n) = 2 r(n  1) + n 2 r(n  1) = 2 (2 r(n  2) + (n  1)) = 2^2 r(n  2) + 2 (n  1) 2^2 r(n  2) = 2^2 (2 r(n  3) + (n  2)) = 2^3 r(n  3) + 2^2 (n  2) ... 2^(n  1) r(1) = 2^n r(0) + 2^(n  1) * 1. Now add up all the equations, cancel like terms, and replace r(0) by its value, to get the following equation: r(n) = 2^n + n + 2(n  1) + ... + 2^(n  1) * 1. 8<cut hereend>8 His example stops there with the remark that if we can now find a closed form formula for this ellipsisexpressions, we're done. This ellipsisexpression is (2^0) n + (2^1) (n  1) + ... + (2^(n  1)) * 1 which has closed form formula 2^(n + 1)  n  2 So the recurrence in his example 1 has closed formula s(n) = 2^n + 2^(n + 1)  n  2 We may now ask. Can we be sure /the recurrence r/ has this closed form formula s(n)? I say sure: we've derived it by a perfectly legal method, so the result must follow, that is, the recurrence r(0) = 1 r(n) = 2 r(n  1) + n. must describe the same sequence as s(n) = 2^n + 2^(n + 1)  n  2. I don't see any flaw in this argument. 


On 15/07/2019 23:35, Daniel Bastos wrote:
[..] > must describe the same sequence as > s(n) = 2^n + 2^(n + 1)  n  2. > I don't see any flaw in this argument. Expanding some rounds of the equation and spotting a pattern is /not/ rigorous proof. It is not hard to turn this into a proper proof, but you do it by induction  not by seeing it looks good for a few n, adding an ellipsis, and saying "we're done". The first thread in this thread was worse, since it started with the first couple of rounds and then used "programming verification". Again, let me say that "spotting a pattern" is useful. Checking by code is useful. But it is not mathematical proof. 


David Brown <david.brown> writes:
> On 15/07/2019 23:35, Daniel Bastos wrote: > Expanding some rounds of the equation and spotting a pattern is /not/ > rigorous proof. What's the flaw in the argument? I'd be very interested seeing it. > It is not hard to turn this into a proper proof, but you do it by > induction  not by seeing it looks good for a few n, adding an > ellipsis, and saying "we're done". The first thread in this thread > was worse, since it started with the first couple of rounds and then > used "programming verification". The first message was asking for a method since the only thing I could do then was try to guess the result. I never claimed that was a proof, of course. Nor did I claim so when I presented for the first time in this thread the technique exposed by James Hein  it was an illustration of the technique. In my previous message, however, I do claim I have a perfectly valid argument for that particular recurrence. > Again, let me say that "spotting a pattern" is useful. Checking by > code is useful. But it is not mathematical proof. I'm definitely not disputing that. The argument in the example presented in not spotting a pattern. It writes equations and adds them up and arrives at a conclusion. Perfectly valid as far as I can see. I'll be thankful if you can expose the flaw. Thanks! 