Are we properly using mathematical induction?
$begingroup$
I recently had a lecture in a Computer Science course involving the use of induction. The main discrepancy lies in that a few students and I think our proof should suffice, but our instructor argues that there are gaps in our logic. We really just want to get a full understanding of why there may be gaps in our logic.
Problem: Prove that for $Kgeq8$, the value $K$ can be made up of the sum of two different types of coins with value $3$ and $5$.
Our Proof: We show that this is true for $K=8,9,10$.
Let $m$ denote a $3$ coin and $n$ denote a $5$ coin.
$K=8=3+5=m+n$
$K=9=3+3+3=3m$
$K=10=5+5=2n$
So we have established that this holds for $K=8,9,10$. Let $N>10$. Assume that our hypothesis hold for $8leq Kleq N$. We wish to show this implies it holds for $K=N+1$.
So, $K=N+1=(N-2)+3$, and by our inductive hypothesis, $N-2$ can be made up of 3-coins and 5-coins, (since $N>10$), and clearly $3$ is simply one 3-coin., thus $K=N+1$ can be made up of 3-coins and 5-coins.
We have established our base case ($K=8,9,10$) and shown that assuming $K=N$ holds for $Ngeq10$, this implies that $K=N+1$ holds, and thus by the principle of mathematical induction, any value $Kgeq8$ can be made up of 3-coins and 5-coins.
Is our argument unsound? Our professor's disagreement was that in order to prove it in this way, we actually must prove for 3 different sequences, that is, 3 separate sequences in which our $K$ value is $8,11,14,...$, and $9,12,15,...$, and $10,13,16,...$ respectively. He states this is because induction must rely solely on the immediately prior term, i.e. $A_N$ implies $A_{N+1}$ implies $A_{N+2}$ ... but that our proof only relates $A_{N+1}$ to $A_{N-2}$. Is this really how induction works?
We think this is maybe because of how induction and sequences are defined in our course, but based on our prior math courses, we think this should suffice.
proof-verification logic induction
$endgroup$
|
show 4 more comments
$begingroup$
I recently had a lecture in a Computer Science course involving the use of induction. The main discrepancy lies in that a few students and I think our proof should suffice, but our instructor argues that there are gaps in our logic. We really just want to get a full understanding of why there may be gaps in our logic.
Problem: Prove that for $Kgeq8$, the value $K$ can be made up of the sum of two different types of coins with value $3$ and $5$.
Our Proof: We show that this is true for $K=8,9,10$.
Let $m$ denote a $3$ coin and $n$ denote a $5$ coin.
$K=8=3+5=m+n$
$K=9=3+3+3=3m$
$K=10=5+5=2n$
So we have established that this holds for $K=8,9,10$. Let $N>10$. Assume that our hypothesis hold for $8leq Kleq N$. We wish to show this implies it holds for $K=N+1$.
So, $K=N+1=(N-2)+3$, and by our inductive hypothesis, $N-2$ can be made up of 3-coins and 5-coins, (since $N>10$), and clearly $3$ is simply one 3-coin., thus $K=N+1$ can be made up of 3-coins and 5-coins.
We have established our base case ($K=8,9,10$) and shown that assuming $K=N$ holds for $Ngeq10$, this implies that $K=N+1$ holds, and thus by the principle of mathematical induction, any value $Kgeq8$ can be made up of 3-coins and 5-coins.
Is our argument unsound? Our professor's disagreement was that in order to prove it in this way, we actually must prove for 3 different sequences, that is, 3 separate sequences in which our $K$ value is $8,11,14,...$, and $9,12,15,...$, and $10,13,16,...$ respectively. He states this is because induction must rely solely on the immediately prior term, i.e. $A_N$ implies $A_{N+1}$ implies $A_{N+2}$ ... but that our proof only relates $A_{N+1}$ to $A_{N-2}$. Is this really how induction works?
We think this is maybe because of how induction and sequences are defined in our course, but based on our prior math courses, we think this should suffice.
proof-verification logic induction
$endgroup$
15
$begingroup$
Your argument is fine.
$endgroup$
– José Carlos Santos
8 hours ago
5
$begingroup$
You might want to emphasize that your hypothesis holds for all $K$ with $8leq Kleq N$. Otherwise this is fine. Using weak induction requires you to do induction on three sequences. But your hypothesis makes this an argument by strong induction, which enables you to do it on just one sequence.
$endgroup$
– Servaes
8 hours ago
1
$begingroup$
@JoséCarlosSantos The proof is correct, but I'm assuming the professor was implying that they needed to use weak induction to solve this problem. Perhaps they have not axiomatically shown that they are equivalent yet.
$endgroup$
– Don Thousand
8 hours ago
6
$begingroup$
The other commenters are right: this is an issue of ordinary vs. strong induction.
$endgroup$
– Randall
8 hours ago
6
$begingroup$
"Let $N>10$" You should change that into "let $Ngeq10$".
$endgroup$
– drhab
8 hours ago
|
show 4 more comments
$begingroup$
I recently had a lecture in a Computer Science course involving the use of induction. The main discrepancy lies in that a few students and I think our proof should suffice, but our instructor argues that there are gaps in our logic. We really just want to get a full understanding of why there may be gaps in our logic.
Problem: Prove that for $Kgeq8$, the value $K$ can be made up of the sum of two different types of coins with value $3$ and $5$.
Our Proof: We show that this is true for $K=8,9,10$.
Let $m$ denote a $3$ coin and $n$ denote a $5$ coin.
$K=8=3+5=m+n$
$K=9=3+3+3=3m$
$K=10=5+5=2n$
So we have established that this holds for $K=8,9,10$. Let $N>10$. Assume that our hypothesis hold for $8leq Kleq N$. We wish to show this implies it holds for $K=N+1$.
So, $K=N+1=(N-2)+3$, and by our inductive hypothesis, $N-2$ can be made up of 3-coins and 5-coins, (since $N>10$), and clearly $3$ is simply one 3-coin., thus $K=N+1$ can be made up of 3-coins and 5-coins.
We have established our base case ($K=8,9,10$) and shown that assuming $K=N$ holds for $Ngeq10$, this implies that $K=N+1$ holds, and thus by the principle of mathematical induction, any value $Kgeq8$ can be made up of 3-coins and 5-coins.
Is our argument unsound? Our professor's disagreement was that in order to prove it in this way, we actually must prove for 3 different sequences, that is, 3 separate sequences in which our $K$ value is $8,11,14,...$, and $9,12,15,...$, and $10,13,16,...$ respectively. He states this is because induction must rely solely on the immediately prior term, i.e. $A_N$ implies $A_{N+1}$ implies $A_{N+2}$ ... but that our proof only relates $A_{N+1}$ to $A_{N-2}$. Is this really how induction works?
We think this is maybe because of how induction and sequences are defined in our course, but based on our prior math courses, we think this should suffice.
proof-verification logic induction
$endgroup$
I recently had a lecture in a Computer Science course involving the use of induction. The main discrepancy lies in that a few students and I think our proof should suffice, but our instructor argues that there are gaps in our logic. We really just want to get a full understanding of why there may be gaps in our logic.
Problem: Prove that for $Kgeq8$, the value $K$ can be made up of the sum of two different types of coins with value $3$ and $5$.
Our Proof: We show that this is true for $K=8,9,10$.
Let $m$ denote a $3$ coin and $n$ denote a $5$ coin.
$K=8=3+5=m+n$
$K=9=3+3+3=3m$
$K=10=5+5=2n$
So we have established that this holds for $K=8,9,10$. Let $N>10$. Assume that our hypothesis hold for $8leq Kleq N$. We wish to show this implies it holds for $K=N+1$.
So, $K=N+1=(N-2)+3$, and by our inductive hypothesis, $N-2$ can be made up of 3-coins and 5-coins, (since $N>10$), and clearly $3$ is simply one 3-coin., thus $K=N+1$ can be made up of 3-coins and 5-coins.
We have established our base case ($K=8,9,10$) and shown that assuming $K=N$ holds for $Ngeq10$, this implies that $K=N+1$ holds, and thus by the principle of mathematical induction, any value $Kgeq8$ can be made up of 3-coins and 5-coins.
Is our argument unsound? Our professor's disagreement was that in order to prove it in this way, we actually must prove for 3 different sequences, that is, 3 separate sequences in which our $K$ value is $8,11,14,...$, and $9,12,15,...$, and $10,13,16,...$ respectively. He states this is because induction must rely solely on the immediately prior term, i.e. $A_N$ implies $A_{N+1}$ implies $A_{N+2}$ ... but that our proof only relates $A_{N+1}$ to $A_{N-2}$. Is this really how induction works?
We think this is maybe because of how induction and sequences are defined in our course, but based on our prior math courses, we think this should suffice.
proof-verification logic induction
proof-verification logic induction
asked 8 hours ago
Damian VuDamian Vu
835
835
15
$begingroup$
Your argument is fine.
$endgroup$
– José Carlos Santos
8 hours ago
5
$begingroup$
You might want to emphasize that your hypothesis holds for all $K$ with $8leq Kleq N$. Otherwise this is fine. Using weak induction requires you to do induction on three sequences. But your hypothesis makes this an argument by strong induction, which enables you to do it on just one sequence.
$endgroup$
– Servaes
8 hours ago
1
$begingroup$
@JoséCarlosSantos The proof is correct, but I'm assuming the professor was implying that they needed to use weak induction to solve this problem. Perhaps they have not axiomatically shown that they are equivalent yet.
$endgroup$
– Don Thousand
8 hours ago
6
$begingroup$
The other commenters are right: this is an issue of ordinary vs. strong induction.
$endgroup$
– Randall
8 hours ago
6
$begingroup$
"Let $N>10$" You should change that into "let $Ngeq10$".
$endgroup$
– drhab
8 hours ago
|
show 4 more comments
15
$begingroup$
Your argument is fine.
$endgroup$
– José Carlos Santos
8 hours ago
5
$begingroup$
You might want to emphasize that your hypothesis holds for all $K$ with $8leq Kleq N$. Otherwise this is fine. Using weak induction requires you to do induction on three sequences. But your hypothesis makes this an argument by strong induction, which enables you to do it on just one sequence.
$endgroup$
– Servaes
8 hours ago
1
$begingroup$
@JoséCarlosSantos The proof is correct, but I'm assuming the professor was implying that they needed to use weak induction to solve this problem. Perhaps they have not axiomatically shown that they are equivalent yet.
$endgroup$
– Don Thousand
8 hours ago
6
$begingroup$
The other commenters are right: this is an issue of ordinary vs. strong induction.
$endgroup$
– Randall
8 hours ago
6
$begingroup$
"Let $N>10$" You should change that into "let $Ngeq10$".
$endgroup$
– drhab
8 hours ago
15
15
$begingroup$
Your argument is fine.
$endgroup$
– José Carlos Santos
8 hours ago
$begingroup$
Your argument is fine.
$endgroup$
– José Carlos Santos
8 hours ago
5
5
$begingroup$
You might want to emphasize that your hypothesis holds for all $K$ with $8leq Kleq N$. Otherwise this is fine. Using weak induction requires you to do induction on three sequences. But your hypothesis makes this an argument by strong induction, which enables you to do it on just one sequence.
$endgroup$
– Servaes
8 hours ago
$begingroup$
You might want to emphasize that your hypothesis holds for all $K$ with $8leq Kleq N$. Otherwise this is fine. Using weak induction requires you to do induction on three sequences. But your hypothesis makes this an argument by strong induction, which enables you to do it on just one sequence.
$endgroup$
– Servaes
8 hours ago
1
1
$begingroup$
@JoséCarlosSantos The proof is correct, but I'm assuming the professor was implying that they needed to use weak induction to solve this problem. Perhaps they have not axiomatically shown that they are equivalent yet.
$endgroup$
– Don Thousand
8 hours ago
$begingroup$
@JoséCarlosSantos The proof is correct, but I'm assuming the professor was implying that they needed to use weak induction to solve this problem. Perhaps they have not axiomatically shown that they are equivalent yet.
$endgroup$
– Don Thousand
8 hours ago
6
6
$begingroup$
The other commenters are right: this is an issue of ordinary vs. strong induction.
$endgroup$
– Randall
8 hours ago
$begingroup$
The other commenters are right: this is an issue of ordinary vs. strong induction.
$endgroup$
– Randall
8 hours ago
6
6
$begingroup$
"Let $N>10$" You should change that into "let $Ngeq10$".
$endgroup$
– drhab
8 hours ago
$begingroup$
"Let $N>10$" You should change that into "let $Ngeq10$".
$endgroup$
– drhab
8 hours ago
|
show 4 more comments
4 Answers
4
active
oldest
votes
$begingroup$
First we have this principle: take any (mathematically well-formed) property $P(n)$, depending on $n$ if you can prove that
$$P(0)$$
$$forall n in mathbb{N}, P(n) implies P(n+1)$$
from this you may conclude $$forall n in mathbb{N}, P(n)$$
From this induction principle you can derive many other induction principles: finite induction, backwards induction etc but we only need two of the following:
You may start from any other natural number other than $0$:
$$P(k)$$
$$forall n in mathbb{N_{ge{k}}}, P(n) implies P(n+1)$$
$$forall n in mathbb{N_{ge{k}}}, P(n)$$
and a principle of strong induction:
Suppose you prove
$$forall n in mathbb{N_{ge{k}}},Bigl(forall k in mathbb{N_{ge{k}}}, [k < n implies P(k)]Bigr) implies P(n)$$
then you may conclude
$$forall n in mathbb{N_{ge{k}}} P(n)$$
In words, the first principle of mathematical induction works like this:
You prove the base case (it is absolutely necessary to do this!) and after that you prove that the property holds for some number $n$ by knowing only that it holds for the previous number $n-1$!
And if you work with the principle of strong induction not only that you don't need to prove the base case - you can also consider that the property holds for all of the previous numbers! How cool is that?
And this is exactly what you did in your proof by strong induction:
Let's suppose that $P(n)$ means than $n$ can be rewritten as sum of $2$'s and $3$'s.
So you take any number $n ge 8$. You assume that forall $8 le k < n$ that property holds and then you prove that it also holds for $n$. You do this by cases:
if $n = 8$ then $P(n)$
if $n = 9$ then $P(n)$
if $n = 10$ then $P(n)$
if $n > 10$ then $8 le n - 3 < n$ and thus by assumption $P(n-3)$ from this follows $P(n)$ since it only has one more $3$.
So you see that $P(n)$ holds in all cases thus by principle of strong induction you may conclude $forall n in mathbb{N_{ge{8}}}, P(n)$
Now let's see how you could proceed by using first (ordinary) induction:
The idea is to use ordinary induction 3 times to prove that the property holds for 3 different sequences of natural numbers, that is for
$8 + 3n$, $9+3n$, $10+3n$ $n ge 8$ from this you will be able to conclude that it in facts hold for any natural number greater than $8$, since it'll definitely be in one of those sequences.
I'll show how to do that for the first one, the other two are proved verbatim.
We prove $$forall n in mathbb{N} mbox{ we have } P(8+3n)$$
$$n = 0, mbox{ we certainly have } P(8)$$
Now assume we have $P(8+3k)$ for some $k in mathbb{N}$ then we need to prove that $P[8 + 3(k+1)]$.
But $8+3(k+1) = (8 + 3k) + 3$ and since $8 + 3k$ could be rewritten as a sum of $3$'s and $2$'s then $(8+3k)+3$ can be also rewritten this way since it is the same but has one more 3.
Thus, we have $P[8 + 3(k+1)]$ and thus by the ordinary induction you may conclude $$forall n in mathbb{N}, P(8+3n)$$
$endgroup$
$begingroup$
Thanks for this! I think that clears up the idea of strong induction for me, which I was a little bit shaky with
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
Another way to organize the proof: show by "weak induction" that for all $k ge 8$, we have $P(k) wedge P(k+1) wedge P(k+2)$. Call this conjunction $Q(k)$; then you have shown all the elements of $Q(8) = P(8) wedge P(9) wedge P(10)$. For $Q(k) rightarrow Q(k+1)$, if $P(k) wedge P(k+1) wedge P(k+2)$, then you already know $P(k+1)$ and $P(k+2)$ are true; and also, since $P(k)$ is true and you have shown $P(k) rightarrow P(k+3)$, you also know $P(k+3)$. Therefore, $P(k+1) wedge P(k+2) wedge P(k+3)$, in other words, $Q(k+1)$.
$endgroup$
– Daniel Schepler
18 mins ago
add a comment |
$begingroup$
Note that $P(N)$ does not imply $P(N+1)$ in any immediate way (e.g. it is not immediately clear why $17$ should have the property just because $16$ has the property ... though see the inductive proof I give a little later in this post).
So, if you have to use weak induction, the obvious thing to do is what your professor does, and do $3$ separate weak inductive proofs:
Show that $P(8)$, and show that for all $n$: $P(8+3n)Rightarrow P(8+3(n+1))$
Show that $P(9)$, and show that for all $n$: $P(9+3n)Rightarrow P(9+3(n+1))$
Show that $P(10)$, and show that for all $n$: $P(10+3n)Rightarrow P(10+3(n+1))$
Combined together, these proofs show that for all $n ge 8$: $P(n)$
Another possible weak inductive proof is this:
Show that $P(8)$, $P(9)$, and $P(10)$ hold. Now suppose $P(N)$ holds with $N ge 10$. Because $N ge 10$, we know that to form $N$, we need to either use at least one $5$, or (if we don't use any $5$'s at all), at least three $3$'s. But if $P(N)$ is formed using at least one $5$, then we can form $P(N+1)$ by taking away one $5$ and adding two $3$'s. And if we use at least three $3$ to form $P(N)$, then we can form $P(N+1)$ by taking away three $3$'s and adding two $5$'s. So, either way, we can form $P(N+1)$
Your method uses strong induction, and is of course a perfectly good mathematical proof as well ... but maybe your professor had insisted on you using weak induction?
$endgroup$
3
$begingroup$
Thanks! I just got an email back from him. He agrees now it is fine, but not a "conventional" way of doing the proof in his words. The main point of discrepancy was that, during lecture, he said "it cannot be done in that way, even under strong induction" which was the confusing part for us. We understood that it would take multiple proofs to do it under weak induction, but that was the main point of confusion. As a matter of fact, the way he did it in class was through a lot more reasoning instead of 3 separate weak inductive proofs, which is what led us to ask if this would work instead
$endgroup$
– Damian Vu
6 hours ago
1
$begingroup$
@DamianVu Cool! Did he do it using the other weak inductive proof I just added to my Answer?
$endgroup$
– Bram28
6 hours ago
1
$begingroup$
ah yes I didn't see that. That is exactly how he did it in class.
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
@DamianVu OK. But that is a different proof than what you described in your post. :)
$endgroup$
– Bram28
6 hours ago
1
$begingroup$
@DamianVu Oh! No, the professor was definitely wrong about that.
$endgroup$
– Bram28
2 hours ago
|
show 1 more comment
$begingroup$
If the property is true for all $k$ such that $$8le kle n,$$ where $10le n$, then it is true for $n-2$ and is true for $n+1$, and for all $k$ such that
$$8le kle n+1.$$
$endgroup$
add a comment |
$begingroup$
Forget about induction for a second.
Let us say $P(K)$ holds iff there exist $c,d geq 0$ such that $K=3c+5d$.
Your goal is to prove that $P(K)$ holds for all $K geq 8$.
If you would only want to prove $P(8)$ (for example) then you could just write a proof for that ($8=3+5$). However, you can't write a proof for $P(K)$ for all $K geq 8$ because there simply is not enough time to do that. What you can do instead is to write a computer program (algorithm) which gets $K geq 8$ as input and outputs a proof for $P(K)$. More specifically, on input $K$ it outputs two numbers $c,d$ such that $K=3c+5d$.
Indeed, your question already contains such a program $A$:
- if $K = 8$ then output $(1,1)$
- if $K = 9$ then output $(3,0)$
- if $K = 10$ then output $(0,2)$
- if $K > 10$ then compute $(c,d) = A(K-3)$ and output $(c + 1, d)$
Now, we need to argue that $A$ works correctly. For the three base cases this is obvious. For the recursive case we argue as follows. Let $K > 10$ and let $(c,d) = A(K-3)$. The algorithm $A$ is correct for input $K$ if
$$ K = 3(c+1) + 5d $$
As you have already observed: if $A(K-3)$ is correct, i.e. $K-3 = 3c+5d$, then the above holds as well. Therefore we have reduced proving that $A(K)$ is correct to proving that $A(K-3)$ is correct. Observe that $K-3 > 7$ because otherwise it would contradict our assumption $K > 10$. If $K-3 leq 10$ then correctness follows from the base cases. Otherwise ($K-3>10$), we can apply the same argument to see that: $A(K-3)$ is correct if $A(K-6)$ is correct. If $K-6$ is still larger than 10 we can apply the same argument and check whether $A(K-9)$ is correct and so on... it is not difficult to argue that eventually a base case is reached. Therefore $A$ works correctly.
My point is that the principle of induction is not some mysterious proof technique but naturally follows from the previous algorithmic perspective. Essentially, a proof by induction is a compact representation of a recursive algorithm which generates the proofs and a proof of correctness of that algorithm. The take-away message is: if you do a proof by induction and you are not certain whether it is sound, try to articulate the recursive algorithm which produces the proofs, try the algorithm out for some cases and then prove its correctness by using a chain of reductions as shown here (don't forget to argue that a base case is always reached eventually).
$endgroup$
$begingroup$
See also the Curry-Howard correspondence: under this correspondence, a proof by induction becomes precisely a special case of a recursive function.
$endgroup$
– Daniel Schepler
21 mins ago
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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%2f3101342%2fare-we-properly-using-mathematical-induction%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First we have this principle: take any (mathematically well-formed) property $P(n)$, depending on $n$ if you can prove that
$$P(0)$$
$$forall n in mathbb{N}, P(n) implies P(n+1)$$
from this you may conclude $$forall n in mathbb{N}, P(n)$$
From this induction principle you can derive many other induction principles: finite induction, backwards induction etc but we only need two of the following:
You may start from any other natural number other than $0$:
$$P(k)$$
$$forall n in mathbb{N_{ge{k}}}, P(n) implies P(n+1)$$
$$forall n in mathbb{N_{ge{k}}}, P(n)$$
and a principle of strong induction:
Suppose you prove
$$forall n in mathbb{N_{ge{k}}},Bigl(forall k in mathbb{N_{ge{k}}}, [k < n implies P(k)]Bigr) implies P(n)$$
then you may conclude
$$forall n in mathbb{N_{ge{k}}} P(n)$$
In words, the first principle of mathematical induction works like this:
You prove the base case (it is absolutely necessary to do this!) and after that you prove that the property holds for some number $n$ by knowing only that it holds for the previous number $n-1$!
And if you work with the principle of strong induction not only that you don't need to prove the base case - you can also consider that the property holds for all of the previous numbers! How cool is that?
And this is exactly what you did in your proof by strong induction:
Let's suppose that $P(n)$ means than $n$ can be rewritten as sum of $2$'s and $3$'s.
So you take any number $n ge 8$. You assume that forall $8 le k < n$ that property holds and then you prove that it also holds for $n$. You do this by cases:
if $n = 8$ then $P(n)$
if $n = 9$ then $P(n)$
if $n = 10$ then $P(n)$
if $n > 10$ then $8 le n - 3 < n$ and thus by assumption $P(n-3)$ from this follows $P(n)$ since it only has one more $3$.
So you see that $P(n)$ holds in all cases thus by principle of strong induction you may conclude $forall n in mathbb{N_{ge{8}}}, P(n)$
Now let's see how you could proceed by using first (ordinary) induction:
The idea is to use ordinary induction 3 times to prove that the property holds for 3 different sequences of natural numbers, that is for
$8 + 3n$, $9+3n$, $10+3n$ $n ge 8$ from this you will be able to conclude that it in facts hold for any natural number greater than $8$, since it'll definitely be in one of those sequences.
I'll show how to do that for the first one, the other two are proved verbatim.
We prove $$forall n in mathbb{N} mbox{ we have } P(8+3n)$$
$$n = 0, mbox{ we certainly have } P(8)$$
Now assume we have $P(8+3k)$ for some $k in mathbb{N}$ then we need to prove that $P[8 + 3(k+1)]$.
But $8+3(k+1) = (8 + 3k) + 3$ and since $8 + 3k$ could be rewritten as a sum of $3$'s and $2$'s then $(8+3k)+3$ can be also rewritten this way since it is the same but has one more 3.
Thus, we have $P[8 + 3(k+1)]$ and thus by the ordinary induction you may conclude $$forall n in mathbb{N}, P(8+3n)$$
$endgroup$
$begingroup$
Thanks for this! I think that clears up the idea of strong induction for me, which I was a little bit shaky with
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
Another way to organize the proof: show by "weak induction" that for all $k ge 8$, we have $P(k) wedge P(k+1) wedge P(k+2)$. Call this conjunction $Q(k)$; then you have shown all the elements of $Q(8) = P(8) wedge P(9) wedge P(10)$. For $Q(k) rightarrow Q(k+1)$, if $P(k) wedge P(k+1) wedge P(k+2)$, then you already know $P(k+1)$ and $P(k+2)$ are true; and also, since $P(k)$ is true and you have shown $P(k) rightarrow P(k+3)$, you also know $P(k+3)$. Therefore, $P(k+1) wedge P(k+2) wedge P(k+3)$, in other words, $Q(k+1)$.
$endgroup$
– Daniel Schepler
18 mins ago
add a comment |
$begingroup$
First we have this principle: take any (mathematically well-formed) property $P(n)$, depending on $n$ if you can prove that
$$P(0)$$
$$forall n in mathbb{N}, P(n) implies P(n+1)$$
from this you may conclude $$forall n in mathbb{N}, P(n)$$
From this induction principle you can derive many other induction principles: finite induction, backwards induction etc but we only need two of the following:
You may start from any other natural number other than $0$:
$$P(k)$$
$$forall n in mathbb{N_{ge{k}}}, P(n) implies P(n+1)$$
$$forall n in mathbb{N_{ge{k}}}, P(n)$$
and a principle of strong induction:
Suppose you prove
$$forall n in mathbb{N_{ge{k}}},Bigl(forall k in mathbb{N_{ge{k}}}, [k < n implies P(k)]Bigr) implies P(n)$$
then you may conclude
$$forall n in mathbb{N_{ge{k}}} P(n)$$
In words, the first principle of mathematical induction works like this:
You prove the base case (it is absolutely necessary to do this!) and after that you prove that the property holds for some number $n$ by knowing only that it holds for the previous number $n-1$!
And if you work with the principle of strong induction not only that you don't need to prove the base case - you can also consider that the property holds for all of the previous numbers! How cool is that?
And this is exactly what you did in your proof by strong induction:
Let's suppose that $P(n)$ means than $n$ can be rewritten as sum of $2$'s and $3$'s.
So you take any number $n ge 8$. You assume that forall $8 le k < n$ that property holds and then you prove that it also holds for $n$. You do this by cases:
if $n = 8$ then $P(n)$
if $n = 9$ then $P(n)$
if $n = 10$ then $P(n)$
if $n > 10$ then $8 le n - 3 < n$ and thus by assumption $P(n-3)$ from this follows $P(n)$ since it only has one more $3$.
So you see that $P(n)$ holds in all cases thus by principle of strong induction you may conclude $forall n in mathbb{N_{ge{8}}}, P(n)$
Now let's see how you could proceed by using first (ordinary) induction:
The idea is to use ordinary induction 3 times to prove that the property holds for 3 different sequences of natural numbers, that is for
$8 + 3n$, $9+3n$, $10+3n$ $n ge 8$ from this you will be able to conclude that it in facts hold for any natural number greater than $8$, since it'll definitely be in one of those sequences.
I'll show how to do that for the first one, the other two are proved verbatim.
We prove $$forall n in mathbb{N} mbox{ we have } P(8+3n)$$
$$n = 0, mbox{ we certainly have } P(8)$$
Now assume we have $P(8+3k)$ for some $k in mathbb{N}$ then we need to prove that $P[8 + 3(k+1)]$.
But $8+3(k+1) = (8 + 3k) + 3$ and since $8 + 3k$ could be rewritten as a sum of $3$'s and $2$'s then $(8+3k)+3$ can be also rewritten this way since it is the same but has one more 3.
Thus, we have $P[8 + 3(k+1)]$ and thus by the ordinary induction you may conclude $$forall n in mathbb{N}, P(8+3n)$$
$endgroup$
$begingroup$
Thanks for this! I think that clears up the idea of strong induction for me, which I was a little bit shaky with
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
Another way to organize the proof: show by "weak induction" that for all $k ge 8$, we have $P(k) wedge P(k+1) wedge P(k+2)$. Call this conjunction $Q(k)$; then you have shown all the elements of $Q(8) = P(8) wedge P(9) wedge P(10)$. For $Q(k) rightarrow Q(k+1)$, if $P(k) wedge P(k+1) wedge P(k+2)$, then you already know $P(k+1)$ and $P(k+2)$ are true; and also, since $P(k)$ is true and you have shown $P(k) rightarrow P(k+3)$, you also know $P(k+3)$. Therefore, $P(k+1) wedge P(k+2) wedge P(k+3)$, in other words, $Q(k+1)$.
$endgroup$
– Daniel Schepler
18 mins ago
add a comment |
$begingroup$
First we have this principle: take any (mathematically well-formed) property $P(n)$, depending on $n$ if you can prove that
$$P(0)$$
$$forall n in mathbb{N}, P(n) implies P(n+1)$$
from this you may conclude $$forall n in mathbb{N}, P(n)$$
From this induction principle you can derive many other induction principles: finite induction, backwards induction etc but we only need two of the following:
You may start from any other natural number other than $0$:
$$P(k)$$
$$forall n in mathbb{N_{ge{k}}}, P(n) implies P(n+1)$$
$$forall n in mathbb{N_{ge{k}}}, P(n)$$
and a principle of strong induction:
Suppose you prove
$$forall n in mathbb{N_{ge{k}}},Bigl(forall k in mathbb{N_{ge{k}}}, [k < n implies P(k)]Bigr) implies P(n)$$
then you may conclude
$$forall n in mathbb{N_{ge{k}}} P(n)$$
In words, the first principle of mathematical induction works like this:
You prove the base case (it is absolutely necessary to do this!) and after that you prove that the property holds for some number $n$ by knowing only that it holds for the previous number $n-1$!
And if you work with the principle of strong induction not only that you don't need to prove the base case - you can also consider that the property holds for all of the previous numbers! How cool is that?
And this is exactly what you did in your proof by strong induction:
Let's suppose that $P(n)$ means than $n$ can be rewritten as sum of $2$'s and $3$'s.
So you take any number $n ge 8$. You assume that forall $8 le k < n$ that property holds and then you prove that it also holds for $n$. You do this by cases:
if $n = 8$ then $P(n)$
if $n = 9$ then $P(n)$
if $n = 10$ then $P(n)$
if $n > 10$ then $8 le n - 3 < n$ and thus by assumption $P(n-3)$ from this follows $P(n)$ since it only has one more $3$.
So you see that $P(n)$ holds in all cases thus by principle of strong induction you may conclude $forall n in mathbb{N_{ge{8}}}, P(n)$
Now let's see how you could proceed by using first (ordinary) induction:
The idea is to use ordinary induction 3 times to prove that the property holds for 3 different sequences of natural numbers, that is for
$8 + 3n$, $9+3n$, $10+3n$ $n ge 8$ from this you will be able to conclude that it in facts hold for any natural number greater than $8$, since it'll definitely be in one of those sequences.
I'll show how to do that for the first one, the other two are proved verbatim.
We prove $$forall n in mathbb{N} mbox{ we have } P(8+3n)$$
$$n = 0, mbox{ we certainly have } P(8)$$
Now assume we have $P(8+3k)$ for some $k in mathbb{N}$ then we need to prove that $P[8 + 3(k+1)]$.
But $8+3(k+1) = (8 + 3k) + 3$ and since $8 + 3k$ could be rewritten as a sum of $3$'s and $2$'s then $(8+3k)+3$ can be also rewritten this way since it is the same but has one more 3.
Thus, we have $P[8 + 3(k+1)]$ and thus by the ordinary induction you may conclude $$forall n in mathbb{N}, P(8+3n)$$
$endgroup$
First we have this principle: take any (mathematically well-formed) property $P(n)$, depending on $n$ if you can prove that
$$P(0)$$
$$forall n in mathbb{N}, P(n) implies P(n+1)$$
from this you may conclude $$forall n in mathbb{N}, P(n)$$
From this induction principle you can derive many other induction principles: finite induction, backwards induction etc but we only need two of the following:
You may start from any other natural number other than $0$:
$$P(k)$$
$$forall n in mathbb{N_{ge{k}}}, P(n) implies P(n+1)$$
$$forall n in mathbb{N_{ge{k}}}, P(n)$$
and a principle of strong induction:
Suppose you prove
$$forall n in mathbb{N_{ge{k}}},Bigl(forall k in mathbb{N_{ge{k}}}, [k < n implies P(k)]Bigr) implies P(n)$$
then you may conclude
$$forall n in mathbb{N_{ge{k}}} P(n)$$
In words, the first principle of mathematical induction works like this:
You prove the base case (it is absolutely necessary to do this!) and after that you prove that the property holds for some number $n$ by knowing only that it holds for the previous number $n-1$!
And if you work with the principle of strong induction not only that you don't need to prove the base case - you can also consider that the property holds for all of the previous numbers! How cool is that?
And this is exactly what you did in your proof by strong induction:
Let's suppose that $P(n)$ means than $n$ can be rewritten as sum of $2$'s and $3$'s.
So you take any number $n ge 8$. You assume that forall $8 le k < n$ that property holds and then you prove that it also holds for $n$. You do this by cases:
if $n = 8$ then $P(n)$
if $n = 9$ then $P(n)$
if $n = 10$ then $P(n)$
if $n > 10$ then $8 le n - 3 < n$ and thus by assumption $P(n-3)$ from this follows $P(n)$ since it only has one more $3$.
So you see that $P(n)$ holds in all cases thus by principle of strong induction you may conclude $forall n in mathbb{N_{ge{8}}}, P(n)$
Now let's see how you could proceed by using first (ordinary) induction:
The idea is to use ordinary induction 3 times to prove that the property holds for 3 different sequences of natural numbers, that is for
$8 + 3n$, $9+3n$, $10+3n$ $n ge 8$ from this you will be able to conclude that it in facts hold for any natural number greater than $8$, since it'll definitely be in one of those sequences.
I'll show how to do that for the first one, the other two are proved verbatim.
We prove $$forall n in mathbb{N} mbox{ we have } P(8+3n)$$
$$n = 0, mbox{ we certainly have } P(8)$$
Now assume we have $P(8+3k)$ for some $k in mathbb{N}$ then we need to prove that $P[8 + 3(k+1)]$.
But $8+3(k+1) = (8 + 3k) + 3$ and since $8 + 3k$ could be rewritten as a sum of $3$'s and $2$'s then $(8+3k)+3$ can be also rewritten this way since it is the same but has one more 3.
Thus, we have $P[8 + 3(k+1)]$ and thus by the ordinary induction you may conclude $$forall n in mathbb{N}, P(8+3n)$$
edited 7 hours ago
answered 7 hours ago
famesyasdfamesyasd
184111
184111
$begingroup$
Thanks for this! I think that clears up the idea of strong induction for me, which I was a little bit shaky with
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
Another way to organize the proof: show by "weak induction" that for all $k ge 8$, we have $P(k) wedge P(k+1) wedge P(k+2)$. Call this conjunction $Q(k)$; then you have shown all the elements of $Q(8) = P(8) wedge P(9) wedge P(10)$. For $Q(k) rightarrow Q(k+1)$, if $P(k) wedge P(k+1) wedge P(k+2)$, then you already know $P(k+1)$ and $P(k+2)$ are true; and also, since $P(k)$ is true and you have shown $P(k) rightarrow P(k+3)$, you also know $P(k+3)$. Therefore, $P(k+1) wedge P(k+2) wedge P(k+3)$, in other words, $Q(k+1)$.
$endgroup$
– Daniel Schepler
18 mins ago
add a comment |
$begingroup$
Thanks for this! I think that clears up the idea of strong induction for me, which I was a little bit shaky with
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
Another way to organize the proof: show by "weak induction" that for all $k ge 8$, we have $P(k) wedge P(k+1) wedge P(k+2)$. Call this conjunction $Q(k)$; then you have shown all the elements of $Q(8) = P(8) wedge P(9) wedge P(10)$. For $Q(k) rightarrow Q(k+1)$, if $P(k) wedge P(k+1) wedge P(k+2)$, then you already know $P(k+1)$ and $P(k+2)$ are true; and also, since $P(k)$ is true and you have shown $P(k) rightarrow P(k+3)$, you also know $P(k+3)$. Therefore, $P(k+1) wedge P(k+2) wedge P(k+3)$, in other words, $Q(k+1)$.
$endgroup$
– Daniel Schepler
18 mins ago
$begingroup$
Thanks for this! I think that clears up the idea of strong induction for me, which I was a little bit shaky with
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
Thanks for this! I think that clears up the idea of strong induction for me, which I was a little bit shaky with
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
Another way to organize the proof: show by "weak induction" that for all $k ge 8$, we have $P(k) wedge P(k+1) wedge P(k+2)$. Call this conjunction $Q(k)$; then you have shown all the elements of $Q(8) = P(8) wedge P(9) wedge P(10)$. For $Q(k) rightarrow Q(k+1)$, if $P(k) wedge P(k+1) wedge P(k+2)$, then you already know $P(k+1)$ and $P(k+2)$ are true; and also, since $P(k)$ is true and you have shown $P(k) rightarrow P(k+3)$, you also know $P(k+3)$. Therefore, $P(k+1) wedge P(k+2) wedge P(k+3)$, in other words, $Q(k+1)$.
$endgroup$
– Daniel Schepler
18 mins ago
$begingroup$
Another way to organize the proof: show by "weak induction" that for all $k ge 8$, we have $P(k) wedge P(k+1) wedge P(k+2)$. Call this conjunction $Q(k)$; then you have shown all the elements of $Q(8) = P(8) wedge P(9) wedge P(10)$. For $Q(k) rightarrow Q(k+1)$, if $P(k) wedge P(k+1) wedge P(k+2)$, then you already know $P(k+1)$ and $P(k+2)$ are true; and also, since $P(k)$ is true and you have shown $P(k) rightarrow P(k+3)$, you also know $P(k+3)$. Therefore, $P(k+1) wedge P(k+2) wedge P(k+3)$, in other words, $Q(k+1)$.
$endgroup$
– Daniel Schepler
18 mins ago
add a comment |
$begingroup$
Note that $P(N)$ does not imply $P(N+1)$ in any immediate way (e.g. it is not immediately clear why $17$ should have the property just because $16$ has the property ... though see the inductive proof I give a little later in this post).
So, if you have to use weak induction, the obvious thing to do is what your professor does, and do $3$ separate weak inductive proofs:
Show that $P(8)$, and show that for all $n$: $P(8+3n)Rightarrow P(8+3(n+1))$
Show that $P(9)$, and show that for all $n$: $P(9+3n)Rightarrow P(9+3(n+1))$
Show that $P(10)$, and show that for all $n$: $P(10+3n)Rightarrow P(10+3(n+1))$
Combined together, these proofs show that for all $n ge 8$: $P(n)$
Another possible weak inductive proof is this:
Show that $P(8)$, $P(9)$, and $P(10)$ hold. Now suppose $P(N)$ holds with $N ge 10$. Because $N ge 10$, we know that to form $N$, we need to either use at least one $5$, or (if we don't use any $5$'s at all), at least three $3$'s. But if $P(N)$ is formed using at least one $5$, then we can form $P(N+1)$ by taking away one $5$ and adding two $3$'s. And if we use at least three $3$ to form $P(N)$, then we can form $P(N+1)$ by taking away three $3$'s and adding two $5$'s. So, either way, we can form $P(N+1)$
Your method uses strong induction, and is of course a perfectly good mathematical proof as well ... but maybe your professor had insisted on you using weak induction?
$endgroup$
3
$begingroup$
Thanks! I just got an email back from him. He agrees now it is fine, but not a "conventional" way of doing the proof in his words. The main point of discrepancy was that, during lecture, he said "it cannot be done in that way, even under strong induction" which was the confusing part for us. We understood that it would take multiple proofs to do it under weak induction, but that was the main point of confusion. As a matter of fact, the way he did it in class was through a lot more reasoning instead of 3 separate weak inductive proofs, which is what led us to ask if this would work instead
$endgroup$
– Damian Vu
6 hours ago
1
$begingroup$
@DamianVu Cool! Did he do it using the other weak inductive proof I just added to my Answer?
$endgroup$
– Bram28
6 hours ago
1
$begingroup$
ah yes I didn't see that. That is exactly how he did it in class.
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
@DamianVu OK. But that is a different proof than what you described in your post. :)
$endgroup$
– Bram28
6 hours ago
1
$begingroup$
@DamianVu Oh! No, the professor was definitely wrong about that.
$endgroup$
– Bram28
2 hours ago
|
show 1 more comment
$begingroup$
Note that $P(N)$ does not imply $P(N+1)$ in any immediate way (e.g. it is not immediately clear why $17$ should have the property just because $16$ has the property ... though see the inductive proof I give a little later in this post).
So, if you have to use weak induction, the obvious thing to do is what your professor does, and do $3$ separate weak inductive proofs:
Show that $P(8)$, and show that for all $n$: $P(8+3n)Rightarrow P(8+3(n+1))$
Show that $P(9)$, and show that for all $n$: $P(9+3n)Rightarrow P(9+3(n+1))$
Show that $P(10)$, and show that for all $n$: $P(10+3n)Rightarrow P(10+3(n+1))$
Combined together, these proofs show that for all $n ge 8$: $P(n)$
Another possible weak inductive proof is this:
Show that $P(8)$, $P(9)$, and $P(10)$ hold. Now suppose $P(N)$ holds with $N ge 10$. Because $N ge 10$, we know that to form $N$, we need to either use at least one $5$, or (if we don't use any $5$'s at all), at least three $3$'s. But if $P(N)$ is formed using at least one $5$, then we can form $P(N+1)$ by taking away one $5$ and adding two $3$'s. And if we use at least three $3$ to form $P(N)$, then we can form $P(N+1)$ by taking away three $3$'s and adding two $5$'s. So, either way, we can form $P(N+1)$
Your method uses strong induction, and is of course a perfectly good mathematical proof as well ... but maybe your professor had insisted on you using weak induction?
$endgroup$
3
$begingroup$
Thanks! I just got an email back from him. He agrees now it is fine, but not a "conventional" way of doing the proof in his words. The main point of discrepancy was that, during lecture, he said "it cannot be done in that way, even under strong induction" which was the confusing part for us. We understood that it would take multiple proofs to do it under weak induction, but that was the main point of confusion. As a matter of fact, the way he did it in class was through a lot more reasoning instead of 3 separate weak inductive proofs, which is what led us to ask if this would work instead
$endgroup$
– Damian Vu
6 hours ago
1
$begingroup$
@DamianVu Cool! Did he do it using the other weak inductive proof I just added to my Answer?
$endgroup$
– Bram28
6 hours ago
1
$begingroup$
ah yes I didn't see that. That is exactly how he did it in class.
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
@DamianVu OK. But that is a different proof than what you described in your post. :)
$endgroup$
– Bram28
6 hours ago
1
$begingroup$
@DamianVu Oh! No, the professor was definitely wrong about that.
$endgroup$
– Bram28
2 hours ago
|
show 1 more comment
$begingroup$
Note that $P(N)$ does not imply $P(N+1)$ in any immediate way (e.g. it is not immediately clear why $17$ should have the property just because $16$ has the property ... though see the inductive proof I give a little later in this post).
So, if you have to use weak induction, the obvious thing to do is what your professor does, and do $3$ separate weak inductive proofs:
Show that $P(8)$, and show that for all $n$: $P(8+3n)Rightarrow P(8+3(n+1))$
Show that $P(9)$, and show that for all $n$: $P(9+3n)Rightarrow P(9+3(n+1))$
Show that $P(10)$, and show that for all $n$: $P(10+3n)Rightarrow P(10+3(n+1))$
Combined together, these proofs show that for all $n ge 8$: $P(n)$
Another possible weak inductive proof is this:
Show that $P(8)$, $P(9)$, and $P(10)$ hold. Now suppose $P(N)$ holds with $N ge 10$. Because $N ge 10$, we know that to form $N$, we need to either use at least one $5$, or (if we don't use any $5$'s at all), at least three $3$'s. But if $P(N)$ is formed using at least one $5$, then we can form $P(N+1)$ by taking away one $5$ and adding two $3$'s. And if we use at least three $3$ to form $P(N)$, then we can form $P(N+1)$ by taking away three $3$'s and adding two $5$'s. So, either way, we can form $P(N+1)$
Your method uses strong induction, and is of course a perfectly good mathematical proof as well ... but maybe your professor had insisted on you using weak induction?
$endgroup$
Note that $P(N)$ does not imply $P(N+1)$ in any immediate way (e.g. it is not immediately clear why $17$ should have the property just because $16$ has the property ... though see the inductive proof I give a little later in this post).
So, if you have to use weak induction, the obvious thing to do is what your professor does, and do $3$ separate weak inductive proofs:
Show that $P(8)$, and show that for all $n$: $P(8+3n)Rightarrow P(8+3(n+1))$
Show that $P(9)$, and show that for all $n$: $P(9+3n)Rightarrow P(9+3(n+1))$
Show that $P(10)$, and show that for all $n$: $P(10+3n)Rightarrow P(10+3(n+1))$
Combined together, these proofs show that for all $n ge 8$: $P(n)$
Another possible weak inductive proof is this:
Show that $P(8)$, $P(9)$, and $P(10)$ hold. Now suppose $P(N)$ holds with $N ge 10$. Because $N ge 10$, we know that to form $N$, we need to either use at least one $5$, or (if we don't use any $5$'s at all), at least three $3$'s. But if $P(N)$ is formed using at least one $5$, then we can form $P(N+1)$ by taking away one $5$ and adding two $3$'s. And if we use at least three $3$ to form $P(N)$, then we can form $P(N+1)$ by taking away three $3$'s and adding two $5$'s. So, either way, we can form $P(N+1)$
Your method uses strong induction, and is of course a perfectly good mathematical proof as well ... but maybe your professor had insisted on you using weak induction?
edited 6 hours ago
answered 6 hours ago
Bram28Bram28
61.9k44793
61.9k44793
3
$begingroup$
Thanks! I just got an email back from him. He agrees now it is fine, but not a "conventional" way of doing the proof in his words. The main point of discrepancy was that, during lecture, he said "it cannot be done in that way, even under strong induction" which was the confusing part for us. We understood that it would take multiple proofs to do it under weak induction, but that was the main point of confusion. As a matter of fact, the way he did it in class was through a lot more reasoning instead of 3 separate weak inductive proofs, which is what led us to ask if this would work instead
$endgroup$
– Damian Vu
6 hours ago
1
$begingroup$
@DamianVu Cool! Did he do it using the other weak inductive proof I just added to my Answer?
$endgroup$
– Bram28
6 hours ago
1
$begingroup$
ah yes I didn't see that. That is exactly how he did it in class.
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
@DamianVu OK. But that is a different proof than what you described in your post. :)
$endgroup$
– Bram28
6 hours ago
1
$begingroup$
@DamianVu Oh! No, the professor was definitely wrong about that.
$endgroup$
– Bram28
2 hours ago
|
show 1 more comment
3
$begingroup$
Thanks! I just got an email back from him. He agrees now it is fine, but not a "conventional" way of doing the proof in his words. The main point of discrepancy was that, during lecture, he said "it cannot be done in that way, even under strong induction" which was the confusing part for us. We understood that it would take multiple proofs to do it under weak induction, but that was the main point of confusion. As a matter of fact, the way he did it in class was through a lot more reasoning instead of 3 separate weak inductive proofs, which is what led us to ask if this would work instead
$endgroup$
– Damian Vu
6 hours ago
1
$begingroup$
@DamianVu Cool! Did he do it using the other weak inductive proof I just added to my Answer?
$endgroup$
– Bram28
6 hours ago
1
$begingroup$
ah yes I didn't see that. That is exactly how he did it in class.
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
@DamianVu OK. But that is a different proof than what you described in your post. :)
$endgroup$
– Bram28
6 hours ago
1
$begingroup$
@DamianVu Oh! No, the professor was definitely wrong about that.
$endgroup$
– Bram28
2 hours ago
3
3
$begingroup$
Thanks! I just got an email back from him. He agrees now it is fine, but not a "conventional" way of doing the proof in his words. The main point of discrepancy was that, during lecture, he said "it cannot be done in that way, even under strong induction" which was the confusing part for us. We understood that it would take multiple proofs to do it under weak induction, but that was the main point of confusion. As a matter of fact, the way he did it in class was through a lot more reasoning instead of 3 separate weak inductive proofs, which is what led us to ask if this would work instead
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
Thanks! I just got an email back from him. He agrees now it is fine, but not a "conventional" way of doing the proof in his words. The main point of discrepancy was that, during lecture, he said "it cannot be done in that way, even under strong induction" which was the confusing part for us. We understood that it would take multiple proofs to do it under weak induction, but that was the main point of confusion. As a matter of fact, the way he did it in class was through a lot more reasoning instead of 3 separate weak inductive proofs, which is what led us to ask if this would work instead
$endgroup$
– Damian Vu
6 hours ago
1
1
$begingroup$
@DamianVu Cool! Did he do it using the other weak inductive proof I just added to my Answer?
$endgroup$
– Bram28
6 hours ago
$begingroup$
@DamianVu Cool! Did he do it using the other weak inductive proof I just added to my Answer?
$endgroup$
– Bram28
6 hours ago
1
1
$begingroup$
ah yes I didn't see that. That is exactly how he did it in class.
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
ah yes I didn't see that. That is exactly how he did it in class.
$endgroup$
– Damian Vu
6 hours ago
$begingroup$
@DamianVu OK. But that is a different proof than what you described in your post. :)
$endgroup$
– Bram28
6 hours ago
$begingroup$
@DamianVu OK. But that is a different proof than what you described in your post. :)
$endgroup$
– Bram28
6 hours ago
1
1
$begingroup$
@DamianVu Oh! No, the professor was definitely wrong about that.
$endgroup$
– Bram28
2 hours ago
$begingroup$
@DamianVu Oh! No, the professor was definitely wrong about that.
$endgroup$
– Bram28
2 hours ago
|
show 1 more comment
$begingroup$
If the property is true for all $k$ such that $$8le kle n,$$ where $10le n$, then it is true for $n-2$ and is true for $n+1$, and for all $k$ such that
$$8le kle n+1.$$
$endgroup$
add a comment |
$begingroup$
If the property is true for all $k$ such that $$8le kle n,$$ where $10le n$, then it is true for $n-2$ and is true for $n+1$, and for all $k$ such that
$$8le kle n+1.$$
$endgroup$
add a comment |
$begingroup$
If the property is true for all $k$ such that $$8le kle n,$$ where $10le n$, then it is true for $n-2$ and is true for $n+1$, and for all $k$ such that
$$8le kle n+1.$$
$endgroup$
If the property is true for all $k$ such that $$8le kle n,$$ where $10le n$, then it is true for $n-2$ and is true for $n+1$, and for all $k$ such that
$$8le kle n+1.$$
answered 7 hours ago
Yves DaoustYves Daoust
127k673226
127k673226
add a comment |
add a comment |
$begingroup$
Forget about induction for a second.
Let us say $P(K)$ holds iff there exist $c,d geq 0$ such that $K=3c+5d$.
Your goal is to prove that $P(K)$ holds for all $K geq 8$.
If you would only want to prove $P(8)$ (for example) then you could just write a proof for that ($8=3+5$). However, you can't write a proof for $P(K)$ for all $K geq 8$ because there simply is not enough time to do that. What you can do instead is to write a computer program (algorithm) which gets $K geq 8$ as input and outputs a proof for $P(K)$. More specifically, on input $K$ it outputs two numbers $c,d$ such that $K=3c+5d$.
Indeed, your question already contains such a program $A$:
- if $K = 8$ then output $(1,1)$
- if $K = 9$ then output $(3,0)$
- if $K = 10$ then output $(0,2)$
- if $K > 10$ then compute $(c,d) = A(K-3)$ and output $(c + 1, d)$
Now, we need to argue that $A$ works correctly. For the three base cases this is obvious. For the recursive case we argue as follows. Let $K > 10$ and let $(c,d) = A(K-3)$. The algorithm $A$ is correct for input $K$ if
$$ K = 3(c+1) + 5d $$
As you have already observed: if $A(K-3)$ is correct, i.e. $K-3 = 3c+5d$, then the above holds as well. Therefore we have reduced proving that $A(K)$ is correct to proving that $A(K-3)$ is correct. Observe that $K-3 > 7$ because otherwise it would contradict our assumption $K > 10$. If $K-3 leq 10$ then correctness follows from the base cases. Otherwise ($K-3>10$), we can apply the same argument to see that: $A(K-3)$ is correct if $A(K-6)$ is correct. If $K-6$ is still larger than 10 we can apply the same argument and check whether $A(K-9)$ is correct and so on... it is not difficult to argue that eventually a base case is reached. Therefore $A$ works correctly.
My point is that the principle of induction is not some mysterious proof technique but naturally follows from the previous algorithmic perspective. Essentially, a proof by induction is a compact representation of a recursive algorithm which generates the proofs and a proof of correctness of that algorithm. The take-away message is: if you do a proof by induction and you are not certain whether it is sound, try to articulate the recursive algorithm which produces the proofs, try the algorithm out for some cases and then prove its correctness by using a chain of reductions as shown here (don't forget to argue that a base case is always reached eventually).
$endgroup$
$begingroup$
See also the Curry-Howard correspondence: under this correspondence, a proof by induction becomes precisely a special case of a recursive function.
$endgroup$
– Daniel Schepler
21 mins ago
add a comment |
$begingroup$
Forget about induction for a second.
Let us say $P(K)$ holds iff there exist $c,d geq 0$ such that $K=3c+5d$.
Your goal is to prove that $P(K)$ holds for all $K geq 8$.
If you would only want to prove $P(8)$ (for example) then you could just write a proof for that ($8=3+5$). However, you can't write a proof for $P(K)$ for all $K geq 8$ because there simply is not enough time to do that. What you can do instead is to write a computer program (algorithm) which gets $K geq 8$ as input and outputs a proof for $P(K)$. More specifically, on input $K$ it outputs two numbers $c,d$ such that $K=3c+5d$.
Indeed, your question already contains such a program $A$:
- if $K = 8$ then output $(1,1)$
- if $K = 9$ then output $(3,0)$
- if $K = 10$ then output $(0,2)$
- if $K > 10$ then compute $(c,d) = A(K-3)$ and output $(c + 1, d)$
Now, we need to argue that $A$ works correctly. For the three base cases this is obvious. For the recursive case we argue as follows. Let $K > 10$ and let $(c,d) = A(K-3)$. The algorithm $A$ is correct for input $K$ if
$$ K = 3(c+1) + 5d $$
As you have already observed: if $A(K-3)$ is correct, i.e. $K-3 = 3c+5d$, then the above holds as well. Therefore we have reduced proving that $A(K)$ is correct to proving that $A(K-3)$ is correct. Observe that $K-3 > 7$ because otherwise it would contradict our assumption $K > 10$. If $K-3 leq 10$ then correctness follows from the base cases. Otherwise ($K-3>10$), we can apply the same argument to see that: $A(K-3)$ is correct if $A(K-6)$ is correct. If $K-6$ is still larger than 10 we can apply the same argument and check whether $A(K-9)$ is correct and so on... it is not difficult to argue that eventually a base case is reached. Therefore $A$ works correctly.
My point is that the principle of induction is not some mysterious proof technique but naturally follows from the previous algorithmic perspective. Essentially, a proof by induction is a compact representation of a recursive algorithm which generates the proofs and a proof of correctness of that algorithm. The take-away message is: if you do a proof by induction and you are not certain whether it is sound, try to articulate the recursive algorithm which produces the proofs, try the algorithm out for some cases and then prove its correctness by using a chain of reductions as shown here (don't forget to argue that a base case is always reached eventually).
$endgroup$
$begingroup$
See also the Curry-Howard correspondence: under this correspondence, a proof by induction becomes precisely a special case of a recursive function.
$endgroup$
– Daniel Schepler
21 mins ago
add a comment |
$begingroup$
Forget about induction for a second.
Let us say $P(K)$ holds iff there exist $c,d geq 0$ such that $K=3c+5d$.
Your goal is to prove that $P(K)$ holds for all $K geq 8$.
If you would only want to prove $P(8)$ (for example) then you could just write a proof for that ($8=3+5$). However, you can't write a proof for $P(K)$ for all $K geq 8$ because there simply is not enough time to do that. What you can do instead is to write a computer program (algorithm) which gets $K geq 8$ as input and outputs a proof for $P(K)$. More specifically, on input $K$ it outputs two numbers $c,d$ such that $K=3c+5d$.
Indeed, your question already contains such a program $A$:
- if $K = 8$ then output $(1,1)$
- if $K = 9$ then output $(3,0)$
- if $K = 10$ then output $(0,2)$
- if $K > 10$ then compute $(c,d) = A(K-3)$ and output $(c + 1, d)$
Now, we need to argue that $A$ works correctly. For the three base cases this is obvious. For the recursive case we argue as follows. Let $K > 10$ and let $(c,d) = A(K-3)$. The algorithm $A$ is correct for input $K$ if
$$ K = 3(c+1) + 5d $$
As you have already observed: if $A(K-3)$ is correct, i.e. $K-3 = 3c+5d$, then the above holds as well. Therefore we have reduced proving that $A(K)$ is correct to proving that $A(K-3)$ is correct. Observe that $K-3 > 7$ because otherwise it would contradict our assumption $K > 10$. If $K-3 leq 10$ then correctness follows from the base cases. Otherwise ($K-3>10$), we can apply the same argument to see that: $A(K-3)$ is correct if $A(K-6)$ is correct. If $K-6$ is still larger than 10 we can apply the same argument and check whether $A(K-9)$ is correct and so on... it is not difficult to argue that eventually a base case is reached. Therefore $A$ works correctly.
My point is that the principle of induction is not some mysterious proof technique but naturally follows from the previous algorithmic perspective. Essentially, a proof by induction is a compact representation of a recursive algorithm which generates the proofs and a proof of correctness of that algorithm. The take-away message is: if you do a proof by induction and you are not certain whether it is sound, try to articulate the recursive algorithm which produces the proofs, try the algorithm out for some cases and then prove its correctness by using a chain of reductions as shown here (don't forget to argue that a base case is always reached eventually).
$endgroup$
Forget about induction for a second.
Let us say $P(K)$ holds iff there exist $c,d geq 0$ such that $K=3c+5d$.
Your goal is to prove that $P(K)$ holds for all $K geq 8$.
If you would only want to prove $P(8)$ (for example) then you could just write a proof for that ($8=3+5$). However, you can't write a proof for $P(K)$ for all $K geq 8$ because there simply is not enough time to do that. What you can do instead is to write a computer program (algorithm) which gets $K geq 8$ as input and outputs a proof for $P(K)$. More specifically, on input $K$ it outputs two numbers $c,d$ such that $K=3c+5d$.
Indeed, your question already contains such a program $A$:
- if $K = 8$ then output $(1,1)$
- if $K = 9$ then output $(3,0)$
- if $K = 10$ then output $(0,2)$
- if $K > 10$ then compute $(c,d) = A(K-3)$ and output $(c + 1, d)$
Now, we need to argue that $A$ works correctly. For the three base cases this is obvious. For the recursive case we argue as follows. Let $K > 10$ and let $(c,d) = A(K-3)$. The algorithm $A$ is correct for input $K$ if
$$ K = 3(c+1) + 5d $$
As you have already observed: if $A(K-3)$ is correct, i.e. $K-3 = 3c+5d$, then the above holds as well. Therefore we have reduced proving that $A(K)$ is correct to proving that $A(K-3)$ is correct. Observe that $K-3 > 7$ because otherwise it would contradict our assumption $K > 10$. If $K-3 leq 10$ then correctness follows from the base cases. Otherwise ($K-3>10$), we can apply the same argument to see that: $A(K-3)$ is correct if $A(K-6)$ is correct. If $K-6$ is still larger than 10 we can apply the same argument and check whether $A(K-9)$ is correct and so on... it is not difficult to argue that eventually a base case is reached. Therefore $A$ works correctly.
My point is that the principle of induction is not some mysterious proof technique but naturally follows from the previous algorithmic perspective. Essentially, a proof by induction is a compact representation of a recursive algorithm which generates the proofs and a proof of correctness of that algorithm. The take-away message is: if you do a proof by induction and you are not certain whether it is sound, try to articulate the recursive algorithm which produces the proofs, try the algorithm out for some cases and then prove its correctness by using a chain of reductions as shown here (don't forget to argue that a base case is always reached eventually).
answered 1 hour ago
Maurice C.Maurice C.
313
313
$begingroup$
See also the Curry-Howard correspondence: under this correspondence, a proof by induction becomes precisely a special case of a recursive function.
$endgroup$
– Daniel Schepler
21 mins ago
add a comment |
$begingroup$
See also the Curry-Howard correspondence: under this correspondence, a proof by induction becomes precisely a special case of a recursive function.
$endgroup$
– Daniel Schepler
21 mins ago
$begingroup$
See also the Curry-Howard correspondence: under this correspondence, a proof by induction becomes precisely a special case of a recursive function.
$endgroup$
– Daniel Schepler
21 mins ago
$begingroup$
See also the Curry-Howard correspondence: under this correspondence, a proof by induction becomes precisely a special case of a recursive function.
$endgroup$
– Daniel Schepler
21 mins ago
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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%2f3101342%2fare-we-properly-using-mathematical-induction%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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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
15
$begingroup$
Your argument is fine.
$endgroup$
– José Carlos Santos
8 hours ago
5
$begingroup$
You might want to emphasize that your hypothesis holds for all $K$ with $8leq Kleq N$. Otherwise this is fine. Using weak induction requires you to do induction on three sequences. But your hypothesis makes this an argument by strong induction, which enables you to do it on just one sequence.
$endgroup$
– Servaes
8 hours ago
1
$begingroup$
@JoséCarlosSantos The proof is correct, but I'm assuming the professor was implying that they needed to use weak induction to solve this problem. Perhaps they have not axiomatically shown that they are equivalent yet.
$endgroup$
– Don Thousand
8 hours ago
6
$begingroup$
The other commenters are right: this is an issue of ordinary vs. strong induction.
$endgroup$
– Randall
8 hours ago
6
$begingroup$
"Let $N>10$" You should change that into "let $Ngeq10$".
$endgroup$
– drhab
8 hours ago