Page 4 of 4 FirstFirst 1234
Results 46 to 59 of 59

Math Help - help with induction

  1. #46
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165
    You forget MoeBlee, that we don't know if some number 10^{10^{10}} might not be an n such that n = 3j + 8k. That is the point of induction. Therefore, while it is necessary for 13 to fail to be such an n, that is not sufficient. By showing that every other n > 13 can be expressed as n = 3j + 8k, we show sufficiency.
    Follow Math Help Forum on Facebook and Google+

  2. #47
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,370
    Thanks
    739
    i claim a necessary and sufficient condition for the set

    A = {m in N: m = 3j+8k, with j,k in N}

    to be inductive, is it contain 3 consecutive integers: and that the desired n of the original problem is, in this case (that is, when A is inductive): min(A) = 14.

    sufficiency should be clear: if A is inductive, it must contain 3 consecutive integers.

    the necessity is the tough part: if A contains 3 consecutive integers, r, r+1, and r+2, so that:

    r = 3j+8k
    r+1 = 3j'+8k'
    r+2 = 3j"+8k",

    then A contains r+q for any non-negative integer q. why? because any integer (not just non-negative ones) can be written either as q = 3s, 3s+1, or 3s+2.

    case 1) r+q = r+3s --> r+q = 3(s+j) + 8k
    case 2) r+q = r+(3s+1) --> r+q = (r+1)+3s = 3(s+j') + 8k'
    case 3) r+q = r+(3s+2) --> r+q = (r+2)+3s = 3(s+j") + 8k".

    so it remains to be shown that min(A) = 14.

    14 = 3(2) + 8(1)
    15 = 3(5) + 8(0)
    16 = 3(0) + 8(2) so these 3 consecutive integers are in A.

    13 = 3j+8k --> k < 2 (since for k ≥ 2, j ≥ 0 3j + 8k ≥ 16 > 13).
    13 = 3j + 8 --> 5 = 3j, no integer solution, since 3 does not divide 5.
    13 = 3j, no integer solution since 3 does not divide 13.

    thus 13 is not in A, but 14 is. so min(A) = 14, when A is inductive.

    one can, and some may prefer to, use strong induction on cases 1-3 above to show that r in A reduces to either 14,15 or 16 in A.

    *****

    in response to MoeBlee:

    in all fairness, it's hard to know what level of detail is required here. to me, at an informal level, a proof is as follows: we can't make 13, we can make 14,15 and 16. just add 3-cent stamps to one of those numbers, and you can get any bigger integer you like. any formalism beyond that, is just "mathese" for the...an appropriate term might get me infracted, so i will just say..."purists". the original problem is stated in "lay terms", honestly, there's a lot of over-thinking going on.

    the orginal poster made a perfectly good argument in his first go, i merely pointed out he left a "gap", in that he had two cases: and he did not show that after applying one of them, he would always still have case 1 or case 2 (in case 2, he could always subsequently apply case 1, but in case 1, he did not adequately show that either case 1 or case 2 MUST apply. he remedied that adequately in a later post).

    i think you are confusing elegance with clarity. while from a purely aesthetic standpoint, elegance might be preferrable, it's not necessary. your argument isn't very clear. it makes sense, once it's unravelled, but it places more of a demand on the reader than Sneaky's does. i stand by my original assessment, i don't find it straight-forward. it's not so dense as to be unintelligible, it's just not straight-forward.

    by your own admission, you make an existential and universal quantification on the same variable, q. understanding WHY this is permissible (and not logically indefensible) makes QUITE a demand on a reader, especially for an induction proof, which are often quite elementary in nature. in reading your proof for the first time, i had to go back and tell myself: "oh, he doesn't mean the same q in the same way HERE, as he does THERE".

    you also seem to be reacting to this quite personally. the fact is, i don't know you, and i certainly don't have any feelings about you one way or the other. if i had to guess, i'd say you probably have a better command of logic and proof than i do (i am rusty, and out of practice, and have forgotten most of what i once knew).
    Follow Math Help Forum on Facebook and Google+

  3. #48
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by bryangoodrich View Post
    You forget MoeBlee, that we don't know if some number 10^{10^{10}} might not be an n such that n = 3j + 8k. That is the point of induction. Therefore, while it is necessary for 13 to fail to be such an n, that is not sufficient. By showing that every other n > 13 can be expressed as n = 3j + 8k, we show sufficiency.
    No, I don't forget what you mention. Indeed my own proof performs the needed induction.

    I think we agree that there are two parts to this proof:

    (1) Show there is no number less than 14 that works. (That 13 is not a sum of 3's and 8's suffices for that.)

    (2) Show that 14 works.

    My point last was just that (1) doesn't need induction.

    If your earlier marks were not meant to suggest that (1) needs induction, then very well.
    Last edited by MoeBlee; May 26th 2011 at 06:39 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #49
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    I'll start with your closing remark, then in sequence after that:

    Quote Originally Posted by Deveno View Post
    if i had to guess, i'd say you probably have a better command of logic and proof than i do (i am rusty, and out of practice, and have forgotten most of what i once knew).
    I am not brooding for a fight. And I respect your knowledge; almost surely, you know more about mathematics in general than I do.

    i think you are confusing elegance with clarity.
    No, I am not. I said MYSELF that there may be more elegant proofs. But my proof is clear.

    your argument isn't very clear.
    It's quite clear.

    it makes sense, once it's unravelled,
    It makes sense at each step.

    but it places more of a demand on the reader than Sneaky's does.
    I don't opine on that comparison. Of course my proof requires that one read it carefully, line by line, and with some understanding of certain modes of common mathematical reasoning.

    Also, what exactly do you point to as Sneaky's proof?

    by your own admission, you make an existential and universal quantification on the same variable, q.
    It's hardly an "admission". There is nothing wrong with such quantification; indeed it is deft in this case.

    understanding WHY this is permissible (and not logically indefensible) makes QUITE a demand on a reader,
    It requires the reader to understand an argument of the form:

    Suppose, for all q, Pq -> Rq.
    It was earlier established that there is a q such that Sq.
    So let Sq.
    From Sq, Pq -> Rq, and other information, we show T.
    So, if (for all q, Pq -> Rq) then T.

    especially for an induction proof, which are often quite elementary in nature.
    Inductions can be simple or extremely complicated. And the induction I did there was only a few lines.

    in reading your proof for the first time, i had to go back and tell myself: "oh, he doesn't mean the same q in the same way HERE, as he does THERE".
    All you had to do is read the proof carefully exactly as I wrote it. I explicity included the quantifiers "for all q" and "for some q". The reasoning itself (aside from the details of the arithmetic) is as basic as I just mentioned above.

    you also seem to be reacting to this quite personally.
    I love it when someone is snide then when called on it says, "Oh, why do you have to take it personally?" I called you on your being snide. That's all.

    the fact is, i don't know you, and i certainly don't have any feelings about you one way or the other.
    And vice versa. And I didn't conclude that you had much feeling about it; I just called your snideness, that's all, whether you have any feeling in it or not was not my real concern.

    And please go to the top of this post, back to your own closing remark, which I appreciate, and my response again.
    Last edited by MoeBlee; May 26th 2011 at 07:34 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #50
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,370
    Thanks
    739
    if nothing else, i must commend you for an extraordinarily well-thought-out and carefully reasoned self-defense. i suppose i may have come off as condescending in my original response. honor dictates i apologize, and do so forthwith.
    Follow Math Help Forum on Facebook and Google+

  6. #51
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Deveno View Post
    if nothing else, i must commend you for an extraordinarily well-thought-out and carefully reasoned self-defense. i suppose i may have come off as condescending in my original response. honor dictates i apologize, and do so forthwith.
    "extraordinarily well-thought-out and carefully reasoned self-defense" seems damning by faint and (perhaps?) ironic praise, but thank you anyway. But in case you thought I was asking for an apology (I don't know whether you thought that or not), just for the record, I was not seeking an apology nor do I think one was dictated, by honor or by anything else.
    Follow Math Help Forum on Facebook and Google+

  7. #52
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    I see that your argument is to show that a certain set is inductive, but where do you use both weak and strong inductions themselves to do that? What are your weak and strong hypotheses?
    Follow Math Help Forum on Facebook and Google+

  8. #53
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,370
    Thanks
    739
    Quote Originally Posted by MoeBlee View Post
    "extraordinarily well-thought-out and carefully reasoned self-defense" seems damning by faint and (perhaps?) ironic praise, but thank you anyway. But in case you thought I was asking for an apology (I don't know whether you thought that or not), just for the record, I was not seeking an apology nor do I think one was dictated, by honor or by anything else.
    my sense of what it is i should, or should not do, is by and large, internal. i see those people who do what they do because it is expected of them, as weak-willed.
    Follow Math Help Forum on Facebook and Google+

  9. #54
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Deveno View Post
    my sense of what it is i should, or should not do, is by and large, internal. i see those people who do what they do because it is expected of them, as weak-willed.
    You're not a subscriber to the philosophy of Ayn Rand, are you?
    Follow Math Help Forum on Facebook and Google+

  10. #55
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,370
    Thanks
    739
    Quote Originally Posted by MoeBlee View Post
    I see that your argument is to show that a certain set is inductive, but where do you use both weak and strong inductions themselves to do that? What are your weak and strong hypotheses?
    my argument, strictly speaking, is not inductive. if i were to "make it inductive" the logical candidate is strong induction on s, in which case it would be preferable to use 3s-1, instead of 3s+2, so that my induction hypotheses would be:

    "for all 5 ≤ r < s, 3r+m (m=-1,0 or 1) can be written as 3r+m = 3k+8j for non-negative integers j,k". then 3s+m = 3(s-1)+m+3 = 3j+8k+3 = 3(j+1)+8k.

    when r = 5, 14,15 and 16 can clearly be written as such a sum.
    Follow Math Help Forum on Facebook and Google+

  11. #56
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Deveno View Post
    my induction hypotheses would be:

    "for all 5 ≤ r < s, 3r+m (m=-1,0 or 1) can be written as 3r+m = 3k+8j for non-negative integers j,k". then 3s+m = 3(s-1)+m+3 = 3j+8k+3 = 3(j+1)+8k.

    when r = 5, 14,15 and 16 can clearly be written as such a sum.
    And my induction hypothesis was:

    suppose for all q such that 7 < q < r, there are j and k such that 2q = 3j+8k.

    My argument was complicated then by tying up certain details. And your argument too becomes more complicated if you are to attend to those kinds of details. I haven't checked through your argument, but if it all checks out, then I think it might be more streamlined than mine. But my original argument, delivered "on time for the assignment" ;-), is also correct, clear and not egregiously baroque even if not ideally elegant.
    Follow Math Help Forum on Facebook and Google+

  12. #57
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,370
    Thanks
    739
    some elements of Objectivism (or w/e the worshippers of Rand call it) appeal to me, but it only seems workable in a utopian society. people are often irrational, and think short-term, which leads to less than optimal results.

    what else can i say? i originally found your argument confusing. is that just me? i don't know, i don't have an independent panel of judges to appeal to. it's possible i was quibbling for the sake of quibbling (sometimes i do that), or that i was in a particularly irritable mood, or various other things. your repsonse that my argument gets complicated by the formalism is valid, too. in fact, i find it most unsatisfactory that in order to be "rigorous" i have to start speaking in arcane terms.

    as a matter of taste, i prefer "high-level expression" to the more "low-level" (but unambiguous) language of logic, particularly first-order logic. as a kind of comparison, it's like the difference between a program written in visual basic, versus a program written in machine-code. both execute the same instruction-set, but the "lower-level" form doesn't seems as clear to me, in terms of how i actually process ideas. that is, i prefer abstraction, to specification. some people take rather more pleasure in "nuts and bolts" types of things than i do. it happens.
    Follow Math Help Forum on Facebook and Google+

  13. #58
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    I am relieved that you're not an Objectivist.

    As to styles of proof, personally, I prefer the highest level proof in which I can still see that the steps do indeed "lock". Depending on my familiarity with the subject matter, that level can range from pretty high to fairly low. I think it depends always on the particular reader, as some readers may need more detail or less detail for them to see the "locking" of the steps.
    Follow Math Help Forum on Facebook and Google+

  14. #59
    Senior Member
    Joined
    Sep 2009
    Posts
    299
    Some one told me that given two variables i,j in N^+, one can calculate the m value, using this:
    m=(i-1)(j-1) iff the greatest common denominator of i and j is 1. If the GCD is not 1, then m does not exist.
    And it works, finally I know how to get m.
    Follow Math Help Forum on Facebook and Google+

Page 4 of 4 FirstFirst 1234

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2010, 02:08 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 19th 2008, 05:12 PM

Search Tags


/mathhelpforum @mathhelpforum