# Math Help - help with induction

1. Originally Posted by Deveno
suppose we could make 3 consecutive integers in such a fashion: m, m+1, and m+2. adding a 3-cent stamp to each configuration would then give m+3,m+4,and m+5.

can you see that we can use induction to show we can make all integers ≥ m this way?

what are the smallest 3 consecutive integers we can make?
is it 14, 15, 16?

2. prove it.

3. so there are 2 ways of proving it, the simple induction method and complete induction, i think i proved it in post #15 using simple induction, is it right though?

4. there are some holes in your proof.

first off, when you take the first case, where the number of 8-cents stamps is non-zero, you show you can get to the next integer, by replacing the 8-cent stamp with 3 3-cent stamps. so far, so good.

next, you show that if you have no 8-cent stamps, but you have at least 5 3-cent stamps, you can replace those 5 with 2 8-cent stamps. great.

however, you have not shown that after that step, you will have either 5 3-cents stamps, or an 8-cent stamp remaining (so you can repeat the process inductively).

that is, you need to show that in case 1) after you replace the 8-cent stamp with 3 3-cent stamps, you have either a) an 8-cent stamp, or b) 5 3-cent stamps. this is important (this situation actually occurs when n=14, we take away the only 8-cent stamp, and just barely get enough 3-cent stamps to apply case 2) in order to continue).

clearly, we're ok in case 2) as we always have an 8-cent stamp to work with after we're finished.

however, you still have not shown that 14 is the minimum number that works. you've just shown (almost) that every number greater than 14 can be made this way. you need to add that 3j+8k = 13 has no positive integer solutions (this is not hard, but it is a necessary part of the problem. clearly k has to be 0, or 1 (why?), so this amounts to showing that neither 13 nor 5 is divisible by 3).

5. while i try to fix these problems, i just want to know if my process to determine 14 is correct? Is it ok to get the m value like that? or is there a formula to generate 14? (another example is with using 7 and 4, the m for this is 18)

6. i don't know how to prove:

that is, you need to show that in case 1) after you replace the 8-cent stamp with 3 3-cent stamps, you have either a) an 8-cent stamp, or b) 5 3-cent stamps. this is important (this situation actually occurs when n=14, we take away the only 8-cent stamp, and just barely get enough 3-cent stamps to apply case 2) in order to continue).

so in case 1: after making the switch, it should have 1 8-cent stamp, or 5 3-cent stamps. if i'm removing an 8, and putting 3 3's, then there should of been at least 2 3's. or 2 8's before the switch.

7. what you want to rule out is the following possibility:

you apply case 1) and are left with no 8-cent stamps, and only 4 (or less) 3-cent stamps.

but that would mean you started with only 11 cents (in all) of stamps, and therefore....

8. Is this acceptable?

Well for the case u have k>0, since I am removing a k, and adding 3 j's, I don't need to show anything here before the switch.

For the case k=0, I am removing 5 j's and adding 2 k's, so here before the switch I need to show there are at least 5 j's.

3j+0k≥14 [since k=0]
3j≥14 [since k=0]

The only way to make this possible is if 3(j) >= 14 by induction hypothesis

j≥5 [to get at least 14¢]
Therefore if k=0, there will always be at least 5x3¢ stamps.

Is this reasoning oK?

9. Originally Posted by Sneaky
Find the smallest number m such that postage of exactly n cents can be made using only 3-cent and 8-cent stamps for all n>=m. Prove your claim using simple and complete induction.

If n is the amount of cents made from the two stamps, wouldn't the smallest m be 0 for all n?
Well, I'm jumping into this conversation late, but it took me a little bit of computation to see what the question is asking. I ran an R simulation (easy double for loops and spit out the test sequence in order by output) and it looks like after 13 (not inclusive), every n can be written in terms of 3j + 8k. Thus, m = 14. Now, to prove this by induction we need to do two things: (1) Induct on s for P(s) := s = 3j + 8k for some numbers j and k. This is straight-forward use of induction, and can be done by PMI and complete induction. Then, (2) show that 13 cannot be satisfy P(s). You can prove (2) first to say that "m has to be at least greater than 13."

I would do it set-theoretically. Let us define the set:

$A = \{n\ :\ \exists j,k \in N (n = 3\times j + 8\times k)\}$

It should be noted that clearly $n \in N$ since by its specification it is a composition of such numbers. With that aside, we need only prove a minimum number is in A and that A is inductive. Well,

$14 = 3\times 2 + 8\times 1\ \therefore 14\in A$

Now, let us suppose:

$\exists s \in A, s \geq 14$

By the supposition,

$\exists j,k \in N, s = 3j + 8k$

But recognize that we can alter the choices from 's' to derive 's+1' as follows:

$j^* = j+3, k^* = k-1, 3j^* + 8k^* = 3(j + 3) + 8(k - 1) = 3j + 8k + 1 = s + 1$

$\therefore s+1 \in A$

Similar arguments can be made for doing complete induction. One could argue about my definitions of (j+3) and (k-1), but since 14 requires at least k = 1, (k-1) is definable here. Moreover, one should be able to easily point out that 13 cannot be in A. A negative proof would suffice (though, I'd be interested in a direct one).

10. i was just wondering if this was true, i just came up with it and i can't seem to find a counter example, this is a way to get m, using any two numbers.

say the 2 numbers are j, and k, then m is equal to

if jk > 10:
m=jk - 10
else:
m=jk

Is this true?

11. Originally Posted by bryangoodrich
Well, I'm jumping into this conversation late, but it took me a little bit of computation to see what the question is asking. I ran an R simulation (easy double for loops and spit out the test sequence in order by output) and it looks like after 13 (not inclusive), every n can be written in terms of 3j + 8k. Thus, m = 14. Now, to prove this by induction we need to do two things: (1) Induct on s for P(s) := s = 3j + 8k for some numbers j and k. This is straight-forward use of induction, and can be done by PMI and complete induction. Then, (2) show that 13 cannot be satisfy P(s). You can prove (2) first to say that "m has to be at least greater than 13."

I would do it set-theoretically. Let us define the set:

$A = \{n\ :\ \exists j,k \in N (n = 3\times j + 8\times k)\}$

It should be noted that clearly $n \in N$ since by its specification it is a composition of such numbers. With that aside, we need only prove a minimum number is in A and that A is inductive. Well,

$14 = 3\times 2 + 8\times 1\ \therefore 14\in A$

Now, let us suppose:

$\exists s \in A, s \geq 14$

By the supposition,

$\exists j,k \in N, s = 3j + 8k$

But recognize that we can alter the choices from 's' to derive 's+1' as follows:

$j^* = j+3, k^* = k-1, 3j^* + 8k^* = 3(j + 3) + 8(k - 1) = 3j + 8k + 1 = s + 1$

$\therefore s+1 \in A$

Similar arguments can be made for doing complete induction. One could argue about my definitions of (j+3) and (k-1), but since 14 requires at least k = 1, (k-1) is definable here. Moreover, one should be able to easily point out that 13 cannot be in A. A negative proof would suffice (though, I'd be interested in a direct one).
again, i must make the same objection as before, you DO NOT KNOW, and cannot assume, that k > 1. for example, for n = 18, you may have 6 3-cent stamps, and your argument fails. a more pertinent example is n = 15, which can ONLY be made with 5 3-cent stamps, so so using your proof, one finds that you make 16 with 8 3-cent stamps, and a negative 8-cent stamp, which is nonsense.

also, your set A is not adequate to the task. 12 is in A, but 13 is not. so A is not an inductive set.

Sneaky's proof by cases is fine, except: he has to show that after case 1) is applied, we always wind up with a situation where either case 1) is true, or case 2) is true.

this isn't particularly difficult, in case 1), we add 3 3-cent stamps: j-->j* = j+3, and remove 1 8-cent stamp: k-->k* = k-1. however, we must be sure that either:

a) k >1, so that we may apply case 1) again, or:

b) if k = 1, that after applying case 1) we arrive at a situation where we may apply case 2).

suppose n = 3j + 8. subtracting an 8-cent stamp gives us n - 8 = 3j. but n ≥ 14 --> n - 8 ≥ 6 = 3(2)

so if we just have a single 8 cent-stamp, when we remove it, we wind up with all 3-cent stamps left, and the minimum number

we can have left is 2. since in case 1) we add 3 3-cent stamps, the minimum number of 3-cent stamps left after applying

case 1) is 5, so we can safely say we can always apply either case 1) or case 2).

again, this is so much simpler, if we do the following:

instead of doing induction on the total n (= 3j+8k), write:

n = 14 + 3m, n = 15 + 3m, or n = 16 + 3m, and do induction on m, rather than n.

this gives us 3 inductive sets: A = {14 + 3m: m in N}, B = {15 + 3m: m in N}, C = {16 + 3m: m in N}

each of which can be shown rather easily to be inductive (just add another 3-cent stamp).

furthermore, these sets are disjoint, with AUBUC, being the desired consecutive integers greater than 14.

more informally, i looked at this problem like this: first i considered how we might get a difference of 1. and i saw trading an 8-cent stamp for a 3-cent stamp, would increase the total by one. but then i thought: what happens when we run out of 8-cent stamps to trade? or what if we only had 3-cent stamps to begin with (like 9, or 27 or 51 cents)? and then i thought, well, just by adding ONLY 3-cent stamps, we could always get to the next 3rd integer. so if we could just form 3 integers in a row, ANY 3 integers, then by adding a 3-cent stamp to each total, we would get the NEXT 3 integers.

1,2,3: can only make 3
2,3,4: can only make 3
3,4,5: can only make 3
4,5,6: can only make 6
6,7,8: can only make 6 and 8
7,8,9: can only make 8 and 9
8,9,10: can only make 8 and 9
9,10,11: can only make 9 and 11
10,11,12: can only make 11 and 12
11,12,13: can only make 11 and 12
12,13,14: can only make 12 and 14
13,14,15: can only make 14 and 15
14,15,16: bingo! add a 3-cent stamp to each, we can make 17,18,19. add another, we can make 20,21,22. add another....

12. Is there a name for this problem, because I am trying to figure out a way to get m, using i and j (as variables), in other words find out a formula.

@deveno

isn't this fine?

Code:
Is this acceptable?

Well for the case u have k>0, since I am removing a k, and adding 3 j's, I don't need to show anything here before the switch.

For the case k=0, I am removing 5 j's and adding 2 k's, so here before the switch I need to show there are at least 5 j's.

3j+0k≥14 [since k=0]
3j≥14 [since k=0]

The only way to make this possible is if 3(j) >= 14 by induction hypothesis

j≥5 [to get at least 14¢]
Therefore if k=0, there will always be at least 5x3¢ stamps.

Is this reasoning oK?

13. You're right about A not being inductive. I just need to specify 14 as its minimum to correct that, or conclude that it's subset after 14 is inductive. I was also too hasty with my algorithm. I do believe we can do a proof by cases for this to tidy up my proof. Other than that, it should follow the same basic structure.

Might I add, I was thinking about this while I was pulling into my housing complex yesterday (don't ask me why), and I wondered if there might be a way to devise an algorithm in terms of modulo 3 and modulo 8, to generate a sort of equivalence class operation. It would then make dealing with the proof by cases straight forward because there's only so many cases between modulo 3 and modulo 8 we have to deal with. At least notationally, I think it would simplify a lot of it.

For those interested in seeing the simulation of this problem, you can download R and run the following code. Keep in mind that R indexes its vectors started at 1, not 0.
Code:
f = function(j, k) 3*j + 8*k
x = matrix(nrow=100, ncol=3)
for(j in 0:9) for(k in 0:9) x[(10*j + k + 1), ] = c(j, k, f(j, k))
x = data.frame(x)
(x = x[order(x[[3]]), ])

14. Originally Posted by bryangoodrich
You're right about A not being inductive. I just need to specify 14 as its minimum to correct that, or conclude that it's subset after 14 is inductive. I was also too hasty with my algorithm. I do believe we can do a proof by cases for this to tidy up my proof. Other than that, it should follow the same basic structure.

Might I add, I was thinking about this while I was pulling into my housing complex yesterday (don't ask me why), and I wondered if there might be a way to devise an algorithm in terms of modulo 3 and modulo 8, to generate a sort of equivalence class operation. It would then make dealing with the proof by cases straight forward because there's only so many cases between modulo 3 and modulo 8 we have to deal with. At least notationally, I think it would simplify a lot of it.

For those interested in seeing the simulation of this problem, you can download R and run the following code. Keep in mind that R indexes its vectors started at 1, not 0.
Code:
f = function(j, k) 3*j + 8*k
x = matrix(nrow=100, ncol=3)
for(j in 0:9) for(k in 0:9) x[(10*j + k + 1), ] = c(j, k, f(j, k))
x = data.frame(x)
(x = x[order(x[[3]]), ])
Is there a name for this problem, because I am trying to figure out a way to get m, using i and j (as variables), in other words find out a formula.

15. No, sneaky, I don't think there is a name to this problem (or class of problems). I don't understand what you're trying to do, though. You want to have a function of j and k such that f(j, k) = m? I think what you want to do is find an inductive set derived from the specifications (i.e., n = 3j + 8k, in this case), and then find its minimum. The problem is excluding the non-inductive elements that, in my case, satisfy the specification for A. My reply above was just to indicate it as all those after 13, but that assumes we already found the minimum of its inductive subset. To find the solution you want, I believe you need to find a way to write all the possible transformations so that, in this case, any n greater than 13 can be shifted to any other number higher. My suggested above was to think of it in terms of modulo operation. Algebraically I have cosets in mind. This would make the notation force the numbers to basically become countable (14 is like 0, 15 is like 1, ...), but it does this by being a member of J (i.e., in the coset of modulo 3) and a member of K. This would give us an algebraic way to describe what has been talked about throughout this thread. As such, we can then simplify our expressions and have that "formula" you want.

Page 2 of 4 First 1234 Last