Mixing
Understanding this proof by strong induction that each n≥12 is n = 3a + 7b for some natural numbers (a,b)
$begingroup$
Thm: for all natural numbers $n≥12$, $n = 3a +7b$, for some natural numbers $a$, and $b$. (Natural numbers include 0 here).
My question about the following proof has to do with why we need to show 4 different cases, instead just the last one. I expand this question further at the end.
Proof: By strong induction
For all natural numbers $n$, such that $n≥12$, let $P(n)$ be the statement "$n = 3a +7b$."
Let $n$ be an arbitrary natural number such that $n≥12$. Suppose for every $12 ≤ k < n, P(k)$ is true.
We consider 4 cases.
Case#1: $n = 12$
$$n = 3(4) + 0(7)$$
Case#2: $n = 13$
$$n = 3(2) + 7(1)$$
Case#3: $n = 14$
$$n = 3(0) + 7(2)$$
Case#4: $n≥15$
Then $(n−3)≥12$ and $(n−3)<n$. It follows from the induction hypothesis that $P(n-3)$ is true, and so we can choose some $a$ and $b$ such that $3a + 7b = (n-3)$. Thus, $n = 3a +7b +3 = 3(a+1) +7b$. Since $a+1$ is a natural number, it follows that $P(n)$ is true, and the implication follows. Since $n$ was arbitrary, it is true for all such, and the theorem follows.
My question: Why do we need cases $1, 2,$ and $3$? Why can't I just assume that $P(k)$ is true for all $12 ≤ k < n, P(k)$, and then start with case 4 that says $n≥15$. Since I have assumed $P(k)$ for all values less than $n$, I should be able to draw the same conclusions, as none seem dependent on the previous 3 cases.
If we need a "base case" to start the induction process, then why can't we just use case 1 and case 4, cutting out 2 and 3? Any help understanding this would be greatly appreciated.
Edit: changed $c$ to $b$, also added MathJax delimiters
elementary-number-theory induction proof-explanation
edited Jan 15 at 18:23
Martin Sleziak
44.6k10118272
asked Nov 3 '16 at 12:53
IgnorantCuriosityIgnorantCuriosity
5852519
$endgroup$
add a comment |
$begingroup$
Thm: for all natural numbers $n≥12$, $n = 3a +7b$, for some natural numbers $a$, and $b$. (Natural numbers include 0 here).
My question about the following proof has to do with why we need to show 4 different cases, instead just the last one. I expand this question further at the end.
Proof: By strong induction
For all natural numbers $n$, such that $n≥12$, let $P(n)$ be the statement "$n = 3a +7b$."
Let $n$ be an arbitrary natural number such that $n≥12$. Suppose for every $12 ≤ k < n, P(k)$ is true.
We consider 4 cases.
Case#1: $n = 12$
$$n = 3(4) + 0(7)$$
Case#2: $n = 13$
$$n = 3(2) + 7(1)$$
Case#3: $n = 14$
$$n = 3(0) + 7(2)$$
Case#4: $n≥15$
Then $(n−3)≥12$ and $(n−3)<n$. It follows from the induction hypothesis that $P(n-3)$ is true, and so we can choose some $a$ and $b$ such that $3a + 7b = (n-3)$. Thus, $n = 3a +7b +3 = 3(a+1) +7b$. Since $a+1$ is a natural number, it follows that $P(n)$ is true, and the implication follows. Since $n$ was arbitrary, it is true for all such, and the theorem follows.
My question: Why do we need cases $1, 2,$ and $3$? Why can't I just assume that $P(k)$ is true for all $12 ≤ k < n, P(k)$, and then start with case 4 that says $n≥15$. Since I have assumed $P(k)$ for all values less than $n$, I should be able to draw the same conclusions, as none seem dependent on the previous 3 cases.
If we need a "base case" to start the induction process, then why can't we just use case 1 and case 4, cutting out 2 and 3? Any help understanding this would be greatly appreciated.
Edit: changed $c$ to $b$, also added MathJax delimiters
elementary-number-theory induction proof-explanation
edited Jan 15 at 18:23
Martin Sleziak
44.6k10118272
asked Nov 3 '16 at 12:53
IgnorantCuriosityIgnorantCuriosity
5852519
$endgroup$
$begingroup$
Well, try it. You need some base case...what do you propose?
$endgroup$
– lulu
Nov 3 '16 at 12:54
2
$begingroup$
Just to stress: it is not true that the fact that $n$ can be written as you want implies that $n+1$ can. $3=3times 1+7times 0$ but $4$ can't be written in the desired form.
$endgroup$
– lulu
Nov 3 '16 at 12:59
$begingroup$
Note: if you don't put it inside MathJax then $<$ is interpreted as the start of an HTML tag, and everything on the line after it does not show.
$endgroup$
– Graham Kemp
Nov 3 '16 at 13:02
$begingroup$
If the induction step were $P(n) implies P(n+1)$ we'd need only one base case. If the induction step were $P(n) implies P(n+2)$ then one base case would only prove it true for every other number and we'd need two base cases to prove for all numbers. Here your induction step is $P(n) implies P(n + 3)$ so one base case will only prove it for one third of the numbers. $P(12) implies P(n equiv 0 mod 3;n ge 12)$ which is not enough. $P(13) implies P(n equiv 1mod 3; n > 12)$. and we need $P(14)$ to get $P(nequiv 2 mod 3; n > 12)$.
$endgroup$
– fleablood
Nov 3 '16 at 18:58
$begingroup$
I remmeber the Chicken McNugget Theorem link
$endgroup$
– Ricardo Largaespada
Nov 4 '16 at 0:09
add a comment |
$begingroup$
Thm: for all natural numbers $n≥12$, $n = 3a +7b$, for some natural numbers $a$, and $b$. (Natural numbers include 0 here).
My question about the following proof has to do with why we need to show 4 different cases, instead just the last one. I expand this question further at the end.
Proof: By strong induction
For all natural numbers $n$, such that $n≥12$, let $P(n)$ be the statement "$n = 3a +7b$."
Let $n$ be an arbitrary natural number such that $n≥12$. Suppose for every $12 ≤ k < n, P(k)$ is true.
We consider 4 cases.
Case#1: $n = 12$
$$n = 3(4) + 0(7)$$
Case#2: $n = 13$
$$n = 3(2) + 7(1)$$
Case#3: $n = 14$
$$n = 3(0) + 7(2)$$
Case#4: $n≥15$
Then $(n−3)≥12$ and $(n−3)<n$. It follows from the induction hypothesis that $P(n-3)$ is true, and so we can choose some $a$ and $b$ such that $3a + 7b = (n-3)$. Thus, $n = 3a +7b +3 = 3(a+1) +7b$. Since $a+1$ is a natural number, it follows that $P(n)$ is true, and the implication follows. Since $n$ was arbitrary, it is true for all such, and the theorem follows.
My question: Why do we need cases $1, 2,$ and $3$? Why can't I just assume that $P(k)$ is true for all $12 ≤ k < n, P(k)$, and then start with case 4 that says $n≥15$. Since I have assumed $P(k)$ for all values less than $n$, I should be able to draw the same conclusions, as none seem dependent on the previous 3 cases.
If we need a "base case" to start the induction process, then why can't we just use case 1 and case 4, cutting out 2 and 3? Any help understanding this would be greatly appreciated.
Edit: changed $c$ to $b$, also added MathJax delimiters
elementary-number-theory induction proof-explanation
edited Jan 15 at 18:23
Martin Sleziak
44.6k10118272
asked Nov 3 '16 at 12:53
IgnorantCuriosityIgnorantCuriosity
5852519
$endgroup$
Thm: for all natural numbers $n≥12$, $n = 3a +7b$, for some natural numbers $a$, and $b$. (Natural numbers include 0 here).
My question about the following proof has to do with why we need to show 4 different cases, instead just the last one. I expand this question further at the end.
Proof: By strong induction
For all natural numbers $n$, such that $n≥12$, let $P(n)$ be the statement "$n = 3a +7b$."
Let $n$ be an arbitrary natural number such that $n≥12$. Suppose for every $12 ≤ k < n, P(k)$ is true.
We consider 4 cases.
Case#1: $n = 12$
$$n = 3(4) + 0(7)$$
Case#2: $n = 13$
$$n = 3(2) + 7(1)$$
Case#3: $n = 14$
$$n = 3(0) + 7(2)$$
Case#4: $n≥15$
Then $(n−3)≥12$ and $(n−3)<n$. It follows from the induction hypothesis that $P(n-3)$ is true, and so we can choose some $a$ and $b$ such that $3a + 7b = (n-3)$. Thus, $n = 3a +7b +3 = 3(a+1) +7b$. Since $a+1$ is a natural number, it follows that $P(n)$ is true, and the implication follows. Since $n$ was arbitrary, it is true for all such, and the theorem follows.
My question: Why do we need cases $1, 2,$ and $3$? Why can't I just assume that $P(k)$ is true for all $12 ≤ k < n, P(k)$, and then start with case 4 that says $n≥15$. Since I have assumed $P(k)$ for all values less than $n$, I should be able to draw the same conclusions, as none seem dependent on the previous 3 cases.
If we need a "base case" to start the induction process, then why can't we just use case 1 and case 4, cutting out 2 and 3? Any help understanding this would be greatly appreciated.
Edit: changed $c$ to $b$, also added MathJax delimiters
elementary-number-theory induction proof-explanation
elementary-number-theory induction proof-explanation
edited Jan 15 at 18:23
Martin Sleziak
44.6k10118272
asked Nov 3 '16 at 12:53
IgnorantCuriosityIgnorantCuriosity
5852519
edited Jan 15 at 18:23
Martin Sleziak
44.6k10118272
asked Nov 3 '16 at 12:53
IgnorantCuriosityIgnorantCuriosity
5852519
edited Jan 15 at 18:23
Martin Sleziak
44.6k10118272
edited Jan 15 at 18:23
Martin Sleziak
44.6k10118272
edited Jan 15 at 18:23
Martin Sleziak
44.6k10118272
44.6k10118272
asked Nov 3 '16 at 12:53
IgnorantCuriosityIgnorantCuriosity
5852519
asked Nov 3 '16 at 12:53
IgnorantCuriosityIgnorantCuriosity
5852519
asked Nov 3 '16 at 12:53
IgnorantCuriosityIgnorantCuriosity
5852519
5852519
$begingroup$
Well, try it. You need some base case...what do you propose?
$endgroup$
– lulu
Nov 3 '16 at 12:54
2
$begingroup$
Just to stress: it is not true that the fact that $n$ can be written as you want implies that $n+1$ can. $3=3times 1+7times 0$ but $4$ can't be written in the desired form.
$endgroup$
– lulu
Nov 3 '16 at 12:59
$begingroup$
Note: if you don't put it inside MathJax then $<$ is interpreted as the start of an HTML tag, and everything on the line after it does not show.
$endgroup$
– Graham Kemp
Nov 3 '16 at 13:02
$begingroup$
If the induction step were $P(n) implies P(n+1)$ we'd need only one base case. If the induction step were $P(n) implies P(n+2)$ then one base case would only prove it true for every other number and we'd need two base cases to prove for all numbers. Here your induction step is $P(n) implies P(n + 3)$ so one base case will only prove it for one third of the numbers. $P(12) implies P(n equiv 0 mod 3;n ge 12)$ which is not enough. $P(13) implies P(n equiv 1mod 3; n > 12)$. and we need $P(14)$ to get $P(nequiv 2 mod 3; n > 12)$.
$endgroup$
– fleablood
Nov 3 '16 at 18:58
$begingroup$
I remmeber the Chicken McNugget Theorem link
$endgroup$
– Ricardo Largaespada
Nov 4 '16 at 0:09
add a comment |
$begingroup$
Well, try it. You need some base case...what do you propose?
$endgroup$
– lulu
Nov 3 '16 at 12:54
2
$begingroup$
Just to stress: it is not true that the fact that $n$ can be written as you want implies that $n+1$ can. $3=3times 1+7times 0$ but $4$ can't be written in the desired form.
$endgroup$
– lulu
Nov 3 '16 at 12:59
$begingroup$
Note: if you don't put it inside MathJax then $<$ is interpreted as the start of an HTML tag, and everything on the line after it does not show.
$endgroup$
– Graham Kemp
Nov 3 '16 at 13:02
$begingroup$
If the induction step were $P(n) implies P(n+1)$ we'd need only one base case. If the induction step were $P(n) implies P(n+2)$ then one base case would only prove it true for every other number and we'd need two base cases to prove for all numbers. Here your induction step is $P(n) implies P(n + 3)$ so one base case will only prove it for one third of the numbers. $P(12) implies P(n equiv 0 mod 3;n ge 12)$ which is not enough. $P(13) implies P(n equiv 1mod 3; n > 12)$. and we need $P(14)$ to get $P(nequiv 2 mod 3; n > 12)$.
$endgroup$
– fleablood
Nov 3 '16 at 18:58
$begingroup$
I remmeber the Chicken McNugget Theorem link
$endgroup$
– Ricardo Largaespada
Nov 4 '16 at 0:09
$begingroup$
Well, try it. You need some base case...what do you propose?
$endgroup$
– lulu
Nov 3 '16 at 12:54
$begingroup$
Well, try it. You need some base case...what do you propose?
$endgroup$
– lulu
Nov 3 '16 at 12:54
2
2
$begingroup$
Just to stress: it is not true that the fact that $n$ can be written as you want implies that $n+1$ can. $3=3times 1+7times 0$ but $4$ can't be written in the desired form.
$endgroup$
– lulu
Nov 3 '16 at 12:59
$begingroup$
Just to stress: it is not true that the fact that $n$ can be written as you want implies that $n+1$ can. $3=3times 1+7times 0$ but $4$ can't be written in the desired form.
$endgroup$
– lulu
Nov 3 '16 at 12:59
$begingroup$
Note: if you don't put it inside MathJax then $<$ is interpreted as the start of an HTML tag, and everything on the line after it does not show.
$endgroup$
– Graham Kemp
Nov 3 '16 at 13:02
$begingroup$
Note: if you don't put it inside MathJax then $<$ is interpreted as the start of an HTML tag, and everything on the line after it does not show.
$endgroup$
– Graham Kemp
Nov 3 '16 at 13:02
$begingroup$
If the induction step were $P(n) implies P(n+1)$ we'd need only one base case. If the induction step were $P(n) implies P(n+2)$ then one base case would only prove it true for every other number and we'd need two base cases to prove for all numbers. Here your induction step is $P(n) implies P(n + 3)$ so one base case will only prove it for one third of the numbers. $P(12) implies P(n equiv 0 mod 3;n ge 12)$ which is not enough. $P(13) implies P(n equiv 1mod 3; n > 12)$. and we need $P(14)$ to get $P(nequiv 2 mod 3; n > 12)$.
$endgroup$
– fleablood
Nov 3 '16 at 18:58
$begingroup$
If the induction step were $P(n) implies P(n+1)$ we'd need only one base case. If the induction step were $P(n) implies P(n+2)$ then one base case would only prove it true for every other number and we'd need two base cases to prove for all numbers. Here your induction step is $P(n) implies P(n + 3)$ so one base case will only prove it for one third of the numbers. $P(12) implies P(n equiv 0 mod 3;n ge 12)$ which is not enough. $P(13) implies P(n equiv 1mod 3; n > 12)$. and we need $P(14)$ to get $P(nequiv 2 mod 3; n > 12)$.
$endgroup$
– fleablood
Nov 3 '16 at 18:58
$begingroup$
I remmeber the Chicken McNugget Theorem link
$endgroup$
– Ricardo Largaespada
Nov 4 '16 at 0:09
$begingroup$
I remmeber the Chicken McNugget Theorem link
$endgroup$
– Ricardo Largaespada
Nov 4 '16 at 0:09
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Let $P(k)$ be the statment ‘$k$ is a multiple of $3$’, and consider the following proposition:
For each integer $nge 12$, $P(n)$ is true.
We’ll use your approach to ‘prove’ it by induction. Let $n$ be a natural number such that $nge 15$, and suppose that $P(k)$ holds whenever $12le k<n$. Clearly $n-3ge 12$, so by hypothesis $n-3$ is a multiple of $3$. Thus, there is an integer $k$ such that $n-3=3k$. But then $n=3k+3=3(k+1)$ is also a multiploe of $3$, and the result follows by induction.
This is clearly nonsense: it certainly is not true that all natural numbers greater than or equal to $12$ are multiples of $3$. However, there is absolutely nothing wrong with the induction step that I just gave. If it were in fact the case that $nge 15$, and all integers $k$ such that $12le k<n$ were multiples of $3$, then it would indeed be true that $n$ was a multiple of $3$. The problem, of course, is that it is not true that all integers $k$ such that $12le k<n$ are multiples of $3$. In particular, $13$ is not, so when $n=16$ the induction step rests on a false premise: it works if $16-3=13$ is a multiple of $3$, but that is not in fact the case, and you’re not entitled to assume that it is.
In fact what the induction argument above actually shows is that if $12,13$, and $14$ were all multiples of $3$, then every natural number greater than or equal to $12$ would be a multiple of $3$. Unfortunately for that conclusion, $13$ and $14$ are not multiples of $3$. The induction step is only as good as its foundation: if you don’t verify enough base cases to make the induction step work, the argument is worthless.
In your case that means verifying $3$ cases, because the induction step for $n$ requires that the result be true for $n-3$. Thus, proving $P(15)$ by the induction step requires knowing that $P(12)$ is true, not just assuming it. Similarly, proving $P(16)$ by the induction step requires knowing that $P(13)$ is true, and proving $P(17)$ by the induction step requires knowing that $P(14)$ is true. There are no stages before $12,13$, and $14$: $P(12),P(13)$, and $P(14)$ are the foundation on which everything else rests. For example, $P(20)$ follows by the induction argument from $P(20-3)=P(17)$, which follows by the induction argument from $P(17-3)=P(14)$, but $P(14)$ doesn’t follow by the induction from $P(11)$, because $11$ isn’t in the domain of the argument (and in fact $P(11)$ is false).
answered Nov 3 '16 at 17:47
Brian M. ScottBrian M. Scott
458k38511913
$endgroup$
$begingroup$
Thank you for the reply. The last paragraph really helped tie some things together for me, but I feel I am still missing something very basic. For one, I don't understand why n-3 is necessarily a multiple of 3. That would only be the case if the n chosen was a multiple of 3, would it not? What about all the n values that are not multiple of 3? Second, and more fundamentally, I don't understand why we need n-3 in the induction step. Would this proof not also work if we showed P(12), set n≥13 and assumed n-1 was true?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 19:47
$begingroup$
@IgnorantCuriosity: You’re forgetting that the induction hypothesis was that $P(k)$ holds whenever $12le k<n$, where $n$ is some natural number greater than or equal to $15$. If $nge 15$, then $12le n-3<n$, so the induction hypothesis tells us that $n-3$ is a multiple of $3$. The problem here is of course that in fact the induction hypothesis isn’t true: we just assumed it. That’s exactly what you were proposing to do in your argument, and it’s no more valid there than it is here. \ Yes, this fallacious argument could have been carried out just as well as you suggest. However, in ...
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:54
$begingroup$
... order to show as clearly as possible what is wrong with the argument that you proposed in your question, I wanted to make it look as much like that argument as possible.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:55
$begingroup$
I apologize for my blindness, but I'm not seeing the connection between stating that (n-3) = 3a +7b, and stating that (n-3) = 3k. Would it be possible for you to spell this connection out for me?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 20:13
$begingroup$
@IgnorantCuriosity: Both are the assertion that $P(n-3)$ is true, where $P(k)$ is the assertion that $k$ has the specific property of interest. The properties are different, but they play exactly the same role in the arguments.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 20:15
|
show 4 more comments
$begingroup$
My question: Why do we need cases $1,2,$ and $3$? Why can't I just assume that $P(k)$ is true for all $k<n$, ...
Well, for starters, $P(11)$ and several others are false so the assumption is not justified.
If we need a "base case" to start the induction process, then why can't we just use case 1 and case 4, cutting out 2 and 3? Any help understanding this would be greatly appreciated.
Case 1 and Case 4 show that $P(12+3(0))$ and $forall nin Bbb N: big(bigwedgelimits_{k=0}^n P(12+3k)big)to P(12+3n+3)$, which proves by strong induction that $forall nin Bbb N: P(12+3n)$.
That is $P(12),P(15),P(18), P(21),ldots$
This misses out two thirds of what we need to show. The other two cases allow us to "fill in the gaps".
Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem?
Case 4 is an implication. An implication alone is not sufficient to prove its consequent.
Recall the difference between soundness and validity of a proof.
If you only assume a premise, then the conclusion may not be true. You have to demonstrate that the pemise is justified in order to prove the conclusion.
I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?
The predicate $P(12+3k)$ is that $exists a{in}Bbb N~exists b{in}Bbb N: (12+3k)=3a+7b$.
You can see that $P(12)$ is justified because $12=3(4)+7(0)$. That is that $a=4$ and $b=0$ are witnesses to $P(12)$.
We can also show that if $P(n_0)$ is true, then $P(n_0+3k)$ is true for every natural number $k$. Because $n_0=4a_0+7b_0 ~to~ (n_0+3k) = 3(a_0+k)+7(b_0)$ is sound.
Then if $P(12)$ is justified, and $forall k{in}Bbb N:P(n_0)to P(n_0+3k)$ is sound, then it follows that $forall kinBbb N: P(12+3k)$ is valid.
answered Nov 3 '16 at 13:15
Graham KempGraham Kemp
86k43378
$endgroup$
$begingroup$
Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem? I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?
$endgroup$
– IgnorantCuriosity
Nov 3 '16 at 15:48
$begingroup$
See the addition, @IgnorantCuriosity
$endgroup$
– Graham Kemp
Nov 3 '16 at 23:55
add a comment |
$begingroup$
Usually a proof by induction has this induction step:
Induction step: $P(n) implies P(n+1)$
So that and the the base case:
Base case: $P(b)$
will yield:
$P(b) implies P(b+1) implies P(b+2) implies ...$ and "any dope can see that will go on forever and cover every $P(n); n ge b$".
But in this exercise we do not have "$P(n) implies P(n+1)$" as our induction step. Instead we have:
Induction step: $P(n-3)implies P(n)$.
Or in other words:
Induction step: $P(n) implies P(n+3)$.
So if our base case is:
Base case: $P(14)$.
So we can conclude:
$P(14) implies P(17) implies....$
And any dope can see this goes on for ever and $P(14 + 3k);k ge 0$.
.... well, but that's only $frac 13$ of the cases. We don't know $P(15),P(16), P(18)$, etc.
So we need:
Base case 2 and 3: $P(12)$ and $P(13)$
the we can conclude we have $P(14 + 3k), P(12 + 3j), P(13 + 3m); k,j,m ge 0$.
Or in other words $P(n); n ge 12$.
In short: if the induction step shows $P(n) = P(n+c)$, we must either have $c$ base cases to prove $P(n); n ge base$, or must accept we can only prove $P(base + kc);k ge 0$.
====old slightly flippant answer where I misunderstood the induction step somewhat below ====
If your induction step includes "If it is true for $(n-3)$" then you actually have to demonstrate that it is true for $(n-3)$. Via a base case.
So if our base case were true for $n = 15$, and we do induction on it and say "since it is true for $(n-3) = 12$..." we need to sit up and do a "whoa! whoa! whoa, whoa.... It's true for $12$? Sez who???"
Hence we also need a base case of $12$.
So we now have a base case for $12$ and $15$. And we do induction on $n=15$ "since it is true for $n-3 = 12$ it is true for $n+1 = 16$". Cool! It's true for $n=16$.
Then we do induction on $n=16$ and we get "since it is true for $n-3 = 13$..." "whoa! whoa! whoa, whoa...."
and so on.
answered Nov 3 '16 at 18:01
fleabloodfleablood
71.1k22686
$endgroup$
add a comment |
$begingroup$
Prove, by strong induction, that if $nge12$, then $n=3a+7b$ for some positive integers $a$ and $b$.
Let's do the induction step, first. Suppose that $n>12$ and that, for $12le k<n$, $k=3a_k+7b_k$.
If $n-3ge 12$, then, by the induction hypothesis, $n-3=3a+7b$, so $n=3(a+1)+7b$. Otherwise $n-3<12$, that is, $n=12$, $n=13$ or $n=14$.
Since $12=3cdot4+7cdot0$, $13=3cdot2+7cdot1$ and $14=3cdot0+7cdot2$, we are done, by adding $3$. Also with the base case $n=12$ is obviously covered.
Can you see now why also the cases $n=13$ and $n=14$ are needed? When we do $n-3$ we can't assume that $n-3ge12$ and we must cope with the possibility $n-3<12$.
answered Nov 4 '16 at 0:19
egregegreg
182k1486204
$endgroup$
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%2f1997535%2funderstanding-this-proof-by-strong-induction-that-each-n%25e2%2589%25a512-is-n-3a-7b-for-s%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$
Let $P(k)$ be the statment ‘$k$ is a multiple of $3$’, and consider the following proposition:
For each integer $nge 12$, $P(n)$ is true.
We’ll use your approach to ‘prove’ it by induction. Let $n$ be a natural number such that $nge 15$, and suppose that $P(k)$ holds whenever $12le k<n$. Clearly $n-3ge 12$, so by hypothesis $n-3$ is a multiple of $3$. Thus, there is an integer $k$ such that $n-3=3k$. But then $n=3k+3=3(k+1)$ is also a multiploe of $3$, and the result follows by induction.
This is clearly nonsense: it certainly is not true that all natural numbers greater than or equal to $12$ are multiples of $3$. However, there is absolutely nothing wrong with the induction step that I just gave. If it were in fact the case that $nge 15$, and all integers $k$ such that $12le k<n$ were multiples of $3$, then it would indeed be true that $n$ was a multiple of $3$. The problem, of course, is that it is not true that all integers $k$ such that $12le k<n$ are multiples of $3$. In particular, $13$ is not, so when $n=16$ the induction step rests on a false premise: it works if $16-3=13$ is a multiple of $3$, but that is not in fact the case, and you’re not entitled to assume that it is.
In fact what the induction argument above actually shows is that if $12,13$, and $14$ were all multiples of $3$, then every natural number greater than or equal to $12$ would be a multiple of $3$. Unfortunately for that conclusion, $13$ and $14$ are not multiples of $3$. The induction step is only as good as its foundation: if you don’t verify enough base cases to make the induction step work, the argument is worthless.
In your case that means verifying $3$ cases, because the induction step for $n$ requires that the result be true for $n-3$. Thus, proving $P(15)$ by the induction step requires knowing that $P(12)$ is true, not just assuming it. Similarly, proving $P(16)$ by the induction step requires knowing that $P(13)$ is true, and proving $P(17)$ by the induction step requires knowing that $P(14)$ is true. There are no stages before $12,13$, and $14$: $P(12),P(13)$, and $P(14)$ are the foundation on which everything else rests. For example, $P(20)$ follows by the induction argument from $P(20-3)=P(17)$, which follows by the induction argument from $P(17-3)=P(14)$, but $P(14)$ doesn’t follow by the induction from $P(11)$, because $11$ isn’t in the domain of the argument (and in fact $P(11)$ is false).
answered Nov 3 '16 at 17:47
Brian M. ScottBrian M. Scott
458k38511913
$endgroup$
$begingroup$
Thank you for the reply. The last paragraph really helped tie some things together for me, but I feel I am still missing something very basic. For one, I don't understand why n-3 is necessarily a multiple of 3. That would only be the case if the n chosen was a multiple of 3, would it not? What about all the n values that are not multiple of 3? Second, and more fundamentally, I don't understand why we need n-3 in the induction step. Would this proof not also work if we showed P(12), set n≥13 and assumed n-1 was true?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 19:47
$begingroup$
@IgnorantCuriosity: You’re forgetting that the induction hypothesis was that $P(k)$ holds whenever $12le k<n$, where $n$ is some natural number greater than or equal to $15$. If $nge 15$, then $12le n-3<n$, so the induction hypothesis tells us that $n-3$ is a multiple of $3$. The problem here is of course that in fact the induction hypothesis isn’t true: we just assumed it. That’s exactly what you were proposing to do in your argument, and it’s no more valid there than it is here. \ Yes, this fallacious argument could have been carried out just as well as you suggest. However, in ...
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:54
$begingroup$
... order to show as clearly as possible what is wrong with the argument that you proposed in your question, I wanted to make it look as much like that argument as possible.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:55
$begingroup$
I apologize for my blindness, but I'm not seeing the connection between stating that (n-3) = 3a +7b, and stating that (n-3) = 3k. Would it be possible for you to spell this connection out for me?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 20:13
$begingroup$
@IgnorantCuriosity: Both are the assertion that $P(n-3)$ is true, where $P(k)$ is the assertion that $k$ has the specific property of interest. The properties are different, but they play exactly the same role in the arguments.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 20:15
|
show 4 more comments
$begingroup$
Let $P(k)$ be the statment ‘$k$ is a multiple of $3$’, and consider the following proposition:
For each integer $nge 12$, $P(n)$ is true.
We’ll use your approach to ‘prove’ it by induction. Let $n$ be a natural number such that $nge 15$, and suppose that $P(k)$ holds whenever $12le k<n$. Clearly $n-3ge 12$, so by hypothesis $n-3$ is a multiple of $3$. Thus, there is an integer $k$ such that $n-3=3k$. But then $n=3k+3=3(k+1)$ is also a multiploe of $3$, and the result follows by induction.
This is clearly nonsense: it certainly is not true that all natural numbers greater than or equal to $12$ are multiples of $3$. However, there is absolutely nothing wrong with the induction step that I just gave. If it were in fact the case that $nge 15$, and all integers $k$ such that $12le k<n$ were multiples of $3$, then it would indeed be true that $n$ was a multiple of $3$. The problem, of course, is that it is not true that all integers $k$ such that $12le k<n$ are multiples of $3$. In particular, $13$ is not, so when $n=16$ the induction step rests on a false premise: it works if $16-3=13$ is a multiple of $3$, but that is not in fact the case, and you’re not entitled to assume that it is.
In fact what the induction argument above actually shows is that if $12,13$, and $14$ were all multiples of $3$, then every natural number greater than or equal to $12$ would be a multiple of $3$. Unfortunately for that conclusion, $13$ and $14$ are not multiples of $3$. The induction step is only as good as its foundation: if you don’t verify enough base cases to make the induction step work, the argument is worthless.
In your case that means verifying $3$ cases, because the induction step for $n$ requires that the result be true for $n-3$. Thus, proving $P(15)$ by the induction step requires knowing that $P(12)$ is true, not just assuming it. Similarly, proving $P(16)$ by the induction step requires knowing that $P(13)$ is true, and proving $P(17)$ by the induction step requires knowing that $P(14)$ is true. There are no stages before $12,13$, and $14$: $P(12),P(13)$, and $P(14)$ are the foundation on which everything else rests. For example, $P(20)$ follows by the induction argument from $P(20-3)=P(17)$, which follows by the induction argument from $P(17-3)=P(14)$, but $P(14)$ doesn’t follow by the induction from $P(11)$, because $11$ isn’t in the domain of the argument (and in fact $P(11)$ is false).
answered Nov 3 '16 at 17:47
Brian M. ScottBrian M. Scott
458k38511913
$endgroup$
$begingroup$
Thank you for the reply. The last paragraph really helped tie some things together for me, but I feel I am still missing something very basic. For one, I don't understand why n-3 is necessarily a multiple of 3. That would only be the case if the n chosen was a multiple of 3, would it not? What about all the n values that are not multiple of 3? Second, and more fundamentally, I don't understand why we need n-3 in the induction step. Would this proof not also work if we showed P(12), set n≥13 and assumed n-1 was true?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 19:47
$begingroup$
@IgnorantCuriosity: You’re forgetting that the induction hypothesis was that $P(k)$ holds whenever $12le k<n$, where $n$ is some natural number greater than or equal to $15$. If $nge 15$, then $12le n-3<n$, so the induction hypothesis tells us that $n-3$ is a multiple of $3$. The problem here is of course that in fact the induction hypothesis isn’t true: we just assumed it. That’s exactly what you were proposing to do in your argument, and it’s no more valid there than it is here. \ Yes, this fallacious argument could have been carried out just as well as you suggest. However, in ...
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:54
$begingroup$
... order to show as clearly as possible what is wrong with the argument that you proposed in your question, I wanted to make it look as much like that argument as possible.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:55
$begingroup$
I apologize for my blindness, but I'm not seeing the connection between stating that (n-3) = 3a +7b, and stating that (n-3) = 3k. Would it be possible for you to spell this connection out for me?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 20:13
$begingroup$
@IgnorantCuriosity: Both are the assertion that $P(n-3)$ is true, where $P(k)$ is the assertion that $k$ has the specific property of interest. The properties are different, but they play exactly the same role in the arguments.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 20:15
|
show 4 more comments
$begingroup$
Let $P(k)$ be the statment ‘$k$ is a multiple of $3$’, and consider the following proposition:
For each integer $nge 12$, $P(n)$ is true.
We’ll use your approach to ‘prove’ it by induction. Let $n$ be a natural number such that $nge 15$, and suppose that $P(k)$ holds whenever $12le k<n$. Clearly $n-3ge 12$, so by hypothesis $n-3$ is a multiple of $3$. Thus, there is an integer $k$ such that $n-3=3k$. But then $n=3k+3=3(k+1)$ is also a multiploe of $3$, and the result follows by induction.
This is clearly nonsense: it certainly is not true that all natural numbers greater than or equal to $12$ are multiples of $3$. However, there is absolutely nothing wrong with the induction step that I just gave. If it were in fact the case that $nge 15$, and all integers $k$ such that $12le k<n$ were multiples of $3$, then it would indeed be true that $n$ was a multiple of $3$. The problem, of course, is that it is not true that all integers $k$ such that $12le k<n$ are multiples of $3$. In particular, $13$ is not, so when $n=16$ the induction step rests on a false premise: it works if $16-3=13$ is a multiple of $3$, but that is not in fact the case, and you’re not entitled to assume that it is.
In fact what the induction argument above actually shows is that if $12,13$, and $14$ were all multiples of $3$, then every natural number greater than or equal to $12$ would be a multiple of $3$. Unfortunately for that conclusion, $13$ and $14$ are not multiples of $3$. The induction step is only as good as its foundation: if you don’t verify enough base cases to make the induction step work, the argument is worthless.
In your case that means verifying $3$ cases, because the induction step for $n$ requires that the result be true for $n-3$. Thus, proving $P(15)$ by the induction step requires knowing that $P(12)$ is true, not just assuming it. Similarly, proving $P(16)$ by the induction step requires knowing that $P(13)$ is true, and proving $P(17)$ by the induction step requires knowing that $P(14)$ is true. There are no stages before $12,13$, and $14$: $P(12),P(13)$, and $P(14)$ are the foundation on which everything else rests. For example, $P(20)$ follows by the induction argument from $P(20-3)=P(17)$, which follows by the induction argument from $P(17-3)=P(14)$, but $P(14)$ doesn’t follow by the induction from $P(11)$, because $11$ isn’t in the domain of the argument (and in fact $P(11)$ is false).
answered Nov 3 '16 at 17:47
Brian M. ScottBrian M. Scott
458k38511913
$endgroup$
Let $P(k)$ be the statment ‘$k$ is a multiple of $3$’, and consider the following proposition:
For each integer $nge 12$, $P(n)$ is true.
We’ll use your approach to ‘prove’ it by induction. Let $n$ be a natural number such that $nge 15$, and suppose that $P(k)$ holds whenever $12le k<n$. Clearly $n-3ge 12$, so by hypothesis $n-3$ is a multiple of $3$. Thus, there is an integer $k$ such that $n-3=3k$. But then $n=3k+3=3(k+1)$ is also a multiploe of $3$, and the result follows by induction.
This is clearly nonsense: it certainly is not true that all natural numbers greater than or equal to $12$ are multiples of $3$. However, there is absolutely nothing wrong with the induction step that I just gave. If it were in fact the case that $nge 15$, and all integers $k$ such that $12le k<n$ were multiples of $3$, then it would indeed be true that $n$ was a multiple of $3$. The problem, of course, is that it is not true that all integers $k$ such that $12le k<n$ are multiples of $3$. In particular, $13$ is not, so when $n=16$ the induction step rests on a false premise: it works if $16-3=13$ is a multiple of $3$, but that is not in fact the case, and you’re not entitled to assume that it is.
In fact what the induction argument above actually shows is that if $12,13$, and $14$ were all multiples of $3$, then every natural number greater than or equal to $12$ would be a multiple of $3$. Unfortunately for that conclusion, $13$ and $14$ are not multiples of $3$. The induction step is only as good as its foundation: if you don’t verify enough base cases to make the induction step work, the argument is worthless.
In your case that means verifying $3$ cases, because the induction step for $n$ requires that the result be true for $n-3$. Thus, proving $P(15)$ by the induction step requires knowing that $P(12)$ is true, not just assuming it. Similarly, proving $P(16)$ by the induction step requires knowing that $P(13)$ is true, and proving $P(17)$ by the induction step requires knowing that $P(14)$ is true. There are no stages before $12,13$, and $14$: $P(12),P(13)$, and $P(14)$ are the foundation on which everything else rests. For example, $P(20)$ follows by the induction argument from $P(20-3)=P(17)$, which follows by the induction argument from $P(17-3)=P(14)$, but $P(14)$ doesn’t follow by the induction from $P(11)$, because $11$ isn’t in the domain of the argument (and in fact $P(11)$ is false).
answered Nov 3 '16 at 17:47
Brian M. ScottBrian M. Scott
458k38511913
answered Nov 3 '16 at 17:47
Brian M. ScottBrian M. Scott
458k38511913
answered Nov 3 '16 at 17:47
Brian M. ScottBrian M. Scott
458k38511913
answered Nov 3 '16 at 17:47
Brian M. ScottBrian M. Scott
458k38511913
458k38511913
$begingroup$
Thank you for the reply. The last paragraph really helped tie some things together for me, but I feel I am still missing something very basic. For one, I don't understand why n-3 is necessarily a multiple of 3. That would only be the case if the n chosen was a multiple of 3, would it not? What about all the n values that are not multiple of 3? Second, and more fundamentally, I don't understand why we need n-3 in the induction step. Would this proof not also work if we showed P(12), set n≥13 and assumed n-1 was true?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 19:47
$begingroup$
@IgnorantCuriosity: You’re forgetting that the induction hypothesis was that $P(k)$ holds whenever $12le k<n$, where $n$ is some natural number greater than or equal to $15$. If $nge 15$, then $12le n-3<n$, so the induction hypothesis tells us that $n-3$ is a multiple of $3$. The problem here is of course that in fact the induction hypothesis isn’t true: we just assumed it. That’s exactly what you were proposing to do in your argument, and it’s no more valid there than it is here. \ Yes, this fallacious argument could have been carried out just as well as you suggest. However, in ...
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:54
$begingroup$
... order to show as clearly as possible what is wrong with the argument that you proposed in your question, I wanted to make it look as much like that argument as possible.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:55
$begingroup$
I apologize for my blindness, but I'm not seeing the connection between stating that (n-3) = 3a +7b, and stating that (n-3) = 3k. Would it be possible for you to spell this connection out for me?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 20:13
$begingroup$
@IgnorantCuriosity: Both are the assertion that $P(n-3)$ is true, where $P(k)$ is the assertion that $k$ has the specific property of interest. The properties are different, but they play exactly the same role in the arguments.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 20:15
|
show 4 more comments
$begingroup$
Thank you for the reply. The last paragraph really helped tie some things together for me, but I feel I am still missing something very basic. For one, I don't understand why n-3 is necessarily a multiple of 3. That would only be the case if the n chosen was a multiple of 3, would it not? What about all the n values that are not multiple of 3? Second, and more fundamentally, I don't understand why we need n-3 in the induction step. Would this proof not also work if we showed P(12), set n≥13 and assumed n-1 was true?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 19:47
$begingroup$
@IgnorantCuriosity: You’re forgetting that the induction hypothesis was that $P(k)$ holds whenever $12le k<n$, where $n$ is some natural number greater than or equal to $15$. If $nge 15$, then $12le n-3<n$, so the induction hypothesis tells us that $n-3$ is a multiple of $3$. The problem here is of course that in fact the induction hypothesis isn’t true: we just assumed it. That’s exactly what you were proposing to do in your argument, and it’s no more valid there than it is here. \ Yes, this fallacious argument could have been carried out just as well as you suggest. However, in ...
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:54
$begingroup$
... order to show as clearly as possible what is wrong with the argument that you proposed in your question, I wanted to make it look as much like that argument as possible.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:55
$begingroup$
I apologize for my blindness, but I'm not seeing the connection between stating that (n-3) = 3a +7b, and stating that (n-3) = 3k. Would it be possible for you to spell this connection out for me?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 20:13
$begingroup$
@IgnorantCuriosity: Both are the assertion that $P(n-3)$ is true, where $P(k)$ is the assertion that $k$ has the specific property of interest. The properties are different, but they play exactly the same role in the arguments.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 20:15
$begingroup$
Thank you for the reply. The last paragraph really helped tie some things together for me, but I feel I am still missing something very basic. For one, I don't understand why n-3 is necessarily a multiple of 3. That would only be the case if the n chosen was a multiple of 3, would it not? What about all the n values that are not multiple of 3? Second, and more fundamentally, I don't understand why we need n-3 in the induction step. Would this proof not also work if we showed P(12), set n≥13 and assumed n-1 was true?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 19:47
$begingroup$
Thank you for the reply. The last paragraph really helped tie some things together for me, but I feel I am still missing something very basic. For one, I don't understand why n-3 is necessarily a multiple of 3. That would only be the case if the n chosen was a multiple of 3, would it not? What about all the n values that are not multiple of 3? Second, and more fundamentally, I don't understand why we need n-3 in the induction step. Would this proof not also work if we showed P(12), set n≥13 and assumed n-1 was true?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 19:47
$begingroup$
@IgnorantCuriosity: You’re forgetting that the induction hypothesis was that $P(k)$ holds whenever $12le k<n$, where $n$ is some natural number greater than or equal to $15$. If $nge 15$, then $12le n-3<n$, so the induction hypothesis tells us that $n-3$ is a multiple of $3$. The problem here is of course that in fact the induction hypothesis isn’t true: we just assumed it. That’s exactly what you were proposing to do in your argument, and it’s no more valid there than it is here. \ Yes, this fallacious argument could have been carried out just as well as you suggest. However, in ...
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:54
$begingroup$
@IgnorantCuriosity: You’re forgetting that the induction hypothesis was that $P(k)$ holds whenever $12le k<n$, where $n$ is some natural number greater than or equal to $15$. If $nge 15$, then $12le n-3<n$, so the induction hypothesis tells us that $n-3$ is a multiple of $3$. The problem here is of course that in fact the induction hypothesis isn’t true: we just assumed it. That’s exactly what you were proposing to do in your argument, and it’s no more valid there than it is here. \ Yes, this fallacious argument could have been carried out just as well as you suggest. However, in ...
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:54
$begingroup$
... order to show as clearly as possible what is wrong with the argument that you proposed in your question, I wanted to make it look as much like that argument as possible.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:55
$begingroup$
... order to show as clearly as possible what is wrong with the argument that you proposed in your question, I wanted to make it look as much like that argument as possible.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 19:55
$begingroup$
I apologize for my blindness, but I'm not seeing the connection between stating that (n-3) = 3a +7b, and stating that (n-3) = 3k. Would it be possible for you to spell this connection out for me?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 20:13
$begingroup$
I apologize for my blindness, but I'm not seeing the connection between stating that (n-3) = 3a +7b, and stating that (n-3) = 3k. Would it be possible for you to spell this connection out for me?
$endgroup$
– IgnorantCuriosity
Nov 6 '16 at 20:13
$begingroup$
@IgnorantCuriosity: Both are the assertion that $P(n-3)$ is true, where $P(k)$ is the assertion that $k$ has the specific property of interest. The properties are different, but they play exactly the same role in the arguments.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 20:15
$begingroup$
@IgnorantCuriosity: Both are the assertion that $P(n-3)$ is true, where $P(k)$ is the assertion that $k$ has the specific property of interest. The properties are different, but they play exactly the same role in the arguments.
$endgroup$
– Brian M. Scott
Nov 6 '16 at 20:15
|
show 4 more comments
$begingroup$
My question: Why do we need cases $1,2,$ and $3$? Why can't I just assume that $P(k)$ is true for all $k<n$, ...
Well, for starters, $P(11)$ and several others are false so the assumption is not justified.
If we need a "base case" to start the induction process, then why can't we just use case 1 and case 4, cutting out 2 and 3? Any help understanding this would be greatly appreciated.
Case 1 and Case 4 show that $P(12+3(0))$ and $forall nin Bbb N: big(bigwedgelimits_{k=0}^n P(12+3k)big)to P(12+3n+3)$, which proves by strong induction that $forall nin Bbb N: P(12+3n)$.
That is $P(12),P(15),P(18), P(21),ldots$
This misses out two thirds of what we need to show. The other two cases allow us to "fill in the gaps".
Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem?
Case 4 is an implication. An implication alone is not sufficient to prove its consequent.
Recall the difference between soundness and validity of a proof.
If you only assume a premise, then the conclusion may not be true. You have to demonstrate that the pemise is justified in order to prove the conclusion.
I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?
The predicate $P(12+3k)$ is that $exists a{in}Bbb N~exists b{in}Bbb N: (12+3k)=3a+7b$.
You can see that $P(12)$ is justified because $12=3(4)+7(0)$. That is that $a=4$ and $b=0$ are witnesses to $P(12)$.
We can also show that if $P(n_0)$ is true, then $P(n_0+3k)$ is true for every natural number $k$. Because $n_0=4a_0+7b_0 ~to~ (n_0+3k) = 3(a_0+k)+7(b_0)$ is sound.
Then if $P(12)$ is justified, and $forall k{in}Bbb N:P(n_0)to P(n_0+3k)$ is sound, then it follows that $forall kinBbb N: P(12+3k)$ is valid.
answered Nov 3 '16 at 13:15
Graham KempGraham Kemp
86k43378
$endgroup$
$begingroup$
Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem? I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?
$endgroup$
– IgnorantCuriosity
Nov 3 '16 at 15:48
$begingroup$
See the addition, @IgnorantCuriosity
$endgroup$
– Graham Kemp
Nov 3 '16 at 23:55
add a comment |
$begingroup$
My question: Why do we need cases $1,2,$ and $3$? Why can't I just assume that $P(k)$ is true for all $k<n$, ...
Well, for starters, $P(11)$ and several others are false so the assumption is not justified.
If we need a "base case" to start the induction process, then why can't we just use case 1 and case 4, cutting out 2 and 3? Any help understanding this would be greatly appreciated.
Case 1 and Case 4 show that $P(12+3(0))$ and $forall nin Bbb N: big(bigwedgelimits_{k=0}^n P(12+3k)big)to P(12+3n+3)$, which proves by strong induction that $forall nin Bbb N: P(12+3n)$.
That is $P(12),P(15),P(18), P(21),ldots$
This misses out two thirds of what we need to show. The other two cases allow us to "fill in the gaps".
Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem?
Case 4 is an implication. An implication alone is not sufficient to prove its consequent.
Recall the difference between soundness and validity of a proof.
If you only assume a premise, then the conclusion may not be true. You have to demonstrate that the pemise is justified in order to prove the conclusion.
I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?
The predicate $P(12+3k)$ is that $exists a{in}Bbb N~exists b{in}Bbb N: (12+3k)=3a+7b$.
You can see that $P(12)$ is justified because $12=3(4)+7(0)$. That is that $a=4$ and $b=0$ are witnesses to $P(12)$.
We can also show that if $P(n_0)$ is true, then $P(n_0+3k)$ is true for every natural number $k$. Because $n_0=4a_0+7b_0 ~to~ (n_0+3k) = 3(a_0+k)+7(b_0)$ is sound.
Then if $P(12)$ is justified, and $forall k{in}Bbb N:P(n_0)to P(n_0+3k)$ is sound, then it follows that $forall kinBbb N: P(12+3k)$ is valid.
answered Nov 3 '16 at 13:15
Graham KempGraham Kemp
86k43378
$endgroup$
$begingroup$
Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem? I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?
$endgroup$
– IgnorantCuriosity
Nov 3 '16 at 15:48
$begingroup$
See the addition, @IgnorantCuriosity
$endgroup$
– Graham Kemp
Nov 3 '16 at 23:55
add a comment |
$begingroup$
My question: Why do we need cases $1,2,$ and $3$? Why can't I just assume that $P(k)$ is true for all $k<n$, ...
Well, for starters, $P(11)$ and several others are false so the assumption is not justified.
If we need a "base case" to start the induction process, then why can't we just use case 1 and case 4, cutting out 2 and 3? Any help understanding this would be greatly appreciated.
Case 1 and Case 4 show that $P(12+3(0))$ and $forall nin Bbb N: big(bigwedgelimits_{k=0}^n P(12+3k)big)to P(12+3n+3)$, which proves by strong induction that $forall nin Bbb N: P(12+3n)$.
That is $P(12),P(15),P(18), P(21),ldots$
This misses out two thirds of what we need to show. The other two cases allow us to "fill in the gaps".
Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem?
Case 4 is an implication. An implication alone is not sufficient to prove its consequent.
Recall the difference between soundness and validity of a proof.
If you only assume a premise, then the conclusion may not be true. You have to demonstrate that the pemise is justified in order to prove the conclusion.
I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?
The predicate $P(12+3k)$ is that $exists a{in}Bbb N~exists b{in}Bbb N: (12+3k)=3a+7b$.
You can see that $P(12)$ is justified because $12=3(4)+7(0)$. That is that $a=4$ and $b=0$ are witnesses to $P(12)$.
We can also show that if $P(n_0)$ is true, then $P(n_0+3k)$ is true for every natural number $k$. Because $n_0=4a_0+7b_0 ~to~ (n_0+3k) = 3(a_0+k)+7(b_0)$ is sound.
Then if $P(12)$ is justified, and $forall k{in}Bbb N:P(n_0)to P(n_0+3k)$ is sound, then it follows that $forall kinBbb N: P(12+3k)$ is valid.
answered Nov 3 '16 at 13:15
Graham KempGraham Kemp
86k43378
$endgroup$
My question: Why do we need cases $1,2,$ and $3$? Why can't I just assume that $P(k)$ is true for all $k<n$, ...
Well, for starters, $P(11)$ and several others are false so the assumption is not justified.
If we need a "base case" to start the induction process, then why can't we just use case 1 and case 4, cutting out 2 and 3? Any help understanding this would be greatly appreciated.
Case 1 and Case 4 show that $P(12+3(0))$ and $forall nin Bbb N: big(bigwedgelimits_{k=0}^n P(12+3k)big)to P(12+3n+3)$, which proves by strong induction that $forall nin Bbb N: P(12+3n)$.
That is $P(12),P(15),P(18), P(21),ldots$
This misses out two thirds of what we need to show. The other two cases allow us to "fill in the gaps".
Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem?
Case 4 is an implication. An implication alone is not sufficient to prove its consequent.
Recall the difference between soundness and validity of a proof.
If you only assume a premise, then the conclusion may not be true. You have to demonstrate that the pemise is justified in order to prove the conclusion.
I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?
The predicate $P(12+3k)$ is that $exists a{in}Bbb N~exists b{in}Bbb N: (12+3k)=3a+7b$.
You can see that $P(12)$ is justified because $12=3(4)+7(0)$. That is that $a=4$ and $b=0$ are witnesses to $P(12)$.
We can also show that if $P(n_0)$ is true, then $P(n_0+3k)$ is true for every natural number $k$. Because $n_0=4a_0+7b_0 ~to~ (n_0+3k) = 3(a_0+k)+7(b_0)$ is sound.
Then if $P(12)$ is justified, and $forall k{in}Bbb N:P(n_0)to P(n_0+3k)$ is sound, then it follows that $forall kinBbb N: P(12+3k)$ is valid.
answered Nov 3 '16 at 13:15
Graham KempGraham Kemp
86k43378
edited Nov 3 '16 at 23:55
answered Nov 3 '16 at 13:15
Graham KempGraham Kemp
86k43378
answered Nov 3 '16 at 13:15
Graham KempGraham Kemp
86k43378
answered Nov 3 '16 at 13:15
Graham KempGraham Kemp
86k43378
86k43378
$begingroup$
Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem? I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?
$endgroup$
– IgnorantCuriosity
Nov 3 '16 at 15:48
$begingroup$
See the addition, @IgnorantCuriosity
$endgroup$
– Graham Kemp
Nov 3 '16 at 23:55
add a comment |
$begingroup$
Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem? I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?
$endgroup$
– IgnorantCuriosity
Nov 3 '16 at 15:48
$begingroup$
See the addition, @IgnorantCuriosity
$endgroup$
– Graham Kemp
Nov 3 '16 at 23:55
$begingroup$
Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem? I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?
$endgroup$
– IgnorantCuriosity
Nov 3 '16 at 15:48
$begingroup$
Thank you for the reply. I have corrected my post to show that the first part of my question should have assumed k was between 12 and n. Can you explain what it is I end up with if I only assume this and show case 4, and why this result does not prove the theorem? I also do not understand where you are getting P(12 +3(0)) and P(12+3k) from. Should this be P(12 +7(0)) and P(12+7k)?
$endgroup$
– IgnorantCuriosity
Nov 3 '16 at 15:48
$begingroup$
See the addition, @IgnorantCuriosity
$endgroup$
– Graham Kemp
Nov 3 '16 at 23:55
$begingroup$
See the addition, @IgnorantCuriosity
$endgroup$
– Graham Kemp
Nov 3 '16 at 23:55
add a comment |
$begingroup$
Usually a proof by induction has this induction step:
Induction step: $P(n) implies P(n+1)$
So that and the the base case:
Base case: $P(b)$
will yield:
$P(b) implies P(b+1) implies P(b+2) implies ...$ and "any dope can see that will go on forever and cover every $P(n); n ge b$".
But in this exercise we do not have "$P(n) implies P(n+1)$" as our induction step. Instead we have:
Induction step: $P(n-3)implies P(n)$.
Or in other words:
Induction step: $P(n) implies P(n+3)$.
So if our base case is:
Base case: $P(14)$.
So we can conclude:
$P(14) implies P(17) implies....$
And any dope can see this goes on for ever and $P(14 + 3k);k ge 0$.
.... well, but that's only $frac 13$ of the cases. We don't know $P(15),P(16), P(18)$, etc.
So we need:
Base case 2 and 3: $P(12)$ and $P(13)$
the we can conclude we have $P(14 + 3k), P(12 + 3j), P(13 + 3m); k,j,m ge 0$.
Or in other words $P(n); n ge 12$.
In short: if the induction step shows $P(n) = P(n+c)$, we must either have $c$ base cases to prove $P(n); n ge base$, or must accept we can only prove $P(base + kc);k ge 0$.
====old slightly flippant answer where I misunderstood the induction step somewhat below ====
If your induction step includes "If it is true for $(n-3)$" then you actually have to demonstrate that it is true for $(n-3)$. Via a base case.
So if our base case were true for $n = 15$, and we do induction on it and say "since it is true for $(n-3) = 12$..." we need to sit up and do a "whoa! whoa! whoa, whoa.... It's true for $12$? Sez who???"
Hence we also need a base case of $12$.
So we now have a base case for $12$ and $15$. And we do induction on $n=15$ "since it is true for $n-3 = 12$ it is true for $n+1 = 16$". Cool! It's true for $n=16$.
Then we do induction on $n=16$ and we get "since it is true for $n-3 = 13$..." "whoa! whoa! whoa, whoa...."
and so on.
answered Nov 3 '16 at 18:01
fleabloodfleablood
71.1k22686
$endgroup$
add a comment |
$begingroup$
Usually a proof by induction has this induction step:
Induction step: $P(n) implies P(n+1)$
So that and the the base case:
Base case: $P(b)$
will yield:
$P(b) implies P(b+1) implies P(b+2) implies ...$ and "any dope can see that will go on forever and cover every $P(n); n ge b$".
But in this exercise we do not have "$P(n) implies P(n+1)$" as our induction step. Instead we have:
Induction step: $P(n-3)implies P(n)$.
Or in other words:
Induction step: $P(n) implies P(n+3)$.
So if our base case is:
Base case: $P(14)$.
So we can conclude:
$P(14) implies P(17) implies....$
And any dope can see this goes on for ever and $P(14 + 3k);k ge 0$.
.... well, but that's only $frac 13$ of the cases. We don't know $P(15),P(16), P(18)$, etc.
So we need:
Base case 2 and 3: $P(12)$ and $P(13)$
the we can conclude we have $P(14 + 3k), P(12 + 3j), P(13 + 3m); k,j,m ge 0$.
Or in other words $P(n); n ge 12$.
In short: if the induction step shows $P(n) = P(n+c)$, we must either have $c$ base cases to prove $P(n); n ge base$, or must accept we can only prove $P(base + kc);k ge 0$.
====old slightly flippant answer where I misunderstood the induction step somewhat below ====
If your induction step includes "If it is true for $(n-3)$" then you actually have to demonstrate that it is true for $(n-3)$. Via a base case.
So if our base case were true for $n = 15$, and we do induction on it and say "since it is true for $(n-3) = 12$..." we need to sit up and do a "whoa! whoa! whoa, whoa.... It's true for $12$? Sez who???"
Hence we also need a base case of $12$.
So we now have a base case for $12$ and $15$. And we do induction on $n=15$ "since it is true for $n-3 = 12$ it is true for $n+1 = 16$". Cool! It's true for $n=16$.
Then we do induction on $n=16$ and we get "since it is true for $n-3 = 13$..." "whoa! whoa! whoa, whoa...."
and so on.
answered Nov 3 '16 at 18:01
fleabloodfleablood
71.1k22686
$endgroup$
add a comment |
$begingroup$
Usually a proof by induction has this induction step:
Induction step: $P(n) implies P(n+1)$
So that and the the base case:
Base case: $P(b)$
will yield:
$P(b) implies P(b+1) implies P(b+2) implies ...$ and "any dope can see that will go on forever and cover every $P(n); n ge b$".
But in this exercise we do not have "$P(n) implies P(n+1)$" as our induction step. Instead we have:
Induction step: $P(n-3)implies P(n)$.
Or in other words:
Induction step: $P(n) implies P(n+3)$.
So if our base case is:
Base case: $P(14)$.
So we can conclude:
$P(14) implies P(17) implies....$
And any dope can see this goes on for ever and $P(14 + 3k);k ge 0$.
.... well, but that's only $frac 13$ of the cases. We don't know $P(15),P(16), P(18)$, etc.
So we need:
Base case 2 and 3: $P(12)$ and $P(13)$
the we can conclude we have $P(14 + 3k), P(12 + 3j), P(13 + 3m); k,j,m ge 0$.
Or in other words $P(n); n ge 12$.
In short: if the induction step shows $P(n) = P(n+c)$, we must either have $c$ base cases to prove $P(n); n ge base$, or must accept we can only prove $P(base + kc);k ge 0$.
====old slightly flippant answer where I misunderstood the induction step somewhat below ====
If your induction step includes "If it is true for $(n-3)$" then you actually have to demonstrate that it is true for $(n-3)$. Via a base case.
So if our base case were true for $n = 15$, and we do induction on it and say "since it is true for $(n-3) = 12$..." we need to sit up and do a "whoa! whoa! whoa, whoa.... It's true for $12$? Sez who???"
Hence we also need a base case of $12$.
So we now have a base case for $12$ and $15$. And we do induction on $n=15$ "since it is true for $n-3 = 12$ it is true for $n+1 = 16$". Cool! It's true for $n=16$.
Then we do induction on $n=16$ and we get "since it is true for $n-3 = 13$..." "whoa! whoa! whoa, whoa...."
and so on.
answered Nov 3 '16 at 18:01
fleabloodfleablood
71.1k22686
$endgroup$
Usually a proof by induction has this induction step:
Induction step: $P(n) implies P(n+1)$
So that and the the base case:
Base case: $P(b)$
will yield:
$P(b) implies P(b+1) implies P(b+2) implies ...$ and "any dope can see that will go on forever and cover every $P(n); n ge b$".
But in this exercise we do not have "$P(n) implies P(n+1)$" as our induction step. Instead we have:
Induction step: $P(n-3)implies P(n)$.
Or in other words:
Induction step: $P(n) implies P(n+3)$.
So if our base case is:
Base case: $P(14)$.
So we can conclude:
$P(14) implies P(17) implies....$
And any dope can see this goes on for ever and $P(14 + 3k);k ge 0$.
.... well, but that's only $frac 13$ of the cases. We don't know $P(15),P(16), P(18)$, etc.
So we need:
Base case 2 and 3: $P(12)$ and $P(13)$
the we can conclude we have $P(14 + 3k), P(12 + 3j), P(13 + 3m); k,j,m ge 0$.
Or in other words $P(n); n ge 12$.
In short: if the induction step shows $P(n) = P(n+c)$, we must either have $c$ base cases to prove $P(n); n ge base$, or must accept we can only prove $P(base + kc);k ge 0$.
====old slightly flippant answer where I misunderstood the induction step somewhat below ====
If your induction step includes "If it is true for $(n-3)$" then you actually have to demonstrate that it is true for $(n-3)$. Via a base case.
So if our base case were true for $n = 15$, and we do induction on it and say "since it is true for $(n-3) = 12$..." we need to sit up and do a "whoa! whoa! whoa, whoa.... It's true for $12$? Sez who???"
Hence we also need a base case of $12$.
So we now have a base case for $12$ and $15$. And we do induction on $n=15$ "since it is true for $n-3 = 12$ it is true for $n+1 = 16$". Cool! It's true for $n=16$.
Then we do induction on $n=16$ and we get "since it is true for $n-3 = 13$..." "whoa! whoa! whoa, whoa...."
and so on.
answered Nov 3 '16 at 18:01
fleabloodfleablood
71.1k22686
edited Nov 3 '16 at 18:52
answered Nov 3 '16 at 18:01
fleabloodfleablood
71.1k22686
answered Nov 3 '16 at 18:01
fleabloodfleablood
71.1k22686
answered Nov 3 '16 at 18:01
fleabloodfleablood
71.1k22686
71.1k22686
add a comment |
add a comment |
$begingroup$
Prove, by strong induction, that if $nge12$, then $n=3a+7b$ for some positive integers $a$ and $b$.
Let's do the induction step, first. Suppose that $n>12$ and that, for $12le k<n$, $k=3a_k+7b_k$.
If $n-3ge 12$, then, by the induction hypothesis, $n-3=3a+7b$, so $n=3(a+1)+7b$. Otherwise $n-3<12$, that is, $n=12$, $n=13$ or $n=14$.
Since $12=3cdot4+7cdot0$, $13=3cdot2+7cdot1$ and $14=3cdot0+7cdot2$, we are done, by adding $3$. Also with the base case $n=12$ is obviously covered.
Can you see now why also the cases $n=13$ and $n=14$ are needed? When we do $n-3$ we can't assume that $n-3ge12$ and we must cope with the possibility $n-3<12$.
answered Nov 4 '16 at 0:19
egregegreg
182k1486204
$endgroup$
add a comment |
$begingroup$
Prove, by strong induction, that if $nge12$, then $n=3a+7b$ for some positive integers $a$ and $b$.
Let's do the induction step, first. Suppose that $n>12$ and that, for $12le k<n$, $k=3a_k+7b_k$.
If $n-3ge 12$, then, by the induction hypothesis, $n-3=3a+7b$, so $n=3(a+1)+7b$. Otherwise $n-3<12$, that is, $n=12$, $n=13$ or $n=14$.
Since $12=3cdot4+7cdot0$, $13=3cdot2+7cdot1$ and $14=3cdot0+7cdot2$, we are done, by adding $3$. Also with the base case $n=12$ is obviously covered.
Can you see now why also the cases $n=13$ and $n=14$ are needed? When we do $n-3$ we can't assume that $n-3ge12$ and we must cope with the possibility $n-3<12$.
answered Nov 4 '16 at 0:19
egregegreg
182k1486204
$endgroup$
add a comment |
$begingroup$
Prove, by strong induction, that if $nge12$, then $n=3a+7b$ for some positive integers $a$ and $b$.
Let's do the induction step, first. Suppose that $n>12$ and that, for $12le k<n$, $k=3a_k+7b_k$.
If $n-3ge 12$, then, by the induction hypothesis, $n-3=3a+7b$, so $n=3(a+1)+7b$. Otherwise $n-3<12$, that is, $n=12$, $n=13$ or $n=14$.
Since $12=3cdot4+7cdot0$, $13=3cdot2+7cdot1$ and $14=3cdot0+7cdot2$, we are done, by adding $3$. Also with the base case $n=12$ is obviously covered.
Can you see now why also the cases $n=13$ and $n=14$ are needed? When we do $n-3$ we can't assume that $n-3ge12$ and we must cope with the possibility $n-3<12$.
answered Nov 4 '16 at 0:19
egregegreg
182k1486204
$endgroup$
Prove, by strong induction, that if $nge12$, then $n=3a+7b$ for some positive integers $a$ and $b$.
Let's do the induction step, first. Suppose that $n>12$ and that, for $12le k<n$, $k=3a_k+7b_k$.
If $n-3ge 12$, then, by the induction hypothesis, $n-3=3a+7b$, so $n=3(a+1)+7b$. Otherwise $n-3<12$, that is, $n=12$, $n=13$ or $n=14$.
Since $12=3cdot4+7cdot0$, $13=3cdot2+7cdot1$ and $14=3cdot0+7cdot2$, we are done, by adding $3$. Also with the base case $n=12$ is obviously covered.
Can you see now why also the cases $n=13$ and $n=14$ are needed? When we do $n-3$ we can't assume that $n-3ge12$ and we must cope with the possibility $n-3<12$.
answered Nov 4 '16 at 0:19
egregegreg
182k1486204
answered Nov 4 '16 at 0:19
egregegreg
182k1486204
answered Nov 4 '16 at 0:19
egregegreg
182k1486204
answered Nov 4 '16 at 0:19
egregegreg
182k1486204
182k1486204
add a comment |
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%2f1997535%2funderstanding-this-proof-by-strong-induction-that-each-n%25e2%2589%25a512-is-n-3a-7b-for-s%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$
Well, try it. You need some base case...what do you propose?
$endgroup$
– lulu
Nov 3 '16 at 12:54
2
$begingroup$
Just to stress: it is not true that the fact that $n$ can be written as you want implies that $n+1$ can. $3=3times 1+7times 0$ but $4$ can't be written in the desired form.
$endgroup$
– lulu
Nov 3 '16 at 12:59
$begingroup$
Note: if you don't put it inside MathJax then $<$ is interpreted as the start of an HTML tag, and everything on the line after it does not show.
$endgroup$
– Graham Kemp
Nov 3 '16 at 13:02
$begingroup$
If the induction step were $P(n) implies P(n+1)$ we'd need only one base case. If the induction step were $P(n) implies P(n+2)$ then one base case would only prove it true for every other number and we'd need two base cases to prove for all numbers. Here your induction step is $P(n) implies P(n + 3)$ so one base case will only prove it for one third of the numbers. $P(12) implies P(n equiv 0 mod 3;n ge 12)$ which is not enough. $P(13) implies P(n equiv 1mod 3; n > 12)$. and we need $P(14)$ to get $P(nequiv 2 mod 3; n > 12)$.
$endgroup$
– fleablood
Nov 3 '16 at 18:58
$begingroup$
I remmeber the Chicken McNugget Theorem link
$endgroup$
– Ricardo Largaespada
Nov 4 '16 at 0:09