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

Groups > comp.programming > #7606 > unrolled thread

on solving recurrences

Back to article view | Back to comp.programming

Contents

  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
      Re: on solving recurrences Daniel Bastos <dbastos@toledo.com> - 2019-07-10 11:29 -0300
        Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2019-07-10 17:25 +0200
          Re: on solving recurrences Robert Girault <r@dev.null> - 2019-07-15 15:16 -0300
            Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2019-07-15 21:23 +0200
              Re: on solving recurrences Daniel Bastos <dbastos@toledo.com> - 2019-07-15 18:35 -0300
                Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2019-07-16 00:00 +0200
                  Re: on solving recurrences Daniel Bastos <dbastos@toledo.com> - 2019-07-15 19:32 -0300
                    Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2019-07-16 09:32 +0200
                      Re: on solving recurrences Daniel Bastos <dbastos@toledo.com> - 2019-07-16 11:40 -0300
                        Re: on solving recurrences David Brown <david.brown@hesbynett.no> - 2019-07-16 17:36 +0200
                        Re: on solving recurrences Horizon68 like Menz <cdalten@gmail.com> - 2019-07-17 05:15 -0700

#7606 — on solving recurrences

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

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

[toc] | [next] | [standalone]

#7615

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

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

[toc] | [prev] | [next] | [standalone]

#7622

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.

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

[toc] | [prev] | [next] | [standalone]

#7624

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.

[toc] | [prev] | [next] | [standalone]

#7626

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.

[toc] | [prev] | [next] | [standalone]

#7616

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

[toc] | [prev] | [next] | [standalone]

#7623

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.

[toc] | [prev] | [next] | [standalone]

#7625

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.

[toc] | [prev] | [next] | [standalone]

#10059

> 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 here---------------start------------->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 here---------------end--------------->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.

[toc] | [prev] | [next] | [standalone]

#10060

On 10/07/2019 16:29, Daniel Bastos wrote:
>> 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 here---------------start------------->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 here---------------end--------------->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.  


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.

[toc] | [prev] | [next] | [standalone]

#10066

David Brown <david.brown@hesbynett.no> writes:

> On 10/07/2019 16:29, Daniel Bastos wrote:
>>> 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 here---------------start------------->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 here---------------end--------------->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.  
>
>
> 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!

[...]

[toc] | [prev] | [next] | [standalone]

#10067

On 15/07/2019 20:16, Robert Girault wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 

>>
>> 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!
> 

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.

[toc] | [prev] | [next] | [standalone]

#10069

David Brown <david.brown@hesbynett.no> writes:

> On 15/07/2019 20:16, Robert Girault wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>>
>>> 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!
>
> 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 here---------------start------------->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 here---------------end--------------->8---

His example stops there with the remark that if we can now find a closed
form formula for this ellipsis-expressions, we're done.  This
ellipsis-expression 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.

[toc] | [prev] | [next] | [standalone]

#10070

On 15/07/2019 23:35, Daniel Bastos wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 15/07/2019 20:16, Robert Girault wrote:
>>> David Brown <david.brown@hesbynett.no> writes:
>>>>
>>>> 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!
>>
>> 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 here---------------start------------->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 here---------------end--------------->8---
> 
> His example stops there with the remark that if we can now find a closed
> form formula for this ellipsis-expressions, we're done.  This
> ellipsis-expression 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.
> 

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.

[toc] | [prev] | [next] | [standalone]

#10071

David Brown <david.brown@hesbynett.no> writes:

> On 15/07/2019 23:35, Daniel Bastos wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>
>>> On 15/07/2019 20:16, Robert Girault wrote:
>>>> David Brown <david.brown@hesbynett.no> writes:
>>>>>
>>>>> 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!
>>>
>>> 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 here---------------start------------->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 here---------------end--------------->8---
>>
>> His example stops there with the remark that if we can now find a closed
>> form formula for this ellipsis-expressions, we're done.  This
>> ellipsis-expression 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.
>
> 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!

[toc] | [prev] | [next] | [standalone]

#10072

On 16/07/2019 00:32, Daniel Bastos wrote:

> 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!
> 

I really don't want to sound patronising here, but do you understand
what "proof by induction" means, and how it works?  If so, then I think
you will quickly see the point, and how to turn this technique into a
proof.  If not, then I am not going to be able to show you it in a few
Usenet posts - but I think you should have no problem learning about it
from some web tutorial.  (Wikipedia is often a good starting point for
some maths topics, but can sometimes be a bit too technical.)

"Proof by induction" gives you the step to go from "I see the pattern
here from expanding a few times" to "I know it always works for all
cases."  It fixes the flaw in your argument - the missing /proof/ that
the generalisation works.

[toc] | [prev] | [next] | [standalone]

#10073

David Brown <david.brown@hesbynett.no> writes:

> On 16/07/2019 00:32, Daniel Bastos wrote:
>
>> 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!
>
> I really don't want to sound patronising here, but do you understand
> what "proof by induction" means, and how it works?  

Your answer here seems unconnected to the passage you quote.  Induction
is not the problem here.  If a step in a mathematical argument is
incorrect, you have to show it leads to trouble.  I was hoping you'd
show that.

I think you see nothing as incorrect, but something lacking rigor.  I'm
trying to guess what it is that lacks rigor here.  Perhaps you consider
invalid the n applications of the definition of the recurrence.  For
example, the recurrence is defined as

  r(0) = 1
  r(n) = 2 r(n - 1) + n

James Hein applies the definition n times when he writes

            r(n) = 2 r(n - 1) + n           -- 1st application
      2 r(n - 1) = 2 (2 r(n - 2) + (n - 1)) -- 2nd application
   ...
  2^(n - 1) r(1) = 2^n r(0) + 2^(n - 1) * 1 -- nth application

From these n equations, he derives another where r(n) is isolated at the
left hand side.  Perhaps you think that /can be/ equivalent to a proof
by induction, but, not being rigorously shown, cannot be considered
equivalent.

--8<---------------cut here---------------start------------->8---
Perhaps the situation is analogous to solving a first-order separable
differential equation such as

  dy/dx = y.

One considers the left hand side as a fraction of different variables
and manipulates it to get

  1/y dy = dx

then some integral sign is miraculously attached to both sides

 int 1/y dy = int dx

and each side is integrated with respect to y, x, respectively, yielding

  ln |y| + c(1) = x + c(2)
         ln |y| = x + c(3)
              y = c(4) e^x.

The step where integral signs are attached is very strange to me and
until someone explains to me how that makes sense, I consider it
invalid, but the fact is that there's a theorem that states that you can
go from

  dy/dx = y

to 

  int 1/y dy = int dx.

So the steps written in that solution can be seen as an informal way to
remember what the theorem says.
--8<---------------cut here---------------end--------------->8---

So perhaps the writing of n equations to add them up afterwards is a
mnemonic that lets us get the desired result, but it can only be
considered a legal step if shown by induction --- despite it probably
being impossible to produce an incorrect answer.

But then again, I don't know if that is the problem you see.  It's not
clear.  I can only conclude your problem is in the lack of rigor in the
powerful ellipsis.  You could illustrate such dangers by presenting the
all horses are of the same color argument, but that would be a radical
change of subject: the thread began with a request for help on solving
the most basic types of recurrences, pointing out a good book on the
topic that was too advanced for helping at that point.

[...]

[toc] | [prev] | [next] | [standalone]

#10074

On 16/07/2019 16:40, Daniel Bastos wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 16/07/2019 00:32, Daniel Bastos wrote:
>>
>>> 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!
>>
>> I really don't want to sound patronising here, but do you understand
>> what "proof by induction" means, and how it works?  
> 
> Your answer here seems unconnected to the passage you quote.  Induction
> is not the problem here.  If a step in a mathematical argument is
> incorrect, you have to show it leads to trouble.  I was hoping you'd
> show that.
> 
> I think you see nothing as incorrect, but something lacking rigor.

Yes, that is correct.  I don't think there are mistakes in what you have
written, it is simply that it is missing the parts that make it a proof
rather than a "this seems to work" answer.  (Don't misunderstand me here
- sometimes "this looks right" is all you need.)

>  I'm
> trying to guess what it is that lacks rigor here.  Perhaps you consider
> invalid the n applications of the definition of the recurrence.  For
> example, the recurrence is defined as
> 
>   r(0) = 1
>   r(n) = 2 r(n - 1) + n
> 
> James Hein applies the definition n times when he writes
> 
>             r(n) = 2 r(n - 1) + n           -- 1st application
>       2 r(n - 1) = 2 (2 r(n - 2) + (n - 1)) -- 2nd application
>    ...
>   2^(n - 1) r(1) = 2^n r(0) + 2^(n - 1) * 1 -- nth application
> 
> From these n equations, he derives another where r(n) is isolated at the
> left hand side.  Perhaps you think that /can be/ equivalent to a proof
> by induction, but, not being rigorously shown, cannot be considered
> equivalent.

It is the "..." part that is not rigorous.

> 
> --8<---------------cut here---------------start------------->8---
> Perhaps the situation is analogous to solving a first-order separable
> differential equation such as
> 
>   dy/dx = y.
> 
> One considers the left hand side as a fraction of different variables
> and manipulates it to get
> 
>   1/y dy = dx
> 
> then some integral sign is miraculously attached to both sides
> 
>  int 1/y dy = int dx
> 
> and each side is integrated with respect to y, x, respectively, yielding
> 
>   ln |y| + c(1) = x + c(2)
>          ln |y| = x + c(3)
>               y = c(4) e^x.
> 
> The step where integral signs are attached is very strange to me and
> until someone explains to me how that makes sense, I consider it
> invalid, but the fact is that there's a theorem that states that you can
> go from
> 
>   dy/dx = y
> 
> to 
> 
>   int 1/y dy = int dx.
> 
> So the steps written in that solution can be seen as an informal way to
> remember what the theorem says.
> --8<---------------cut here---------------end--------------->8---

In all these steps, you are progressing from one step to the next.
Clearly you need to know that the steps are valid.  It is not trivial to
prove that you can "miraculously attach an integral sign to both sides",
but that would require a separate and substantial proof, so it's
reasonable to take it as read here.

But you can't jump over the "..." lines quite as lightly as you do.

> 
> So perhaps the writing of n equations to add them up afterwards is a
> mnemonic that lets us get the desired result, but it can only be
> considered a legal step if shown by induction --- despite it probably
> being impossible to produce an incorrect answer.

Yes, that is a fair way to put it.

> 
> But then again, I don't know if that is the problem you see.  It's not
> clear.  I can only conclude your problem is in the lack of rigor in the
> powerful ellipsis.  You could illustrate such dangers by presenting the
> all horses are of the same color argument, but that would be a radical
> change of subject: the thread began with a request for help on solving
> the most basic types of recurrences, pointing out a good book on the
> topic that was too advanced for helping at that point.
> 

I am not sure how much help I can be with books - it's over 30 years
since I learned this stuff.

But please, look back at the "proof by induction" method I posted at the
start of this thread, a year and a half ago:


"""
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.
"""

This is simpler, and IMHO clearer, than the method you were showing -
and it is a rigorous proof.


So while I can't recommend any particular book for you, it seems I can
recommend a book for you to avoid - the one you have been using.


It might also help if you gave a little background about what stage you
are at, and where you are aiming.  Are you a student learning
mathematics?  Is this a hobby?  (Some people consider the idea of maths
as a hobby to be very odd - I think it's fun.)  Are you trying to use
this in software of some kind - or trying to use software to see results
from the maths?

[toc] | [prev] | [next] | [standalone]

#10075

On Tuesday, July 16, 2019 at 7:40:12 AM UTC-7, Daniel Bastos wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
> > On 16/07/2019 00:32, Daniel Bastos wrote:
> >
> >> 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!
> >
> > I really don't want to sound patronising here, but do you understand
> > what "proof by induction" means, and how it works?  
> 
> Your answer here seems unconnected to the passage you quote.  Induction
> is not the problem here.  If a step in a mathematical argument is
> incorrect, you have to show it leads to trouble.  I was hoping you'd
> show that.
> 
> I think you see nothing as incorrect, but something lacking rigor.  I'm
> trying to guess what it is that lacks rigor here.  Perhaps you consider
> invalid the n applications of the definition of the recurrence.  For
> example, the recurrence is defined as
> 
>   r(0) = 1
>   r(n) = 2 r(n - 1) + n
> 
> James Hein applies the definition n times when he writes
> 
>             r(n) = 2 r(n - 1) + n           -- 1st application
>       2 r(n - 1) = 2 (2 r(n - 2) + (n - 1)) -- 2nd application
>    ...
>   2^(n - 1) r(1) = 2^n r(0) + 2^(n - 1) * 1 -- nth application
> 
> From these n equations, he derives another where r(n) is isolated at the
> left hand side.  Perhaps you think that /can be/ equivalent to a proof
> by induction, but, not being rigorously shown, cannot be considered
> equivalent.
> 
> --8<---------------cut here---------------start------------->8---
> Perhaps the situation is analogous to solving a first-order separable
> differential equation such as
> 
>   dy/dx = y.
> 
> One considers the left hand side as a fraction of different variables
> and manipulates it to get
> 
>   1/y dy = dx
> 
> then some integral sign is miraculously attached to both sides
> 
>  int 1/y dy = int dx
> 
> and each side is integrated with respect to y, x, respectively, yielding
> 
>   ln |y| + c(1) = x + c(2)
>          ln |y| = x + c(3)
>               y = c(4) e^x.
> 
> The step where integral signs are attached is very strange to me and
> until someone explains to me how that makes sense, I consider it
> invalid, but the fact is that there's a theorem that states that you can
> go from

If this argument is part of the hypothesis, and not part of the actual proof, then I see nothing strange about this.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web