Thread: help with induction

Check me on this; I think it's pretty straightforward (maybe someone already posted this proof):

Show 14 is the least m such that for all n >= m, there are j and k such that n = 3j+8k.

First, show there is no m < 14 such that for all n >= m, there are j and k such that n = 3j+8k.

Try every m less than 14, finding the least n >= m such that there are no j and k such that n = 3j+8k. To prove, for each m < 14 and for its selected n, that there are no j and k such that n = 3j+8k, just try all j and k less than n (since j and k would have to be less than n in order for n = 3j+8k to hold).

Show for all n >= 14, there are j and k such that n = 3j+8k.

First we show it for n is even.

By weak induction on r, it's easy to show: If r > 3 then there is a q such that 2r = 2q+8.

Then, by strong induction on r, show: If r > 7, then there are j and k such that 2r = 3j+8k, as follows:

For the stong induction hypothesis, suppose for all q such that 7 < q < r, we have there are j and k such that 2q = 3j+8k.

Now for some q, let 2r = 2q + 8. So q < r. And, since r > 7, we have q > 2. Now if q is in {3, 4, 5, 6, 7} then it's easy to verify that, for each case, there are j and k such that 2r = 3j+8k. So suppose 7 < q. So let 2q = 3j+8k. So 2r = 3j+8(k+1).

So, for n is even, we're done.

Now, suppose n is odd. Checking n = 15 and n = 17 is easy. So, suppose n > 17.

By weak induction on n, it is easy to show that for every n such that n is odd and n > 17, there is an r such that n = 2r+3.

So for some j and k, we have n = 2r+3 = 3(j+1)+8K.

if i want to generalize it would this make sense?

∃m∈ℕ and ∀n∈ℕ s.t n>=m ∃g∈ℕ,∀j∈ℕ,∃h∈ℕ,∀k∈ℕ gj+hk=n

The problem is (and assume as "built in" that all quantifiers are relativized to the set of natural numbers N):

Find the m such that

An(if n >= m then Ejk n=3j+8k)
& Ap(if p < m then it is not the case that An(if n >= p then Ejk n=3j+8k))

and prove it for your choice of m.

I did a proof in my latest post.

pretty straight-forward, eh? by the time one is finished, one has the feeling that SOMETHING has been proved, but how it relates to the original problem is lost amongs r's,q's,j's and k's.

and the 2 cases of the OP's proof have been subsumed in a bewildering array of two main cases and 5 sub-cases to check in the strong induction of r, for the case when n is even, the proof of which you have omitted as "easy to verify", and a further two cases sub-cases for n odd which are again, "left to the reader to verify".

it's like hitting a fly with a sledge-hammer. it works, but it's kinda hard on the counter-top.

as i remarked before, it's sufficient to prove that n = 13 has no solution (we can't have an inductive set that "skips an integer"). and one need not check EVERY j,k < 13,

verifying that k = 0 or 1 will not work is all you need to do (yes, 16 is bigger than 13, so any positive integer added to 16 will never equal 13).

@bryangoodrich, yes, thinking in terms of mod 3 and mod 8 is the simplest conceptual way to go.

Originally Posted by Deveno

pretty straight-forward, eh?

Yes, pretty straightforward. Dump your saracasm, wouldya?

Originally Posted by Deveno

by the time one is finished, one has the feeling that SOMETHING has been proved,

Not just "SOMETHING", but the original problem.

Originally Posted by Deveno

but how it relates to the original problem is lost amongs r's,q's,j's and k's.

No, it's not. It's made explicitly clear.

Originally Posted by Deveno

and the 2 cases of the OP's proof have been subsumed in a bewildering array

Nothing bewilidering. Each step follows logically.

Originally Posted by Deveno

of two main cases and 5 sub-cases to check in the strong induction of r, for the case when n is even, the proof of which you have omitted as "easy to verify",

Because it IS easy to verify. It's routine to verify it. A proof doesn't have to mention every easy detail that a reader can routinely check for himself.

Originally Posted by Deveno

and a further two cases sub-cases for n odd which are again, "left to the reader to verify".

Yes, because it is indeed easy enough to verify.

Originally Posted by Deveno

it's like hitting a fly with a sledge-hammer. it works, but it's kinda hard on the counter-top.

So, you do understand that it works. I do not claim it is the most simple proof. I claim only that it is a proof. And it follows a simple observation that motivates the proof, which is that for even numbers great enough, they're all x+8 for some even x and for odd numbers great enough, they're all x+3 for some even x. The rest of the proof is in showing that fact and some other matters that are needed to make the whole thing airtight.

If you feel another proof is more simple or elegant, then fine, but drop your condescending sarcasm.

your motivating observation is simple enough. but i point out that one need not establish n = 3j+8k for n = 2r for r = 2q+8 and r > 7 and q > 7 (plus q in {3,4,5,6,7}),

and then for n = 15, n = 17, and n = 2r + 3 with r > 7. if my counting skills serve me right, that requires establishing 7 manual verifications:

n = 14, 15, 16, 17, 18, 20 and 22 which seems like an extraordinary amount of "base cases" to verify for an inductive proof.

i contrast this with establishing the base cases of 14,15 and 16 (and then adding 3 to each), or in the OP's proof,

the three cases k = 0, k = 1, or k > 1 (along with the proviso n ≥ 14).

perhaps it is just me, but i don't find your proof straight-forward at all. to verify it is indeed "air-tight", i have to verify we have enough "even numbers" to start with:

that is, we need n, n+2, n+4, n+6, n+8 to get every even number than n. i have to find the values for j,k myself, which isn't terribly difficult,

but it does interrupt the flow of the proof. and if i were a professor reading this proof (perhaps as some homework assignment), i would probably mark off

some for "unsupported assumptions". yes, we CAN find j,k such that 14,16,18,20 and 22 can be written as 3j+8k for some j,k, but that's part of what one is supposed

to be proving. you might as well say: "for every n > 13, we can obviously write n = 3j + 8k for non-negative j,k."

it's not just a matter of elegance or simplicity. it's a matter of clarity. when i read your proof, it was not immediately obvious, what you were saying is true,

some reflection was required. it was confusing. in one line you take as an assumption "all 7 < q < r",

and then in the next line you talk about q in {3, 4, 5, 6, 7}, leaving one to wonder how you can assume q > 7 on one hand, and q = 3, on the other.

that kind of tangled variable reference ought to be avoided in a proof, it muddies the clarity of your argument.

another example: you say "By weak induction on r, it's easy to show: If r > 3 then there is a q such that 2r = 2q+8".

you omit certain vital facts about q. i can infer that what you meant was:

if r is an integer greater than 3, then there is a POSITIVE integer q such that 2r = 2q+8. but as you have written your statement,

it's true for ANY integer r (or real number, even), so it's not CLEAR why you stipulate r > 3. and that, is what i mean by:

"not straight-forward". i shouldn't have to make your qualifying assumptions for you, when i read a proof, rather YOU should make them for ME.

formalism in a proof is helpful, insofar as it removes ambiguity. but i humbly submit the point of a proof, is to communicate an idea.

presumably, the idea is one which you already have clear in your mind, and you intend to make it so to me.

now, your original idea: prove that if we have enough even numbers and odd numbers to start with, we can get every succeeding number, is a good one

(it involves succession, and so is amenable to an inductive proof). and again, you recognize we need "every third odd number" to get them all,

so we need to start off with 2 successive odd numbers (and 15 and 17 are the first 2 we get, because 13 doesn't work).

and i believe what you are trying to do is formalize the idea that if we have 8 consecutive odd numbers (actually we only need 6, but that's OK, it doesn't hurt to start with an extra),

we can continue to get every even number after that. and that's a valid approach. there are several ways to "solve" a problem like this,

and any one which is logically valid will do. it's not your idea i'm quibbling with...it's the expostion. the double use of q with different ranges,

and the "passing of the active variable" n--> r (via n = 2r) --> q (via 2r = 2q+8) makes your proof harder to read, than any other i've seen posted in this topic.

another thing: your induction hypothesis is: 7 < q < r, shouldn't it be 7 ≤ q < r? i mean, after all, we do want to show, in the end that 14 works, right?

it's not sarcasm...i honestly believe your proof hides the simplicity of the problem, and indeed, of your underlying method.

a case in point: at one point you say "By weak induction on r, it's easy to show: If r > 3 then there is a q such that 2r = 2q+8."

think about that for a second. you are asking the reader to supply an inductive proof, which is then a lemma in YOUR proof.

why, should i as the reader, be asked to prove part of your proof, when you are the one trying to prove something? again,

from a pedagogical point of view, that would lose marks right there. yes, it's an easy proof, since 8 = 0 + 8.

might it not be better to say simply: if m ≥ 4, then 2m ≥ 8, so 2m can be written as 2m = 2q + 8 for q ≥ 0?

and also wouldn't it be preferrable to take as our induction hypothesis: for all 7 ≤ r < m,

2r can be written as a sum 3j+8k? since we can prove (explicitly) that we can do so for r = 7, 8, 9, and 10,

we can assume without loss of generality m ≥ 12, so that m > q ≥ 7 (since 2m = 2q+8 from above (m > 7 certainly imples m ≥ 4),

so it satisfies the induction hypothesis, whence the result (insert remainder of your proof here). THAT is what i am talking about, keeping the various

variables straight (and even this is, in my view, overly complicated).

Originally Posted by Deveno

@bryangoodrich, yes, thinking in terms of mod 3 and mod 8 is the simplest conceptual way to go.

I thought about it for like, maybe, five minutes last night and gave up. It can be a bit of a pain. Then today I remembered discussing an algorithm with someone a few weeks ago that involved a difference in parity (in this case, even and odds). Since the coefficients on j and k (as our notation has been so far) have been 3 and 8, these allow us in some fashion to represent every even and odd number for n > 13. If we go the modulo route, I think we can simplify it even further. Why? Because . Instead of we can find a way to write it in terms of . I haven't worked out the details, but I've just been letting my intuition guide me, and played around with some computations in R. Once I find a definitive answer (or see someone else grasp it), I'll be back.

Originally Posted by Deveno

your motivating observation is simple enough. but i point out [...]

I don't mind suggested simplifications. But the proof is still straightforward even if there are more elegant proofs. It doesn't involve any advanced notions in mathematics; all that is involved are checking some grammar school additions and then mathematical induction. As to the number of "base cases", again I don't claim elegance. Indeed, I was going to use the phrase "brute force" a couple of times in the proof, but I took it out because it's not needed to mention that I'm using "brute force" since it is obvious enough that I am.

Originally Posted by Deveno

if i were a professor reading this proof (perhaps as some homework assignment), i would probably mark off

Mark off for what? Lack of elegance? Then you have to give elegance as a grading criterion. If I were grading proofs, I would grade solely on whether the proof is correct and supplies reasonable detail. I wouldn't mark for elegance unless elegance were STATED as a criterion.

Originally Posted by Deveno

"unsupported assumptions". yes, we CAN find j,k such that 14,16,18,20 and 22 can be written as 3j+8k for some j,k, but that's part of what one is supposed to be proving.

Oh, come on, those have simple, finite verifications in grammar school addition. In a proof for grown up readers it's not needed to belabor such matters.

you might as well say: "for every n > 13, we can obviously write n = 3j + 8k for non-negative j,k."

No, I can't just say that. It requires proving.

it's not just a matter of elegance or simplicity. it's a matter of clarity. when i read your proof, it was not immediately obvious, what you were saying is true,

Then you weren't reading carefully at all. At every line I stated what assumption I was making, then I stepped through to conclusions from those assumptions. Then the assumptions are dischaged in the obvious way.

in one line you take as an assumption "all 7 < q < r",

and then in the next line you talk about q in {3, 4, 5, 6, 7}, leaving one to wonder how you can assume q > 7 on one hand, and q = 3, on the other.

No, you misparaphrased.

I wrote:

"For the stong induction hypothesis, suppose for all q such that 7 < q < r, we have there are j and k such that 2q = 3j+8k.

Now for some q, let 2r = 2q + 8. So q < r. And, since r > 7, we have q > 2. Now if q is in {3, 4, 5, 6, 7}"

I didn't assume "all 7 < q < r". That doesn't make sense standalone in this context. What I ACTUALLY said is:

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

That is the strong induction HYPOTHESIS.

Also, we have from previous work that for SOME q we have 2r = 2q + 8.

Then, also, I narrowed down to what happens if that q is in {3, 4, 5, 6, 7}.

The method is perfectly clear. First I have a strong induction hypothesis that is a universal generalization on q (for all q, if 7 < q < r then we have that there are j and k such that 2q = 3j+8k). And I have an existential generalization q (there is a q such that 2r = 2q + 8.) Then I grabbed that q, took cases on it, and applied the earlier universal generalization on it too. Perfectly legal and clear.

that kind of tangled variable reference ought to be avoided in a proof, it muddies the clarity of your argument.

No, it was clear, and economical use of variables. For all q, blah blah holds. And there is some q such that glab glab holds. Consider some q such that glab glab holds. Now infer about it with the fact that both blah blah and glab glab holds for it.

you say "By weak induction on r, it's easy to show: If r > 3 then there is a q such that 2r = 2q+8you omit certain vital facts about q.

No, I didn't omit any vital facts about q. All I need there is exactly what I said: If r > 3 then there is a q such that 2r = 2q+8. Yes, I ommitted belaboring the weak induction that allows me to infer that if r > 3 then there is a q such that 2r = 2q+8, but that is because the induction there is quite routine.

you omit certain vital facts about q. i can infer that what you meant was:

it's true for ANY integer r (or real number, even)

Oh, come on, from all the previous discussion and from the context of the proof, one can easily allow that I'm talking about natural numbers. But one doesn't even have to allow it, since I STATED I'm doing "induction on r", so OF COURSE r is a natural number. As grown ups, in such context, we don't pick on such nits as "you didn't say you're only working with natural numbers" when the context is clear enough that we are and when one says ANYWAY in such a context "INDUCTION ON".

any other i've seen posted in this topic.

Would you please tell me specifically what post you consider to be an elegant, more or less self contained, and sufficiently detailed proof that 14 is the desired number?

at one point you say "By weak induction on r, it's easy to show: If r > 3 then there is a q such that 2r = 2q+8."

think about that for a second. you are asking the reader to supply an inductive proof, which is then a lemma in YOUR proof.

How about you think for a second that mathematical proofs OFTEN mention things like "it's easy to see" or "the verification is routine" et. al when indeed it's quite easy to whip out a trivial bit of reasoning like the quite easy weak induction I'm referring to there.

why, should i as the reader, be asked to prove part of your proof, when you are the one trying to prove something?

Because you can flash it through your head, or jot it quick on paper just about as fast it would take you to read it already typed out for you. Are you serious? You don't see that it's utterly common in mathematics that authors or givers of notes leave some too obvious steps with remarks such as "the weak induction here is routine"?

Look, do you have the slightest difficulty seeing how routine the weak inductions are? If not, then it's captious of you to make an issue of it.

from a pedagogical point of view,

I don't claim to provide sparkling pedagogy. My point was merely to show that there is indeed a proof that 14 is the number and to use induction (and using both kinds) to do it.

/

Originally Posted by Deveno

it's not sarcasm

That denial makes it worse, given that your tone definitely was sarcastic: "pretty straight-forward, eh?" along with you striving to be arch with "by the time one is finished, one has the feeling that SOMETHING has been proved," which sounds like some affectation you got from reading too many hack movie reviews: "By the time the credits roll, one has the feeling that there was some point or another in the making of this film..."

Originally Posted by Deveno

it's sufficient to prove that n = 13 has no solution (we can't have an inductive set that "skips an integer")

That's fine, and does simplify the first part of my proof. Except that there is no need to mention any induction there.

As a point of information now, what specific post is claimed to be an elegant, reasonably standalone, straightforward, and sufficiently detailed proof that 14 is the number?

To add to my previous comment, I was thinking about how we can think of this new set (n > 13 with n = 3j + 8k) in terms of algebra. Here we can redefine everything in terms of J and K where J 'absorbs' all those multiples of 3 and K 'absorbs' all those multiples of 8.

0 = 2J + K
1 = 3J - K
2 = K - 2J
3 = J
4 = 2 + 2 = 2K - 4J
5 = 2 + 3 = K - J
6 = 2J
7 = 5 + 2 = 2K - 3J (= 5J - K)
8 = K
9 = 3J

and so on. The only three that really needed defining were 0, 1, and 2 (Why?). What I errored in my original proof was thinking I can define a unit change on this new "number line," and while that may be possible, I certainly didn't do it. What I have just shown above is how to treat 14 as 0 and then define every number distant from 0. Thus, 15 = 14 + 1 = 0 + 1 = 1 in this expression. Also, 16 = 14 + 2 = 0 + 2 = 2 in this expression. Substitute 3 for J and 8 for K and notice the changes to j and k that occur. They match up with their respective numbers appropriately. Only 1 and 2 need defining. Everything else is then defined in terms of those 1 and 2 (not necessarily unique, see 7). This gives us a way of expressing every number meeting the requirement for my set A in a much easier format.

I haven't thought beyond this, so I don't know how it helps the proof by induction. I was merely trying to find another way of viewing the problem that could prove much more direct.

I don't mean to hector, but, aside from my proof, do we have an elegant, reasonably standalone, straightforward, and sufficiently detailed proof that 14 is the number? If so but it hasn't yet been posted with all the parts together, would someone please post it?

Originally Posted by MoeBlee

I don't mean to hector, but, aside from my proof, do we have an elegant, reasonably standalone, straightforward, and sufficiently detailed proof that 14 is the number? If so but it hasn't yet been posted with all the parts together, would someone please post it?

That 14 is the first number? That requires two things (1) that 13 cannot be represented as n = 3j + 8k, and (2) that the set consisting of all such n is inductive. (2) is the crux of the issue since (1) is direct. You cannot prove it otherwise, because to say 14 is the first requires us to know that we don't skip an integer out beyond 14. That is the point of induction.

Originally Posted by bryangoodrich

That 14 is the first number?

No, I'm not asking just about 14 being least. That's the trivial part. As we agreee, it's easy to see that there is no m < 14 such that for all n >= m, there are j and k such that n = 3j+8k. So I'm asking: What proof (other than mine) is on the table that shows that for all n >= 14, there are j and k such that n = 3j+8k?

Originally Posted by bryangoodrich

That 14 is the first number? That requires two things (1) that 13 cannot be represented as n = 3j + 8k, and (2) that the set consisting of all such n is inductive.

Maybe I'm not reading you right, because there's no induction needed for the leastness part.

By trivial argument we can see that there is no j and k such that 13=3j+8k. So no number less than 14 can be our winner, and there's no induction needed for that part. The rest of the proof is to show that for all n >= 14 there are j and k such that n = 3j+8k, and that is where induction comes in.