Notices
Results 1 to 44 of 44

Thread: Induction

  1. #1 Induction 
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I feel like I really need a lesson on mathematical induction. I tried it once and failed miserably. I understand the idea but I can't do it right. I've seen it in the case of proving that and things like that. However I'm clueless when it comes to proving things where you have, say the objects and have to use it on to prove that something works for objects. I have to use induction for the proof I'm currently working on, but I want to be able to do it myself so I'm not posting that problem here. Any help would be appreciated.


    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Ph.D.
    Join Date
    Jul 2008
    Location
    New York State
    Posts
    846
    The basic idea is to determine if a proposition about something which depends on integers holds for all integers (n). The approach has two basic steps:
    1) Show that the proposition holds for n=1.
    2) Assume that the proposition is true for n=k. Show that the proposition then holds for n=k+1.

    The idea behind it is that once you have carried out step one, you know that the proposition holds for n=1. Step 2 then implies that it therefore holds for n=2, and therefore it holds for n=3, and therefore it holds for n=4, etc.


    Reply With Quote  
     

  4. #3 Re: Induction 
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    I feel like I really need a lesson on mathematical induction. I tried it once and failed miserably. I understand the idea but I can't do it right. I've seen it in the case of proving that and things like that. However I'm clueless when it comes to proving things where you have, say the objects and have to use it on to prove that something works for objects. I have to use induction for the proof I'm currently working on, but I want to be able to do it myself so I'm not posting that problem here. Any help would be appreciated.
    It is not clear from you post just what the problem is. Here is a link to a proof by induction of a formula for the first n cubes in another thread. Take a look at that proof and see if it helps you understand the basic process.

    http://www.thescienceforum.com/viewt...r=asc&start=45
    Reply With Quote  
     

  5. #4  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    I understand it there where you have s in a formula. What I don't understand is how you work with it when the is in a subscript or something.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  6. #5  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    I understand it there where you have s in a formula. What I don't understand is how you work with it when the is in a subscript or something.
    I think you need to show us an example of such a proof that is giving you trouble.
    Reply With Quote  
     

  7. #6  
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,526
    ...Bearing in mind that I, as an interested outsider, am still of the opinion that Induction cannot work with regard to any series except one consisting of whole numbers. Or is this a false notion?
    Reply With Quote  
     

  8. #7  
    Forum Ph.D.
    Join Date
    Jul 2008
    Location
    New York State
    Posts
    846
    Quote Originally Posted by sunshinewarrior
    ...Bearing in mind that I, as an interested outsider, am still of the opinion that Induction cannot work with regard to any series except one consisting of whole numbers. Or is this a false notion?
    The terms in the sequence are not necessarily integers. However each term is dependent on an integer and succeeding terms depend on succeeding integers.
    Reply With Quote  
     

  9. #8  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    induction is used on orderd sequences, that is, sequences with numbered terms, where those numbers must be integers, or, more commonly, natural numbers
    Wise men speak because they have something to say; Fools, because they have to say something.
    -Plato

    Reply With Quote  
     

  10. #9  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by sunshinewarrior
    ...Bearing in mind that I, as an interested outsider, am still of the opinion that Induction cannot work with regard to any series except one consisting of whole numbers. Or is this a false notion?
    Induction is a means of proof for statements involving the natural numbers, independent of how the natural numbers are involved. The principle is very simple -- if a set of natural numbers contains a natural number K, and if whenever it contains a natural number n it also containse its successor (n+1), then that set contains all natural numbers greater than or equal to K.

    Most commonly you have a statement A(n) which makes an assertion regarding the natural number n. You wish to prove that A(n) is true for all n. So first you show that A(1) is true. Then you show that if A(n) is true that it logically follows that A(n+1) is true. You then conclude that A(n) is true for all natural numbers n.
    Reply With Quote  
     

  11. #10  
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,526
    Quote Originally Posted by DrRocket
    Quote Originally Posted by sunshinewarrior
    ...Bearing in mind that I, as an interested outsider, am still of the opinion that Induction cannot work with regard to any series except one consisting of whole numbers. Or is this a false notion?
    Induction is a means of proof for statements involving the natural numbers, independent of how the natural numbers are involved. The principle is very simple -- if a set of natural numbers contains a natural number K, and if whenever it contains a natural number n it also containse its successor (n+1), then that set contains all natural numbers greater than or equal to K.

    Most commonly you have a statement A(n) which makes an assertion regarding the natural number n. You wish to prove that A(n) is true for all n. So first you show that A(1) is true. Then you show that if A(n) is true that it logically follows that A(n+1) is true. You then conclude that A(n) is true for all natural numbers n.
    That's what I thought - but couldn't put into words as well as you guys.

    Thanks.

    Quote Originally Posted by Chemboy
    I feel like I really need a lesson on mathematical induction. I tried it once and failed miserably. I understand the idea but I can't do it right. I've seen it in the case of proving that and things like that. However I'm clueless when it comes to proving things where you have, say the objects and have to use it on to prove that something works for objects. I have to use induction for the proof I'm currently working on, but I want to be able to do it myself so I'm not posting that problem here. Any help would be appreciated.
    From these various postings it seems to me that it can only work on your set of objects if there is a rule regarding them such that a relationship can be mathematically formulated between and .

    Is this the case in the problem on which you're working?
    Reply With Quote  
     

  12. #11  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    No, I don't think it is. Unfortunately the only example I have is the problem I'm trying to do, which I want to do myself.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  13. #12  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    you can only do it if you can establish a mathematical relation between all of the members of your sequence. i.e. there must be some rule that the nth term follows.
    Wise men speak because they have something to say; Fools, because they have to say something.
    -Plato

    Reply With Quote  
     

  14. #13  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Ummm,

    Every uncountable set has at least one countable proper subset. So we know that is uncountable, then is countable, say. . But "countable" means a bijection from the natural numbers to , say ,

    Then since there is a natural ordering on this induces an ordering on such that, for any there will always be some . (This is true, of course, for any subset of )

    Induction would fail should this not be true.
    Reply With Quote  
     

  15. #14  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    No, I don't think it is. Unfortunately the only example I have is the problem I'm trying to do, which I want to do myself.
    If there is no relationship that you can clearly formulate relating to then you may dealing with a proof that is not amenable to the technique of induction.

    Do you have some reason to believe that induction is the right tool for your problem ?
    Reply With Quote  
     

  16. #15  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    The author says it is. haha. I'll look at it more closely though when I'm able.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  17. #16  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Quote Originally Posted by Chemboy
    No, I don't think it is. Unfortunately the only example I have is the problem I'm trying to do, which I want to do myself.
    Say what, post your problem, and I will do my best to ensure that nobody does it for you, at least not for your eyes. No guarantees (because of time zones)

    To all: Should Chemboy decide to post his problem, I hope we all here will respect his wish, namely that he wants to solve it himself.
    Reply With Quote  
     

  18. #17  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Guitarist

    To all: Should Chemboy decide to post his problem, I hope we all here will respect his wish, namely that he wants to solve it himself.
    Agreed
    Reply With Quote  
     

  19. #18  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Thank you very much Guitarist and DrRocket, I appreciate it.

    Let be positive real numbers. Prove that if , then , where equality occurs iff .

    The case for 1 I think is trivial, and I can show it for 2 (that was problem #6, this is #7).

    The hint in the book says "Use induction and Problem 6."
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  20. #19  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Thank you very much Guitarist and DrRocket, I appreciate it.

    Let be positive real numbers. Prove that if , then , where equality occurs iff .

    The case for 1 I think is trivial, and I can show it for 2 (that was problem #6, this is #7).

    The hint in the book says "Use induction and Problem 6."
    It is possible to prove that theorem by induction.

    If you will give me your permission, I will give you a one-line hint (with no mathematical symbols) that might help you just a little, merely pointing out the potential usefulness of some things that I know that you already know.
    Reply With Quote  
     

  21. #20  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Sure, go ahead. I just don't want the whole thing given away, or enough information to make it obvious.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  22. #21  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    Sure, go ahead. I just don't want the whole thing given away, or enough information to make it obvious.
    OK use the associative property of multiplication and the results for the case n=2 from your exercise 6.
    Reply With Quote  
     

  23. #22  
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,526
    May I ask a question for explication? I don't believe it has anything to do with the solution (the Proof using Induction), but it will help me grasp the problem better.

    Would that be ok?
    Reply With Quote  
     

  24. #23  
    Forum Bachelors Degree
    Join Date
    Mar 2009
    Posts
    421
    Examples of induction using the well-ordering of the natural numbers:

    Theorem: Every dog has his day.

    proof: Suppose that some dog did not have his day. Call that dog D. Without loss of generality, we may assume that D is the first dog who did not have his day. But then today is the day for that unique dog. Contradiction.

    Theorem: Every positive integer is special.

    proof: Suppose not. Let N be the least positive integer which is not special. That sounds like a pretty special quality to me. Contradiction.
    Reply With Quote  
     

  25. #24  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    I would have never thought to use induction that way... very nice use of the concept on rather abstract ideas
    Wise men speak because they have something to say; Fools, because they have to say something.
    -Plato

    Reply With Quote  
     

  26. #25  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by sunshinewarrior
    May I ask a question for explication? I don't believe it has anything to do with the solution (the Proof using Induction), but it will help me grasp the problem better.

    Would that be ok?
    You can ask anything that you want to ask. It is, after all, your problem that we are addressing. You get to make the rules here.


    Edit: Oops -- I lost track of the source of the question. I was addressing Chemboy, but sunshinewarrior asked the question.
    Reply With Quote  
     

  27. #26  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Quote Originally Posted by sunshinewarrior
    May I ask a question for explication? I don't believe it has anything to do with the solution (the Proof using Induction), but it will help me grasp the problem better.

    Would that be ok?
    Yep, go for it. Maybe if the answer would be too revealing the reply could be via PM?
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  28. #27  
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,526
    Thanks.

    The question was this:

    Are we allowed to assume that the value of is the same for every value of ?

    Or are we even to take that the value of will differ depending upon the value of ? (Or in other terms, the sets defined by values of are not necessarily proper subsets of those defined by the higher values of .)

    Does this question make sense?
    Reply With Quote  
     

  29. #28  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    looking at his problem, it looks as if each member of the sequence is equivalent to every other member, and is equal to 1. so it doesn't matter what n is: for all n
    Wise men speak because they have something to say; Fools, because they have to say something.
    -Plato

    Reply With Quote  
     

  30. #29  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    No. It just says that that's the only way is true.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  31. #30  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    can you post your proof for the case n=2?
    Wise men speak because they have something to say; Fools, because they have to say something.
    -Plato

    Reply With Quote  
     

  32. #31  
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,526
    Quote Originally Posted by Chemboy
    No. It just says that that's the only way is true.
    That's what I assumed - but do you have an idea how my question should be tackled? Unique s or varying?
    Reply With Quote  
     

  33. #32  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    That response was just to Arcane... I would think the s can vary. No reason to think they can't, really.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  34. #33  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by sunshinewarrior
    Quote Originally Posted by Chemboy
    No. It just says that that's the only way is true.
    That's what I assumed - but do you have an idea how my question should be tackled? Unique s or varying?
    The s are permitted but not required to vary. If they do not vary then the theorem is trivial, since the fact their product is zero would then imply that they would all be 1, since they are positive by hypothesis.
    Reply With Quote  
     

  35. #34  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    I suspect part of the problem here is in the index notation. Here, refers to the number of factors in the product, and hence to the same number of terms in the sum. It is a positive integer. That is is the "last" factor or term in a string that is precisely factors/terms long.

    If we wish to refer to a particular factor or term, it would be better to use . This means that is integer, but does not mean that is integer, and in general will not be

    So yes, for any we may have that , but for full generality it would better not to assume so.

    Actually, unless I have misunderstood the problem, it is quite straightforward. But, since the reals comprise rationals, irrationals and transcendentals, the only way through is by abstraction; that is, don't attempt to use "actual" reals. As far as I can see it, this part of the object of the exercise.

    But then, what do I know?
    Reply With Quote  
     

  36. #35  
    Forum Bachelors Degree
    Join Date
    Mar 2009
    Posts
    421
    Quote Originally Posted by DrRocket
    OK use the associative property of multiplication...
    Aarg, that sounds like something you'd see in a Hungerford textbook.
    Reply With Quote  
     

  37. #36  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    So. I haven't been able to put an awful lot of time into this, unfortunately. For the case the elements have to be an and a . Can I do the same thing with elements, and call the first elements and the th element ? And then can I do the same thing as when I showed that the case is true? (of course I haven't shown that, but I'm sure you know it)
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  38. #37  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by Chemboy
    So. I haven't been able to put an awful lot of time into this, unfortunately. For the case the elements have to be an and a . Can I do the same thing with elements, and call the first elements and the th element ? And then can I do the same thing as when I showed that the case is true? (of course I haven't shown that, but I'm sure you know it)
    I don't quite follow your question, but I think the answer is "no."

    The case n=2 actually takes some work. It does not follow, at least as far as I can see, from the case n=1. The case n=1 is trivial. The case n=2 is not so trivial and is the key to the remainder of the proof by induction. That in no way is meant to imply that the inductive step in any way resembles the proof for n=2.

    This is not a stupendously difficult proof (Wiles's proof of Fermat's Last Theorem was stupendously difficult) but it is not trivial either. It is not so straightforward as the typical proofs by induction that one sees in school classes that are designed to simply provide a little exposure to inductive proofs. This one takes some thought and some work, and is not just pushing symbols.

    Keep plugging away. This is a good exercise.
    Reply With Quote  
     

  39. #38 A Solution 
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    At chemboy's request here is a proof by induction of the theorem being discussed. I have not polished this presentation so there may well be a more elegant proof. Also beware of typos, there are undoubtedly a few.

    Theorem: Let with for all i=1,2,...n for some natural number n. Suppose that
    . Then



    and equality holds if and only if

    Proof

    a) If n=1 the theorem is obvious

    b) Suppose that n=2

    so

    Hence



    Now let for . Then and if and only if . From this and inspection of it follows immediately that has a minimum at 1 and .

    This proves the theorem in the case n=2.

    c) Now assume inductively that the theorem is true for all for some

    Then we have as our hypothesis for the theorem that

    .

    Without loss of generality we may assume (re-ording the if necessary) that



    By the inductive hypothesis, treating as a single term



    which becomes




    Consider now the function for and . We claim that with equality if and only if

    The claim follows from observing that ,

    and the theorem follows as well.

    QED

    Edit: 1) A simpler proof of the case n=2 follows from the observation that the statement is equivalent to the statement that which is clear for

    2) The case n=2 is not really needed in the step c) and one can dispense with it, simply assuming then that
    Reply With Quote  
     

  40. #39  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Absolutely never would have gotten that. I was nowhere close.

    For I said




    which is obviously true.

    I guess that's closer to what you had in your edit.

    So now I won't waste any more time on trying to do that, and I've learned a new trick for proofs involving or type requirements: use derivatives.
    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  41. #40  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,607
    Fair enough, but just for the masochism of being publicly humiliated, I will post what I thought was a "proof".

    Base case is . Notice first that for any then can only be true when .

    Since , then for any that . Moreover, for any there is nothing to prove, since then by necessity.

    So consider that . Again, and

    But if obviously , so clearly from the above.

    Base case "proved".

    Assume that . Here we must assume that,either each is one - to- one paired with its inverse, or that mutual inverses can be found by factoring as appropriate (recalling that is arbitrary). Call this sum as .

    Then the case for is trivial - if and , then .

    Consider the case of . Since this product must be unity, from the base case we must have that , then
    Reply With Quote  
     

  42. #41  
    Forum Isotope
    Join Date
    Feb 2009
    Location
    Transient
    Posts
    2,914
    I made it as far as getting the base case of 2 down, couldn't get a handle on the induction part.
    Wise men speak because they have something to say; Fools, because they have to say something.
    -Plato

    Reply With Quote  
     

  43. #42 Re: A Solution 
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,526
    Wow.

    Followed some of it.

    Quote Originally Posted by DrRocket

    By the inductive hypothesis, treating as a single term


    Couldn't understand how you're allowed to do this. How can the product of those two be used in a sum?

    Is this a silly question?
    Reply With Quote  
     

  44. #43 Re: A Solution 
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote Originally Posted by sunshinewarrior
    Wow.

    Followed some of it.

    Quote Originally Posted by DrRocket

    By the inductive hypothesis, treating as a single term


    Couldn't understand how you're allowed to do this. How can the product of those two be used in a sum?

    Is this a silly question?
    It is simply treated as a single term, reducing the number of terms being considered to k which is covered by the inductive hypothesis.

    What allows me to do it is the associative property of multiplication.
    Reply With Quote  
     

  45. #44 Re: A Solution 
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,526
    Quote Originally Posted by DrRocket
    Quote Originally Posted by sunshinewarrior
    Wow.

    Followed some of it.

    Quote Originally Posted by DrRocket

    By the inductive hypothesis, treating as a single term


    Couldn't understand how you're allowed to do this. How can the product of those two be used in a sum?

    Is this a silly question?
    It is simply treated as a single term, reducing the number of terms being considered to k which is covered by the inductive hypothesis.

    What allows me to do it is the associative property of multiplication.
    I think I've got it. But it's at the limit of my capacities, alas.

    Thanks ever so much for that.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •