Proof by induction coins
$begingroup$
Question: Tom only have 2 type of coins: coins: 4 cents and 5 cents. Write a proof by induction that every amount n ≥ a can indeed be paid with Tom coins
1) Base Case: Tom can pay $12, $13, $14, $15, $16 and $17
2) Inductive steep: Let n>= 17 and suppose the Tom can pay every amount k with 12 <= k < n
3) Proof of claim: I am confused now...
edit: it's a normal induction, not strong induction
discrete-mathematics proof-verification proof-writing
asked Dec 10 '18 at 2:29
Tom1999Tom1999
445
$endgroup$
add a comment |
$begingroup$
Question: Tom only have 2 type of coins: coins: 4 cents and 5 cents. Write a proof by induction that every amount n ≥ a can indeed be paid with Tom coins
1) Base Case: Tom can pay $12, $13, $14, $15, $16 and $17
2) Inductive steep: Let n>= 17 and suppose the Tom can pay every amount k with 12 <= k < n
3) Proof of claim: I am confused now...
edit: it's a normal induction, not strong induction
discrete-mathematics proof-verification proof-writing
asked Dec 10 '18 at 2:29
Tom1999Tom1999
445
$endgroup$
$begingroup$
If you can get $k = a$ four cents and $b$ five cents, how con you do $k + 1$. How many four cents and how many five cents would you need?
$endgroup$
– fleablood
Dec 10 '18 at 2:37
$begingroup$
Hint: $5-4 = 1$. and $4*4 - 3*5 = 1$.
$endgroup$
– fleablood
Dec 10 '18 at 2:37
$begingroup$
Oh coffee maths answer is better than my hint. Dont try to go from $n= k$ to $n+1 = k+1$. Go from $n= k-4$ to $n+5 = k+1$.
$endgroup$
– fleablood
Dec 10 '18 at 2:51
$begingroup$
Is it for strong or normal induction? thank you!
$endgroup$
– Tom1999
Dec 10 '18 at 2:55
$begingroup$
The only difference between strong and weak is that with strong you use all lower values you've already done. Not just the current one you are assuming. There is no significant difference. I really don't think strong is forbidden. I just think the haven't yet taught you the term.
$endgroup$
– fleablood
Dec 10 '18 at 3:02
add a comment |
$begingroup$
Question: Tom only have 2 type of coins: coins: 4 cents and 5 cents. Write a proof by induction that every amount n ≥ a can indeed be paid with Tom coins
1) Base Case: Tom can pay $12, $13, $14, $15, $16 and $17
2) Inductive steep: Let n>= 17 and suppose the Tom can pay every amount k with 12 <= k < n
3) Proof of claim: I am confused now...
edit: it's a normal induction, not strong induction
discrete-mathematics proof-verification proof-writing
asked Dec 10 '18 at 2:29
Tom1999Tom1999
445
$endgroup$
Question: Tom only have 2 type of coins: coins: 4 cents and 5 cents. Write a proof by induction that every amount n ≥ a can indeed be paid with Tom coins
1) Base Case: Tom can pay $12, $13, $14, $15, $16 and $17
2) Inductive steep: Let n>= 17 and suppose the Tom can pay every amount k with 12 <= k < n
3) Proof of claim: I am confused now...
edit: it's a normal induction, not strong induction
discrete-mathematics proof-verification proof-writing
discrete-mathematics proof-verification proof-writing
asked Dec 10 '18 at 2:29
Tom1999Tom1999
445
asked Dec 10 '18 at 2:29
Tom1999Tom1999
445
edited Dec 10 '18 at 2:49
Tom1999
asked Dec 10 '18 at 2:29
Tom1999Tom1999
445
asked Dec 10 '18 at 2:29
Tom1999Tom1999
445
asked Dec 10 '18 at 2:29
Tom1999Tom1999
445
445
$begingroup$
If you can get $k = a$ four cents and $b$ five cents, how con you do $k + 1$. How many four cents and how many five cents would you need?
$endgroup$
– fleablood
Dec 10 '18 at 2:37
$begingroup$
Hint: $5-4 = 1$. and $4*4 - 3*5 = 1$.
$endgroup$
– fleablood
Dec 10 '18 at 2:37
$begingroup$
Oh coffee maths answer is better than my hint. Dont try to go from $n= k$ to $n+1 = k+1$. Go from $n= k-4$ to $n+5 = k+1$.
$endgroup$
– fleablood
Dec 10 '18 at 2:51
$begingroup$
Is it for strong or normal induction? thank you!
$endgroup$
– Tom1999
Dec 10 '18 at 2:55
$begingroup$
The only difference between strong and weak is that with strong you use all lower values you've already done. Not just the current one you are assuming. There is no significant difference. I really don't think strong is forbidden. I just think the haven't yet taught you the term.
$endgroup$
– fleablood
Dec 10 '18 at 3:02
add a comment |
$begingroup$
If you can get $k = a$ four cents and $b$ five cents, how con you do $k + 1$. How many four cents and how many five cents would you need?
$endgroup$
– fleablood
Dec 10 '18 at 2:37
$begingroup$
Hint: $5-4 = 1$. and $4*4 - 3*5 = 1$.
$endgroup$
– fleablood
Dec 10 '18 at 2:37
$begingroup$
Oh coffee maths answer is better than my hint. Dont try to go from $n= k$ to $n+1 = k+1$. Go from $n= k-4$ to $n+5 = k+1$.
$endgroup$
– fleablood
Dec 10 '18 at 2:51
$begingroup$
Is it for strong or normal induction? thank you!
$endgroup$
– Tom1999
Dec 10 '18 at 2:55
$begingroup$
The only difference between strong and weak is that with strong you use all lower values you've already done. Not just the current one you are assuming. There is no significant difference. I really don't think strong is forbidden. I just think the haven't yet taught you the term.
$endgroup$
– fleablood
Dec 10 '18 at 3:02
$begingroup$
If you can get $k = a$ four cents and $b$ five cents, how con you do $k + 1$. How many four cents and how many five cents would you need?
$endgroup$
– fleablood
Dec 10 '18 at 2:37
$begingroup$
If you can get $k = a$ four cents and $b$ five cents, how con you do $k + 1$. How many four cents and how many five cents would you need?
$endgroup$
– fleablood
Dec 10 '18 at 2:37
$begingroup$
Hint: $5-4 = 1$. and $4*4 - 3*5 = 1$.
$endgroup$
– fleablood
Dec 10 '18 at 2:37
$begingroup$
Hint: $5-4 = 1$. and $4*4 - 3*5 = 1$.
$endgroup$
– fleablood
Dec 10 '18 at 2:37
$begingroup$
Oh coffee maths answer is better than my hint. Dont try to go from $n= k$ to $n+1 = k+1$. Go from $n= k-4$ to $n+5 = k+1$.
$endgroup$
– fleablood
Dec 10 '18 at 2:51
$begingroup$
Oh coffee maths answer is better than my hint. Dont try to go from $n= k$ to $n+1 = k+1$. Go from $n= k-4$ to $n+5 = k+1$.
$endgroup$
– fleablood
Dec 10 '18 at 2:51
$begingroup$
Is it for strong or normal induction? thank you!
$endgroup$
– Tom1999
Dec 10 '18 at 2:55
$begingroup$
Is it for strong or normal induction? thank you!
$endgroup$
– Tom1999
Dec 10 '18 at 2:55
$begingroup$
The only difference between strong and weak is that with strong you use all lower values you've already done. Not just the current one you are assuming. There is no significant difference. I really don't think strong is forbidden. I just think the haven't yet taught you the term.
$endgroup$
– fleablood
Dec 10 '18 at 3:02
$begingroup$
The only difference between strong and weak is that with strong you use all lower values you've already done. Not just the current one you are assuming. There is no significant difference. I really don't think strong is forbidden. I just think the haven't yet taught you the term.
$endgroup$
– fleablood
Dec 10 '18 at 3:02
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Consider your next case where $n ge 17.$ you can subtract $5$ and get $12$ (already done by earlier case.)
If $n=18$ subtract $5,$ and so on up to $22.$ Keep going in such groups of six.
answered Dec 10 '18 at 2:37
coffeemathcoffeemath
2,7481415
$endgroup$
add a comment |
$begingroup$
Normal induction includes strong induction.
But consider this:
Assume $k = 4a + 5b$.
Case 1: $a > 0$ then $k+1 = 4a + 5b+1 = 4a + 5b + 5 -4 = 4(a-1) + 5(b+1)$. Done.
Case 2: $a = 0$ but $k > 2$, then $k +1 =4a + 5b +1 = 4a + 5b + 16-15 = 4(a+4) + 5(b-3)$. Done.
Case 3: $a = 0$ and $k le 2$ then $kle 10$ and ... that's not a concern.
======
This is a good example of strong induction.
Suppose you know you can do it for ALL cases $12 le n le k$. And $k ge 17$. Then you can do it for $k-4$. And if you can do it for $k -4$ you can do it for $k -4 +5 =k+1$ simply by doing what you did for $k-4$ and adding a $5$ cent coin.
answered Dec 10 '18 at 2:45
fleabloodfleablood
69.5k22685
$endgroup$
$begingroup$
Thanks @fleablood but I forgot to mention it's not strong induction, it's normal induction
$endgroup$
– Tom1999
Dec 10 '18 at 2:46
$begingroup$
Strong induction and regular induction are the same thing really.
$endgroup$
– fleablood
Dec 10 '18 at 3:00
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3033344%2fproof-by-induction-coins%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Consider your next case where $n ge 17.$ you can subtract $5$ and get $12$ (already done by earlier case.)
If $n=18$ subtract $5,$ and so on up to $22.$ Keep going in such groups of six.
answered Dec 10 '18 at 2:37
coffeemathcoffeemath
2,7481415
$endgroup$
add a comment |
$begingroup$
Consider your next case where $n ge 17.$ you can subtract $5$ and get $12$ (already done by earlier case.)
If $n=18$ subtract $5,$ and so on up to $22.$ Keep going in such groups of six.
answered Dec 10 '18 at 2:37
coffeemathcoffeemath
2,7481415
$endgroup$
add a comment |
$begingroup$
Consider your next case where $n ge 17.$ you can subtract $5$ and get $12$ (already done by earlier case.)
If $n=18$ subtract $5,$ and so on up to $22.$ Keep going in such groups of six.
answered Dec 10 '18 at 2:37
coffeemathcoffeemath
2,7481415
$endgroup$
Consider your next case where $n ge 17.$ you can subtract $5$ and get $12$ (already done by earlier case.)
If $n=18$ subtract $5,$ and so on up to $22.$ Keep going in such groups of six.
answered Dec 10 '18 at 2:37
coffeemathcoffeemath
2,7481415
answered Dec 10 '18 at 2:37
coffeemathcoffeemath
2,7481415
answered Dec 10 '18 at 2:37
coffeemathcoffeemath
2,7481415
answered Dec 10 '18 at 2:37
coffeemathcoffeemath
2,7481415
2,7481415
add a comment |
add a comment |
$begingroup$
Normal induction includes strong induction.
But consider this:
Assume $k = 4a + 5b$.
Case 1: $a > 0$ then $k+1 = 4a + 5b+1 = 4a + 5b + 5 -4 = 4(a-1) + 5(b+1)$. Done.
Case 2: $a = 0$ but $k > 2$, then $k +1 =4a + 5b +1 = 4a + 5b + 16-15 = 4(a+4) + 5(b-3)$. Done.
Case 3: $a = 0$ and $k le 2$ then $kle 10$ and ... that's not a concern.
======
This is a good example of strong induction.
Suppose you know you can do it for ALL cases $12 le n le k$. And $k ge 17$. Then you can do it for $k-4$. And if you can do it for $k -4$ you can do it for $k -4 +5 =k+1$ simply by doing what you did for $k-4$ and adding a $5$ cent coin.
answered Dec 10 '18 at 2:45
fleabloodfleablood
69.5k22685
$endgroup$
$begingroup$
Thanks @fleablood but I forgot to mention it's not strong induction, it's normal induction
$endgroup$
– Tom1999
Dec 10 '18 at 2:46
$begingroup$
Strong induction and regular induction are the same thing really.
$endgroup$
– fleablood
Dec 10 '18 at 3:00
add a comment |
$begingroup$
Normal induction includes strong induction.
But consider this:
Assume $k = 4a + 5b$.
Case 1: $a > 0$ then $k+1 = 4a + 5b+1 = 4a + 5b + 5 -4 = 4(a-1) + 5(b+1)$. Done.
Case 2: $a = 0$ but $k > 2$, then $k +1 =4a + 5b +1 = 4a + 5b + 16-15 = 4(a+4) + 5(b-3)$. Done.
Case 3: $a = 0$ and $k le 2$ then $kle 10$ and ... that's not a concern.
======
This is a good example of strong induction.
Suppose you know you can do it for ALL cases $12 le n le k$. And $k ge 17$. Then you can do it for $k-4$. And if you can do it for $k -4$ you can do it for $k -4 +5 =k+1$ simply by doing what you did for $k-4$ and adding a $5$ cent coin.
answered Dec 10 '18 at 2:45
fleabloodfleablood
69.5k22685
$endgroup$
$begingroup$
Thanks @fleablood but I forgot to mention it's not strong induction, it's normal induction
$endgroup$
– Tom1999
Dec 10 '18 at 2:46
$begingroup$
Strong induction and regular induction are the same thing really.
$endgroup$
– fleablood
Dec 10 '18 at 3:00
add a comment |
$begingroup$
Normal induction includes strong induction.
But consider this:
Assume $k = 4a + 5b$.
Case 1: $a > 0$ then $k+1 = 4a + 5b+1 = 4a + 5b + 5 -4 = 4(a-1) + 5(b+1)$. Done.
Case 2: $a = 0$ but $k > 2$, then $k +1 =4a + 5b +1 = 4a + 5b + 16-15 = 4(a+4) + 5(b-3)$. Done.
Case 3: $a = 0$ and $k le 2$ then $kle 10$ and ... that's not a concern.
======
This is a good example of strong induction.
Suppose you know you can do it for ALL cases $12 le n le k$. And $k ge 17$. Then you can do it for $k-4$. And if you can do it for $k -4$ you can do it for $k -4 +5 =k+1$ simply by doing what you did for $k-4$ and adding a $5$ cent coin.
answered Dec 10 '18 at 2:45
fleabloodfleablood
69.5k22685
$endgroup$
Normal induction includes strong induction.
But consider this:
Assume $k = 4a + 5b$.
Case 1: $a > 0$ then $k+1 = 4a + 5b+1 = 4a + 5b + 5 -4 = 4(a-1) + 5(b+1)$. Done.
Case 2: $a = 0$ but $k > 2$, then $k +1 =4a + 5b +1 = 4a + 5b + 16-15 = 4(a+4) + 5(b-3)$. Done.
Case 3: $a = 0$ and $k le 2$ then $kle 10$ and ... that's not a concern.
======
This is a good example of strong induction.
Suppose you know you can do it for ALL cases $12 le n le k$. And $k ge 17$. Then you can do it for $k-4$. And if you can do it for $k -4$ you can do it for $k -4 +5 =k+1$ simply by doing what you did for $k-4$ and adding a $5$ cent coin.
answered Dec 10 '18 at 2:45
fleabloodfleablood
69.5k22685
edited Dec 10 '18 at 3:00
answered Dec 10 '18 at 2:45
fleabloodfleablood
69.5k22685
answered Dec 10 '18 at 2:45
fleabloodfleablood
69.5k22685
answered Dec 10 '18 at 2:45
fleabloodfleablood
69.5k22685
69.5k22685
$begingroup$
Thanks @fleablood but I forgot to mention it's not strong induction, it's normal induction
$endgroup$
– Tom1999
Dec 10 '18 at 2:46
$begingroup$
Strong induction and regular induction are the same thing really.
$endgroup$
– fleablood
Dec 10 '18 at 3:00
add a comment |
$begingroup$
Thanks @fleablood but I forgot to mention it's not strong induction, it's normal induction
$endgroup$
– Tom1999
Dec 10 '18 at 2:46
$begingroup$
Strong induction and regular induction are the same thing really.
$endgroup$
– fleablood
Dec 10 '18 at 3:00
$begingroup$
Thanks @fleablood but I forgot to mention it's not strong induction, it's normal induction
$endgroup$
– Tom1999
Dec 10 '18 at 2:46
$begingroup$
Thanks @fleablood but I forgot to mention it's not strong induction, it's normal induction
$endgroup$
– Tom1999
Dec 10 '18 at 2:46
$begingroup$
Strong induction and regular induction are the same thing really.
$endgroup$
– fleablood
Dec 10 '18 at 3:00
$begingroup$
Strong induction and regular induction are the same thing really.
$endgroup$
– fleablood
Dec 10 '18 at 3:00
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3033344%2fproof-by-induction-coins%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
If you can get $k = a$ four cents and $b$ five cents, how con you do $k + 1$. How many four cents and how many five cents would you need?
$endgroup$
– fleablood
Dec 10 '18 at 2:37
$begingroup$
Hint: $5-4 = 1$. and $4*4 - 3*5 = 1$.
$endgroup$
– fleablood
Dec 10 '18 at 2:37
$begingroup$
Oh coffee maths answer is better than my hint. Dont try to go from $n= k$ to $n+1 = k+1$. Go from $n= k-4$ to $n+5 = k+1$.
$endgroup$
– fleablood
Dec 10 '18 at 2:51
$begingroup$
Is it for strong or normal induction? thank you!
$endgroup$
– Tom1999
Dec 10 '18 at 2:55
$begingroup$
The only difference between strong and weak is that with strong you use all lower values you've already done. Not just the current one you are assuming. There is no significant difference. I really don't think strong is forbidden. I just think the haven't yet taught you the term.
$endgroup$
– fleablood
Dec 10 '18 at 3:02