Thread: help with induction

You forget MoeBlee, that we don't know if some number 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.

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

Originally Posted by bryangoodrich

You forget MoeBlee, that we don't know if some number 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.

I'll start with your closing remark, then in sequence after that:

Originally Posted by Deveno

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.

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.

Originally Posted by Deveno

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.

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?

Originally Posted by MoeBlee

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

Originally Posted by Deveno

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?

Originally Posted by MoeBlee

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.

Originally Posted by Deveno

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.

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.

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.

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.