Mixing
A Question About The First Step In Induction [duplicate]
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
This question already has an answer here:
Dominoes and induction, or how does induction work?
7 answers
I am currently learning mathematical induction from this site (https://www.mathsisfun.com/algebra/mathematical-induction.html). It has broken induction into 3 steps:
- Show that it is true for n=1
- Assume it is true for n=k
- Show that it is true for n=k+1
I have 4 questions:
Why, of all numbers do we pick n=1? Can't we pick something like n=1, n=2, or the like?
Why do we need the 3rd step? I get a feeling it is to prove that it is true for all n=k, but if that is so, how does it do it? It does prove that it is true for all n=k+1, but that is based on the assumption that n=k; and therefore doesn't prove it. Because if a proof is based on an assumption, how does that prove anything?
Why do we need the first step when we show that it is true for all n=k+1?
In n=k+1, why do we add 1? Why can't we subtract 1, or add 2, etc? Why must it be n=k+1?
Is it possible to answer the question at the level of a Pre-Calc student, who hasn't learnt Calculus (obviously), set theory, and all those complicated stuff?
This question is different from "Dominoes and induction, or how does induction work?" because I have learnt neither limit notation nor L'Hopital's rule, and the other question contains them. This is important for a Precalc student who understands neither of them.
algebra-precalculus soft-question induction proof-explanation
asked Jul 29 at 14:40
Ethan Chan
603322
marked as duplicate by Hans Lundmark, Claude Leibovici, Micah, José Carlos Santos, John Ma Aug 3 at 18:52
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |Â
up vote
1
down vote
favorite
This question already has an answer here:
Dominoes and induction, or how does induction work?
7 answers
I am currently learning mathematical induction from this site (https://www.mathsisfun.com/algebra/mathematical-induction.html). It has broken induction into 3 steps:
- Show that it is true for n=1
- Assume it is true for n=k
- Show that it is true for n=k+1
I have 4 questions:
Why, of all numbers do we pick n=1? Can't we pick something like n=1, n=2, or the like?
Why do we need the 3rd step? I get a feeling it is to prove that it is true for all n=k, but if that is so, how does it do it? It does prove that it is true for all n=k+1, but that is based on the assumption that n=k; and therefore doesn't prove it. Because if a proof is based on an assumption, how does that prove anything?
Why do we need the first step when we show that it is true for all n=k+1?
In n=k+1, why do we add 1? Why can't we subtract 1, or add 2, etc? Why must it be n=k+1?
Is it possible to answer the question at the level of a Pre-Calc student, who hasn't learnt Calculus (obviously), set theory, and all those complicated stuff?
This question is different from "Dominoes and induction, or how does induction work?" because I have learnt neither limit notation nor L'Hopital's rule, and the other question contains them. This is important for a Precalc student who understands neither of them.
algebra-precalculus soft-question induction proof-explanation
asked Jul 29 at 14:40
Ethan Chan
603322
marked as duplicate by Hans Lundmark, Claude Leibovici, Micah, José Carlos Santos, John Ma Aug 3 at 18:52
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
You want to prove that a property holds for all natural numbers. Modifying the process, say picking n=2 instead of n=1 would prove it holds for 2,3,4... but that's not what you want.
– Yagger
Jul 29 at 14:49
@Yagger Can you explain why that isn't something we want? What's wrong with proving it holds for 2,3,4 etc, or even 0 or -1 etc.
– Ethan Chan
Jul 29 at 14:50
-1 isn't even a natural number so it doesn't make sense to start from there. What I mean is if you want to prove that a property holds for all naturals you have to take n=1 as the base case, as it has been pointed out in the answers. Starting from n=2 or proving that if something holds for n=k then it does for n=k+2 may be useful to prove something else, but not to prove that a property holds for any natural. By the way the source that you posted doesn't seem too reliable.
– Yagger
Jul 29 at 15:09
1
Possibly helpful: matheducators.stackexchange.com/questions/10021/…
– Ethan Bolker
Jul 29 at 15:15
2
@Yagger: Starting from $-1$ would be great if you are trying to prove something for all integers bigger than or equal to $-1$.
– Hurkyl
Jul 29 at 15:17
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
This question already has an answer here:
Dominoes and induction, or how does induction work?
7 answers
I am currently learning mathematical induction from this site (https://www.mathsisfun.com/algebra/mathematical-induction.html). It has broken induction into 3 steps:
- Show that it is true for n=1
- Assume it is true for n=k
- Show that it is true for n=k+1
I have 4 questions:
Why, of all numbers do we pick n=1? Can't we pick something like n=1, n=2, or the like?
Why do we need the 3rd step? I get a feeling it is to prove that it is true for all n=k, but if that is so, how does it do it? It does prove that it is true for all n=k+1, but that is based on the assumption that n=k; and therefore doesn't prove it. Because if a proof is based on an assumption, how does that prove anything?
Why do we need the first step when we show that it is true for all n=k+1?
In n=k+1, why do we add 1? Why can't we subtract 1, or add 2, etc? Why must it be n=k+1?
Is it possible to answer the question at the level of a Pre-Calc student, who hasn't learnt Calculus (obviously), set theory, and all those complicated stuff?
This question is different from "Dominoes and induction, or how does induction work?" because I have learnt neither limit notation nor L'Hopital's rule, and the other question contains them. This is important for a Precalc student who understands neither of them.
algebra-precalculus soft-question induction proof-explanation
asked Jul 29 at 14:40
Ethan Chan
603322
This question already has an answer here:
Dominoes and induction, or how does induction work?
7 answers
I am currently learning mathematical induction from this site (https://www.mathsisfun.com/algebra/mathematical-induction.html). It has broken induction into 3 steps:
- Show that it is true for n=1
- Assume it is true for n=k
- Show that it is true for n=k+1
I have 4 questions:
Why, of all numbers do we pick n=1? Can't we pick something like n=1, n=2, or the like?
Why do we need the 3rd step? I get a feeling it is to prove that it is true for all n=k, but if that is so, how does it do it? It does prove that it is true for all n=k+1, but that is based on the assumption that n=k; and therefore doesn't prove it. Because if a proof is based on an assumption, how does that prove anything?
Why do we need the first step when we show that it is true for all n=k+1?
In n=k+1, why do we add 1? Why can't we subtract 1, or add 2, etc? Why must it be n=k+1?
Is it possible to answer the question at the level of a Pre-Calc student, who hasn't learnt Calculus (obviously), set theory, and all those complicated stuff?
This question is different from "Dominoes and induction, or how does induction work?" because I have learnt neither limit notation nor L'Hopital's rule, and the other question contains them. This is important for a Precalc student who understands neither of them.
This question already has an answer here:
Dominoes and induction, or how does induction work?
7 answers
algebra-precalculus soft-question induction proof-explanation
asked Jul 29 at 14:40
Ethan Chan
603322
edited Jul 29 at 14:49
asked Jul 29 at 14:40
Ethan Chan
603322
asked Jul 29 at 14:40
Ethan Chan
603322
asked Jul 29 at 14:40
Ethan Chan
603322
603322
marked as duplicate by Hans Lundmark, Claude Leibovici, Micah, José Carlos Santos, John Ma Aug 3 at 18:52
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Hans Lundmark, Claude Leibovici, Micah, José Carlos Santos, John Ma Aug 3 at 18:52
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
1
You want to prove that a property holds for all natural numbers. Modifying the process, say picking n=2 instead of n=1 would prove it holds for 2,3,4... but that's not what you want.
– Yagger
Jul 29 at 14:49
@Yagger Can you explain why that isn't something we want? What's wrong with proving it holds for 2,3,4 etc, or even 0 or -1 etc.
– Ethan Chan
Jul 29 at 14:50
-1 isn't even a natural number so it doesn't make sense to start from there. What I mean is if you want to prove that a property holds for all naturals you have to take n=1 as the base case, as it has been pointed out in the answers. Starting from n=2 or proving that if something holds for n=k then it does for n=k+2 may be useful to prove something else, but not to prove that a property holds for any natural. By the way the source that you posted doesn't seem too reliable.
– Yagger
Jul 29 at 15:09
1
Possibly helpful: matheducators.stackexchange.com/questions/10021/…
– Ethan Bolker
Jul 29 at 15:15
2
@Yagger: Starting from $-1$ would be great if you are trying to prove something for all integers bigger than or equal to $-1$.
– Hurkyl
Jul 29 at 15:17
add a comment |Â
1
You want to prove that a property holds for all natural numbers. Modifying the process, say picking n=2 instead of n=1 would prove it holds for 2,3,4... but that's not what you want.
– Yagger
Jul 29 at 14:49
@Yagger Can you explain why that isn't something we want? What's wrong with proving it holds for 2,3,4 etc, or even 0 or -1 etc.
– Ethan Chan
Jul 29 at 14:50
-1 isn't even a natural number so it doesn't make sense to start from there. What I mean is if you want to prove that a property holds for all naturals you have to take n=1 as the base case, as it has been pointed out in the answers. Starting from n=2 or proving that if something holds for n=k then it does for n=k+2 may be useful to prove something else, but not to prove that a property holds for any natural. By the way the source that you posted doesn't seem too reliable.
– Yagger
Jul 29 at 15:09
1
Possibly helpful: matheducators.stackexchange.com/questions/10021/…
– Ethan Bolker
Jul 29 at 15:15
2
@Yagger: Starting from $-1$ would be great if you are trying to prove something for all integers bigger than or equal to $-1$.
– Hurkyl
Jul 29 at 15:17
1
1
You want to prove that a property holds for all natural numbers. Modifying the process, say picking n=2 instead of n=1 would prove it holds for 2,3,4... but that's not what you want.
– Yagger
Jul 29 at 14:49
You want to prove that a property holds for all natural numbers. Modifying the process, say picking n=2 instead of n=1 would prove it holds for 2,3,4... but that's not what you want.
– Yagger
Jul 29 at 14:49
@Yagger Can you explain why that isn't something we want? What's wrong with proving it holds for 2,3,4 etc, or even 0 or -1 etc.
– Ethan Chan
Jul 29 at 14:50
@Yagger Can you explain why that isn't something we want? What's wrong with proving it holds for 2,3,4 etc, or even 0 or -1 etc.
– Ethan Chan
Jul 29 at 14:50
-1 isn't even a natural number so it doesn't make sense to start from there. What I mean is if you want to prove that a property holds for all naturals you have to take n=1 as the base case, as it has been pointed out in the answers. Starting from n=2 or proving that if something holds for n=k then it does for n=k+2 may be useful to prove something else, but not to prove that a property holds for any natural. By the way the source that you posted doesn't seem too reliable.
– Yagger
Jul 29 at 15:09
-1 isn't even a natural number so it doesn't make sense to start from there. What I mean is if you want to prove that a property holds for all naturals you have to take n=1 as the base case, as it has been pointed out in the answers. Starting from n=2 or proving that if something holds for n=k then it does for n=k+2 may be useful to prove something else, but not to prove that a property holds for any natural. By the way the source that you posted doesn't seem too reliable.
– Yagger
Jul 29 at 15:09
1
1
Possibly helpful: matheducators.stackexchange.com/questions/10021/…
– Ethan Bolker
Jul 29 at 15:15
Possibly helpful: matheducators.stackexchange.com/questions/10021/…
– Ethan Bolker
Jul 29 at 15:15
2
2
@Yagger: Starting from $-1$ would be great if you are trying to prove something for all integers bigger than or equal to $-1$.
– Hurkyl
Jul 29 at 15:17
@Yagger: Starting from $-1$ would be great if you are trying to prove something for all integers bigger than or equal to $-1$.
– Hurkyl
Jul 29 at 15:17
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
4
down vote
Actually steps 2 and 3 should be grouped: what we have to prove is that from one case follows the next case, i.e. if we denote the property to be proved as $P(k)$, we really prove this:
$$forall k,enspace P(k)implies P(k+1),$$
and as for all implications, to prove $;Aimplies B$, we show that if the premise $A$ is true, then the conclusion $B$ is necessarily true.
Intuitively, why does this work?
Well we've proved the initial case $n=1$ (or whatever …). If the inductive step has been proved, there follows that the case $n=2$ is true. So the case $n=3$ is true. Repeat this, say, 99 times, and you've proved it's true for $n=100$.
The induction theorem asserts that if you've proved an initial case $n_0$, and you've proved the inductive step: $P(n)implies P(n+1)$ (not $P(n)$ nor $P(n+1)$ alone, but the implication), then $P(n)$ is true for all $nge n_0$.
answered Jul 29 at 15:13
Bernard
110k635102
add a comment |Â
up vote
1
down vote
- You can prove it for $n=2$ or even $n=1000$ but then the induction proves the statement is true for $Ngeq 1000$ rather than $Ngeq 1$. It really depends on what you are trying to prove.
The rest of the questions sound a little like rambling because you do not understand what is happening when you use a proof by induction. I will try to explain that to you.
So first we prove that the statement is true for $n=1$ (or some other number, that is irrelevant).
Next, we show that if the statement is true for $n=k$ then it is true for $n=k+1$. Keep in mind, that we have not proved that the statement is true for $n=k$, we have proved the implication, " If the statement is true for $n=k$, then it is true for $n=k+1$". In layman terms, we have proved that if the statement is true for some number, then the statement has to be true for the next one.
Once we have done that, we go back to the first step we have done. We have shown that the statement is true for $n=1$, by our proof, that means the statement is true for the next number, $n=2$. But now, we know it is true for the next number $n=3$. etc, we do that continuously and so we have proven that the statement is true for all $Ngeq 1$
Regarding question 4. If you prove the implication for $n=k+2$ then try to think why the reasoning above does not apply.
answered Jul 29 at 14:50
Sorfosh
910616
A "for example" on your last paragraph would help. Or even talking about how some inductions have different behaviours on odd and even indexes. Or stuff with a multi-step recurrence like X_n+2 =f(x_n)+g(x_n+1)
– JKreft
Jul 29 at 14:57
@JKreft I honestly did not want to overcomplicate it. Sure induction works if you prove it for $n=k+2$ and just show the statement is true for two consecutive starting values, but I felt it was not necessary.
– Sorfosh
Jul 29 at 15:02
Fair enough. I just thought you might help in thinking along why the reasoning might not apply. :)
– JKreft
Jul 29 at 15:34
add a comment |Â
up vote
0
down vote
Close your eyes and imagine you have a three years old boy and a very tall ladder.
The boy learns how to climb one step at the time.
If the boy does not get on the ladder then you can relax.
On the other hand if the boy somehow gets on the first step of the ladder you will soon find him on the second and on the third and so forth.
Thus it is important to start at some point and it could be one or two or any other integer.It is also important to know that we can go one step higher at any time.
Now if you have P(1) and if you can conclude P(k+1) from P(k), and if you accept the Mathematical Induction as a valid proof, then the statement P(n) is true for all $nge 1 $
answered Jul 29 at 14:58
Mohammad Riazi-Kermani
27.3k41851
@mr_e_man If the boy does not get on the ladder then you can relax.
– Mohammad Riazi-Kermani
Jul 30 at 12:46
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
Actually steps 2 and 3 should be grouped: what we have to prove is that from one case follows the next case, i.e. if we denote the property to be proved as $P(k)$, we really prove this:
$$forall k,enspace P(k)implies P(k+1),$$
and as for all implications, to prove $;Aimplies B$, we show that if the premise $A$ is true, then the conclusion $B$ is necessarily true.
Intuitively, why does this work?
Well we've proved the initial case $n=1$ (or whatever …). If the inductive step has been proved, there follows that the case $n=2$ is true. So the case $n=3$ is true. Repeat this, say, 99 times, and you've proved it's true for $n=100$.
The induction theorem asserts that if you've proved an initial case $n_0$, and you've proved the inductive step: $P(n)implies P(n+1)$ (not $P(n)$ nor $P(n+1)$ alone, but the implication), then $P(n)$ is true for all $nge n_0$.
answered Jul 29 at 15:13
Bernard
110k635102
add a comment |Â
up vote
4
down vote
Actually steps 2 and 3 should be grouped: what we have to prove is that from one case follows the next case, i.e. if we denote the property to be proved as $P(k)$, we really prove this:
$$forall k,enspace P(k)implies P(k+1),$$
and as for all implications, to prove $;Aimplies B$, we show that if the premise $A$ is true, then the conclusion $B$ is necessarily true.
Intuitively, why does this work?
Well we've proved the initial case $n=1$ (or whatever …). If the inductive step has been proved, there follows that the case $n=2$ is true. So the case $n=3$ is true. Repeat this, say, 99 times, and you've proved it's true for $n=100$.
The induction theorem asserts that if you've proved an initial case $n_0$, and you've proved the inductive step: $P(n)implies P(n+1)$ (not $P(n)$ nor $P(n+1)$ alone, but the implication), then $P(n)$ is true for all $nge n_0$.
answered Jul 29 at 15:13
Bernard
110k635102
add a comment |Â
up vote
4
down vote
up vote
4
down vote
Actually steps 2 and 3 should be grouped: what we have to prove is that from one case follows the next case, i.e. if we denote the property to be proved as $P(k)$, we really prove this:
$$forall k,enspace P(k)implies P(k+1),$$
and as for all implications, to prove $;Aimplies B$, we show that if the premise $A$ is true, then the conclusion $B$ is necessarily true.
Intuitively, why does this work?
Well we've proved the initial case $n=1$ (or whatever …). If the inductive step has been proved, there follows that the case $n=2$ is true. So the case $n=3$ is true. Repeat this, say, 99 times, and you've proved it's true for $n=100$.
The induction theorem asserts that if you've proved an initial case $n_0$, and you've proved the inductive step: $P(n)implies P(n+1)$ (not $P(n)$ nor $P(n+1)$ alone, but the implication), then $P(n)$ is true for all $nge n_0$.
answered Jul 29 at 15:13
Bernard
110k635102
Actually steps 2 and 3 should be grouped: what we have to prove is that from one case follows the next case, i.e. if we denote the property to be proved as $P(k)$, we really prove this:
$$forall k,enspace P(k)implies P(k+1),$$
and as for all implications, to prove $;Aimplies B$, we show that if the premise $A$ is true, then the conclusion $B$ is necessarily true.
Intuitively, why does this work?
Well we've proved the initial case $n=1$ (or whatever …). If the inductive step has been proved, there follows that the case $n=2$ is true. So the case $n=3$ is true. Repeat this, say, 99 times, and you've proved it's true for $n=100$.
The induction theorem asserts that if you've proved an initial case $n_0$, and you've proved the inductive step: $P(n)implies P(n+1)$ (not $P(n)$ nor $P(n+1)$ alone, but the implication), then $P(n)$ is true for all $nge n_0$.
answered Jul 29 at 15:13
Bernard
110k635102
edited Jul 30 at 8:08
answered Jul 29 at 15:13
Bernard
110k635102
answered Jul 29 at 15:13
Bernard
110k635102
answered Jul 29 at 15:13
Bernard
110k635102
110k635102
add a comment |Â
add a comment |Â
up vote
1
down vote
- You can prove it for $n=2$ or even $n=1000$ but then the induction proves the statement is true for $Ngeq 1000$ rather than $Ngeq 1$. It really depends on what you are trying to prove.
The rest of the questions sound a little like rambling because you do not understand what is happening when you use a proof by induction. I will try to explain that to you.
So first we prove that the statement is true for $n=1$ (or some other number, that is irrelevant).
Next, we show that if the statement is true for $n=k$ then it is true for $n=k+1$. Keep in mind, that we have not proved that the statement is true for $n=k$, we have proved the implication, " If the statement is true for $n=k$, then it is true for $n=k+1$". In layman terms, we have proved that if the statement is true for some number, then the statement has to be true for the next one.
Once we have done that, we go back to the first step we have done. We have shown that the statement is true for $n=1$, by our proof, that means the statement is true for the next number, $n=2$. But now, we know it is true for the next number $n=3$. etc, we do that continuously and so we have proven that the statement is true for all $Ngeq 1$
Regarding question 4. If you prove the implication for $n=k+2$ then try to think why the reasoning above does not apply.
answered Jul 29 at 14:50
Sorfosh
910616
A "for example" on your last paragraph would help. Or even talking about how some inductions have different behaviours on odd and even indexes. Or stuff with a multi-step recurrence like X_n+2 =f(x_n)+g(x_n+1)
– JKreft
Jul 29 at 14:57
@JKreft I honestly did not want to overcomplicate it. Sure induction works if you prove it for $n=k+2$ and just show the statement is true for two consecutive starting values, but I felt it was not necessary.
– Sorfosh
Jul 29 at 15:02
Fair enough. I just thought you might help in thinking along why the reasoning might not apply. :)
– JKreft
Jul 29 at 15:34
add a comment |Â
up vote
1
down vote
- You can prove it for $n=2$ or even $n=1000$ but then the induction proves the statement is true for $Ngeq 1000$ rather than $Ngeq 1$. It really depends on what you are trying to prove.
The rest of the questions sound a little like rambling because you do not understand what is happening when you use a proof by induction. I will try to explain that to you.
So first we prove that the statement is true for $n=1$ (or some other number, that is irrelevant).
Next, we show that if the statement is true for $n=k$ then it is true for $n=k+1$. Keep in mind, that we have not proved that the statement is true for $n=k$, we have proved the implication, " If the statement is true for $n=k$, then it is true for $n=k+1$". In layman terms, we have proved that if the statement is true for some number, then the statement has to be true for the next one.
Once we have done that, we go back to the first step we have done. We have shown that the statement is true for $n=1$, by our proof, that means the statement is true for the next number, $n=2$. But now, we know it is true for the next number $n=3$. etc, we do that continuously and so we have proven that the statement is true for all $Ngeq 1$
Regarding question 4. If you prove the implication for $n=k+2$ then try to think why the reasoning above does not apply.
answered Jul 29 at 14:50
Sorfosh
910616
A "for example" on your last paragraph would help. Or even talking about how some inductions have different behaviours on odd and even indexes. Or stuff with a multi-step recurrence like X_n+2 =f(x_n)+g(x_n+1)
– JKreft
Jul 29 at 14:57
@JKreft I honestly did not want to overcomplicate it. Sure induction works if you prove it for $n=k+2$ and just show the statement is true for two consecutive starting values, but I felt it was not necessary.
– Sorfosh
Jul 29 at 15:02
Fair enough. I just thought you might help in thinking along why the reasoning might not apply. :)
– JKreft
Jul 29 at 15:34
add a comment |Â
up vote
1
down vote
up vote
1
down vote
- You can prove it for $n=2$ or even $n=1000$ but then the induction proves the statement is true for $Ngeq 1000$ rather than $Ngeq 1$. It really depends on what you are trying to prove.
The rest of the questions sound a little like rambling because you do not understand what is happening when you use a proof by induction. I will try to explain that to you.
So first we prove that the statement is true for $n=1$ (or some other number, that is irrelevant).
Next, we show that if the statement is true for $n=k$ then it is true for $n=k+1$. Keep in mind, that we have not proved that the statement is true for $n=k$, we have proved the implication, " If the statement is true for $n=k$, then it is true for $n=k+1$". In layman terms, we have proved that if the statement is true for some number, then the statement has to be true for the next one.
Once we have done that, we go back to the first step we have done. We have shown that the statement is true for $n=1$, by our proof, that means the statement is true for the next number, $n=2$. But now, we know it is true for the next number $n=3$. etc, we do that continuously and so we have proven that the statement is true for all $Ngeq 1$
Regarding question 4. If you prove the implication for $n=k+2$ then try to think why the reasoning above does not apply.
answered Jul 29 at 14:50
Sorfosh
910616
- You can prove it for $n=2$ or even $n=1000$ but then the induction proves the statement is true for $Ngeq 1000$ rather than $Ngeq 1$. It really depends on what you are trying to prove.
The rest of the questions sound a little like rambling because you do not understand what is happening when you use a proof by induction. I will try to explain that to you.
So first we prove that the statement is true for $n=1$ (or some other number, that is irrelevant).
Next, we show that if the statement is true for $n=k$ then it is true for $n=k+1$. Keep in mind, that we have not proved that the statement is true for $n=k$, we have proved the implication, " If the statement is true for $n=k$, then it is true for $n=k+1$". In layman terms, we have proved that if the statement is true for some number, then the statement has to be true for the next one.
Once we have done that, we go back to the first step we have done. We have shown that the statement is true for $n=1$, by our proof, that means the statement is true for the next number, $n=2$. But now, we know it is true for the next number $n=3$. etc, we do that continuously and so we have proven that the statement is true for all $Ngeq 1$
Regarding question 4. If you prove the implication for $n=k+2$ then try to think why the reasoning above does not apply.
answered Jul 29 at 14:50
Sorfosh
910616
answered Jul 29 at 14:50
Sorfosh
910616
answered Jul 29 at 14:50
Sorfosh
910616
answered Jul 29 at 14:50
Sorfosh
910616
910616
A "for example" on your last paragraph would help. Or even talking about how some inductions have different behaviours on odd and even indexes. Or stuff with a multi-step recurrence like X_n+2 =f(x_n)+g(x_n+1)
– JKreft
Jul 29 at 14:57
@JKreft I honestly did not want to overcomplicate it. Sure induction works if you prove it for $n=k+2$ and just show the statement is true for two consecutive starting values, but I felt it was not necessary.
– Sorfosh
Jul 29 at 15:02
Fair enough. I just thought you might help in thinking along why the reasoning might not apply. :)
– JKreft
Jul 29 at 15:34
add a comment |Â
A "for example" on your last paragraph would help. Or even talking about how some inductions have different behaviours on odd and even indexes. Or stuff with a multi-step recurrence like X_n+2 =f(x_n)+g(x_n+1)
– JKreft
Jul 29 at 14:57
@JKreft I honestly did not want to overcomplicate it. Sure induction works if you prove it for $n=k+2$ and just show the statement is true for two consecutive starting values, but I felt it was not necessary.
– Sorfosh
Jul 29 at 15:02
Fair enough. I just thought you might help in thinking along why the reasoning might not apply. :)
– JKreft
Jul 29 at 15:34
A "for example" on your last paragraph would help. Or even talking about how some inductions have different behaviours on odd and even indexes. Or stuff with a multi-step recurrence like X_n+2 =f(x_n)+g(x_n+1)
– JKreft
Jul 29 at 14:57
A "for example" on your last paragraph would help. Or even talking about how some inductions have different behaviours on odd and even indexes. Or stuff with a multi-step recurrence like X_n+2 =f(x_n)+g(x_n+1)
– JKreft
Jul 29 at 14:57
@JKreft I honestly did not want to overcomplicate it. Sure induction works if you prove it for $n=k+2$ and just show the statement is true for two consecutive starting values, but I felt it was not necessary.
– Sorfosh
Jul 29 at 15:02
@JKreft I honestly did not want to overcomplicate it. Sure induction works if you prove it for $n=k+2$ and just show the statement is true for two consecutive starting values, but I felt it was not necessary.
– Sorfosh
Jul 29 at 15:02
Fair enough. I just thought you might help in thinking along why the reasoning might not apply. :)
– JKreft
Jul 29 at 15:34
Fair enough. I just thought you might help in thinking along why the reasoning might not apply. :)
– JKreft
Jul 29 at 15:34
add a comment |Â
up vote
0
down vote
Close your eyes and imagine you have a three years old boy and a very tall ladder.
The boy learns how to climb one step at the time.
If the boy does not get on the ladder then you can relax.
On the other hand if the boy somehow gets on the first step of the ladder you will soon find him on the second and on the third and so forth.
Thus it is important to start at some point and it could be one or two or any other integer.It is also important to know that we can go one step higher at any time.
Now if you have P(1) and if you can conclude P(k+1) from P(k), and if you accept the Mathematical Induction as a valid proof, then the statement P(n) is true for all $nge 1 $
answered Jul 29 at 14:58
Mohammad Riazi-Kermani
27.3k41851
@mr_e_man If the boy does not get on the ladder then you can relax.
– Mohammad Riazi-Kermani
Jul 30 at 12:46
add a comment |Â
up vote
0
down vote
Close your eyes and imagine you have a three years old boy and a very tall ladder.
The boy learns how to climb one step at the time.
If the boy does not get on the ladder then you can relax.
On the other hand if the boy somehow gets on the first step of the ladder you will soon find him on the second and on the third and so forth.
Thus it is important to start at some point and it could be one or two or any other integer.It is also important to know that we can go one step higher at any time.
Now if you have P(1) and if you can conclude P(k+1) from P(k), and if you accept the Mathematical Induction as a valid proof, then the statement P(n) is true for all $nge 1 $
answered Jul 29 at 14:58
Mohammad Riazi-Kermani
27.3k41851
@mr_e_man If the boy does not get on the ladder then you can relax.
– Mohammad Riazi-Kermani
Jul 30 at 12:46
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Close your eyes and imagine you have a three years old boy and a very tall ladder.
The boy learns how to climb one step at the time.
If the boy does not get on the ladder then you can relax.
On the other hand if the boy somehow gets on the first step of the ladder you will soon find him on the second and on the third and so forth.
Thus it is important to start at some point and it could be one or two or any other integer.It is also important to know that we can go one step higher at any time.
Now if you have P(1) and if you can conclude P(k+1) from P(k), and if you accept the Mathematical Induction as a valid proof, then the statement P(n) is true for all $nge 1 $
answered Jul 29 at 14:58
Mohammad Riazi-Kermani
27.3k41851
Close your eyes and imagine you have a three years old boy and a very tall ladder.
The boy learns how to climb one step at the time.
If the boy does not get on the ladder then you can relax.
On the other hand if the boy somehow gets on the first step of the ladder you will soon find him on the second and on the third and so forth.
Thus it is important to start at some point and it could be one or two or any other integer.It is also important to know that we can go one step higher at any time.
Now if you have P(1) and if you can conclude P(k+1) from P(k), and if you accept the Mathematical Induction as a valid proof, then the statement P(n) is true for all $nge 1 $
answered Jul 29 at 14:58
Mohammad Riazi-Kermani
27.3k41851
edited Jul 30 at 12:44
answered Jul 29 at 14:58
Mohammad Riazi-Kermani
27.3k41851
answered Jul 29 at 14:58
Mohammad Riazi-Kermani
27.3k41851
answered Jul 29 at 14:58
Mohammad Riazi-Kermani
27.3k41851
27.3k41851
@mr_e_man If the boy does not get on the ladder then you can relax.
– Mohammad Riazi-Kermani
Jul 30 at 12:46
add a comment |Â
@mr_e_man If the boy does not get on the ladder then you can relax.
– Mohammad Riazi-Kermani
Jul 30 at 12:46
@mr_e_man If the boy does not get on the ladder then you can relax.
– Mohammad Riazi-Kermani
Jul 30 at 12:46
@mr_e_man If the boy does not get on the ladder then you can relax.
– Mohammad Riazi-Kermani
Jul 30 at 12:46
add a comment |Â
1
You want to prove that a property holds for all natural numbers. Modifying the process, say picking n=2 instead of n=1 would prove it holds for 2,3,4... but that's not what you want.
– Yagger
Jul 29 at 14:49
@Yagger Can you explain why that isn't something we want? What's wrong with proving it holds for 2,3,4 etc, or even 0 or -1 etc.
– Ethan Chan
Jul 29 at 14:50
-1 isn't even a natural number so it doesn't make sense to start from there. What I mean is if you want to prove that a property holds for all naturals you have to take n=1 as the base case, as it has been pointed out in the answers. Starting from n=2 or proving that if something holds for n=k then it does for n=k+2 may be useful to prove something else, but not to prove that a property holds for any natural. By the way the source that you posted doesn't seem too reliable.
– Yagger
Jul 29 at 15:09
1
Possibly helpful: matheducators.stackexchange.com/questions/10021/…
– Ethan Bolker
Jul 29 at 15:15
2
@Yagger: Starting from $-1$ would be great if you are trying to prove something for all integers bigger than or equal to $-1$.
– Hurkyl
Jul 29 at 15:17