Induction definition
up vote
0
down vote
favorite
Suppose $T$ is a subset of $N$
Property 1: $0 in T$, and
Property 2: For every natural number $n ge 1$, if $n − 1 in T$ then $n in T$
Hi this is how POI is introduced in my notes and then it is stated in the more common way. Im wondering if this version is really useful at all i cant see the point in stating it this way?
Maybe you can help me thanks
induction
add a comment |
up vote
0
down vote
favorite
Suppose $T$ is a subset of $N$
Property 1: $0 in T$, and
Property 2: For every natural number $n ge 1$, if $n − 1 in T$ then $n in T$
Hi this is how POI is introduced in my notes and then it is stated in the more common way. Im wondering if this version is really useful at all i cant see the point in stating it this way?
Maybe you can help me thanks
induction
I think the definition is technically imprecise. The second property is correct, though it's often stated that if $n in T$ then $n + 1 in T$. The first property technically is not correct since we never require a base case of $n = 0$: some statements work only for, say, integers at least $2$. I do think it's useful to think of $T$ as a subset of $mathbb{N}$ to symbolize that we could be talking about all natural numbers (assuming we start with $0$ or $1$, depending on how you define $mathbb{N}$) or all naturals after some point.
– Matt.P
Nov 18 at 0:54
what is what you called 'more common way'?
– Robson
Nov 18 at 1:00
where property 2 is if n is in T then n+1 is in T. This just seems more useful to me, and the one stated above to me seems more unclear
– Carlos Bacca
Nov 18 at 1:02
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Suppose $T$ is a subset of $N$
Property 1: $0 in T$, and
Property 2: For every natural number $n ge 1$, if $n − 1 in T$ then $n in T$
Hi this is how POI is introduced in my notes and then it is stated in the more common way. Im wondering if this version is really useful at all i cant see the point in stating it this way?
Maybe you can help me thanks
induction
Suppose $T$ is a subset of $N$
Property 1: $0 in T$, and
Property 2: For every natural number $n ge 1$, if $n − 1 in T$ then $n in T$
Hi this is how POI is introduced in my notes and then it is stated in the more common way. Im wondering if this version is really useful at all i cant see the point in stating it this way?
Maybe you can help me thanks
induction
induction
edited Nov 18 at 2:16
hanszimmer
195
195
asked Nov 18 at 0:49
Carlos Bacca
171116
171116
I think the definition is technically imprecise. The second property is correct, though it's often stated that if $n in T$ then $n + 1 in T$. The first property technically is not correct since we never require a base case of $n = 0$: some statements work only for, say, integers at least $2$. I do think it's useful to think of $T$ as a subset of $mathbb{N}$ to symbolize that we could be talking about all natural numbers (assuming we start with $0$ or $1$, depending on how you define $mathbb{N}$) or all naturals after some point.
– Matt.P
Nov 18 at 0:54
what is what you called 'more common way'?
– Robson
Nov 18 at 1:00
where property 2 is if n is in T then n+1 is in T. This just seems more useful to me, and the one stated above to me seems more unclear
– Carlos Bacca
Nov 18 at 1:02
add a comment |
I think the definition is technically imprecise. The second property is correct, though it's often stated that if $n in T$ then $n + 1 in T$. The first property technically is not correct since we never require a base case of $n = 0$: some statements work only for, say, integers at least $2$. I do think it's useful to think of $T$ as a subset of $mathbb{N}$ to symbolize that we could be talking about all natural numbers (assuming we start with $0$ or $1$, depending on how you define $mathbb{N}$) or all naturals after some point.
– Matt.P
Nov 18 at 0:54
what is what you called 'more common way'?
– Robson
Nov 18 at 1:00
where property 2 is if n is in T then n+1 is in T. This just seems more useful to me, and the one stated above to me seems more unclear
– Carlos Bacca
Nov 18 at 1:02
I think the definition is technically imprecise. The second property is correct, though it's often stated that if $n in T$ then $n + 1 in T$. The first property technically is not correct since we never require a base case of $n = 0$: some statements work only for, say, integers at least $2$. I do think it's useful to think of $T$ as a subset of $mathbb{N}$ to symbolize that we could be talking about all natural numbers (assuming we start with $0$ or $1$, depending on how you define $mathbb{N}$) or all naturals after some point.
– Matt.P
Nov 18 at 0:54
I think the definition is technically imprecise. The second property is correct, though it's often stated that if $n in T$ then $n + 1 in T$. The first property technically is not correct since we never require a base case of $n = 0$: some statements work only for, say, integers at least $2$. I do think it's useful to think of $T$ as a subset of $mathbb{N}$ to symbolize that we could be talking about all natural numbers (assuming we start with $0$ or $1$, depending on how you define $mathbb{N}$) or all naturals after some point.
– Matt.P
Nov 18 at 0:54
what is what you called 'more common way'?
– Robson
Nov 18 at 1:00
what is what you called 'more common way'?
– Robson
Nov 18 at 1:00
where property 2 is if n is in T then n+1 is in T. This just seems more useful to me, and the one stated above to me seems more unclear
– Carlos Bacca
Nov 18 at 1:02
where property 2 is if n is in T then n+1 is in T. This just seems more useful to me, and the one stated above to me seems more unclear
– Carlos Bacca
Nov 18 at 1:02
add a comment |
3 Answers
3
active
oldest
votes
up vote
1
down vote
accepted
Yes that is a valid definition of induction method .
Probably you worry about the starting point of $0$ instead of $1$ because usually they start with $n=1$
You can start at any integer and go from there depending on the problem.
add a comment |
up vote
1
down vote
You can enunciate the principle of finite induction (PFI) in many ways! A nice approach that helps visualizing equivalence between different statements about PFI is to imagine that you are going up stairs.
Property one says simply where you begin your rise. You could prove that some math statements works for all $ngeq 2$ and induction is used there too! For example, Fermat's Last Theorem! (Although that its not just induction which solves it hehehe)
Property two says just how you walk up the stairs. The main point is that from where you started PIF guarantees you will go through all steps up the stairs.
Saying "if its valid for $n-1$ then it works too for $n$, for all $n$" also guarantees our climb because you DO know that you got in step $0$ (by property one) and you can use $0=n-1$ and prove that you ALSO can go to step $1=n$... and so one. That's exactly the same thing that saying that "if its valid for $n$ then it works too for $n$, for all $n+1$"... you just name $0=n$ and then $1=n+1$ and so on.
The first way maybe is more "esthetically good" because you were asked to prove some statement for all $n$ and finishes your proof by showing that some property is also valid for some generical $n$ (instead of some generical $n+1$)
add a comment |
up vote
0
down vote
What I like about this POI is that it focuses on set membership and not equations. This is what I mean. Consider the equation $$forall n in mathbb N, sum_{i=0}^n i = dfrac 12n(n+1)tag{1}$$ A proof using your version of POI would go as follows.
Let $displaystyle mathbf T = left{n in mathbb N: sum_{i=0}^n i = dfrac 12n(n+1)right}$. (Note $mathbf T subseteq mathbb N.$)
STEP $1$. Since $sum_{i=0}^0 i =0= dfrac 120(0+1)$, then $0 in mathbf T$.
STEP $2$. Suppose for some natural number, $n > 0$, that $n-1 in mathbf T$. Then
$displaystyle sum_{i=0}^{n-1} i = dfrac 12(n-1)(n)$. So
begin{align}
sum_{i=0}^{n} i
&= sum_{i=0}^{n-1} i + sum_{i=n}^{n} i \
&= dfrac 12(n-1)(n) + n \
&= dfrac 12(n^2 - n + 2n) \
&= dfrac 12 n(n+1).
end{align}
Hence $n-1 in mathbf T implies n in mathbf T$.
It follows, from POI, that $mathbf T = mathbb N$. Hence equation $(1)$ is proved.
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Yes that is a valid definition of induction method .
Probably you worry about the starting point of $0$ instead of $1$ because usually they start with $n=1$
You can start at any integer and go from there depending on the problem.
add a comment |
up vote
1
down vote
accepted
Yes that is a valid definition of induction method .
Probably you worry about the starting point of $0$ instead of $1$ because usually they start with $n=1$
You can start at any integer and go from there depending on the problem.
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Yes that is a valid definition of induction method .
Probably you worry about the starting point of $0$ instead of $1$ because usually they start with $n=1$
You can start at any integer and go from there depending on the problem.
Yes that is a valid definition of induction method .
Probably you worry about the starting point of $0$ instead of $1$ because usually they start with $n=1$
You can start at any integer and go from there depending on the problem.
answered Nov 18 at 0:57
Mohammad Riazi-Kermani
40.3k41958
40.3k41958
add a comment |
add a comment |
up vote
1
down vote
You can enunciate the principle of finite induction (PFI) in many ways! A nice approach that helps visualizing equivalence between different statements about PFI is to imagine that you are going up stairs.
Property one says simply where you begin your rise. You could prove that some math statements works for all $ngeq 2$ and induction is used there too! For example, Fermat's Last Theorem! (Although that its not just induction which solves it hehehe)
Property two says just how you walk up the stairs. The main point is that from where you started PIF guarantees you will go through all steps up the stairs.
Saying "if its valid for $n-1$ then it works too for $n$, for all $n$" also guarantees our climb because you DO know that you got in step $0$ (by property one) and you can use $0=n-1$ and prove that you ALSO can go to step $1=n$... and so one. That's exactly the same thing that saying that "if its valid for $n$ then it works too for $n$, for all $n+1$"... you just name $0=n$ and then $1=n+1$ and so on.
The first way maybe is more "esthetically good" because you were asked to prove some statement for all $n$ and finishes your proof by showing that some property is also valid for some generical $n$ (instead of some generical $n+1$)
add a comment |
up vote
1
down vote
You can enunciate the principle of finite induction (PFI) in many ways! A nice approach that helps visualizing equivalence between different statements about PFI is to imagine that you are going up stairs.
Property one says simply where you begin your rise. You could prove that some math statements works for all $ngeq 2$ and induction is used there too! For example, Fermat's Last Theorem! (Although that its not just induction which solves it hehehe)
Property two says just how you walk up the stairs. The main point is that from where you started PIF guarantees you will go through all steps up the stairs.
Saying "if its valid for $n-1$ then it works too for $n$, for all $n$" also guarantees our climb because you DO know that you got in step $0$ (by property one) and you can use $0=n-1$ and prove that you ALSO can go to step $1=n$... and so one. That's exactly the same thing that saying that "if its valid for $n$ then it works too for $n$, for all $n+1$"... you just name $0=n$ and then $1=n+1$ and so on.
The first way maybe is more "esthetically good" because you were asked to prove some statement for all $n$ and finishes your proof by showing that some property is also valid for some generical $n$ (instead of some generical $n+1$)
add a comment |
up vote
1
down vote
up vote
1
down vote
You can enunciate the principle of finite induction (PFI) in many ways! A nice approach that helps visualizing equivalence between different statements about PFI is to imagine that you are going up stairs.
Property one says simply where you begin your rise. You could prove that some math statements works for all $ngeq 2$ and induction is used there too! For example, Fermat's Last Theorem! (Although that its not just induction which solves it hehehe)
Property two says just how you walk up the stairs. The main point is that from where you started PIF guarantees you will go through all steps up the stairs.
Saying "if its valid for $n-1$ then it works too for $n$, for all $n$" also guarantees our climb because you DO know that you got in step $0$ (by property one) and you can use $0=n-1$ and prove that you ALSO can go to step $1=n$... and so one. That's exactly the same thing that saying that "if its valid for $n$ then it works too for $n$, for all $n+1$"... you just name $0=n$ and then $1=n+1$ and so on.
The first way maybe is more "esthetically good" because you were asked to prove some statement for all $n$ and finishes your proof by showing that some property is also valid for some generical $n$ (instead of some generical $n+1$)
You can enunciate the principle of finite induction (PFI) in many ways! A nice approach that helps visualizing equivalence between different statements about PFI is to imagine that you are going up stairs.
Property one says simply where you begin your rise. You could prove that some math statements works for all $ngeq 2$ and induction is used there too! For example, Fermat's Last Theorem! (Although that its not just induction which solves it hehehe)
Property two says just how you walk up the stairs. The main point is that from where you started PIF guarantees you will go through all steps up the stairs.
Saying "if its valid for $n-1$ then it works too for $n$, for all $n$" also guarantees our climb because you DO know that you got in step $0$ (by property one) and you can use $0=n-1$ and prove that you ALSO can go to step $1=n$... and so one. That's exactly the same thing that saying that "if its valid for $n$ then it works too for $n$, for all $n+1$"... you just name $0=n$ and then $1=n+1$ and so on.
The first way maybe is more "esthetically good" because you were asked to prove some statement for all $n$ and finishes your proof by showing that some property is also valid for some generical $n$ (instead of some generical $n+1$)
edited Nov 18 at 1:20
answered Nov 18 at 1:12
Robson
751221
751221
add a comment |
add a comment |
up vote
0
down vote
What I like about this POI is that it focuses on set membership and not equations. This is what I mean. Consider the equation $$forall n in mathbb N, sum_{i=0}^n i = dfrac 12n(n+1)tag{1}$$ A proof using your version of POI would go as follows.
Let $displaystyle mathbf T = left{n in mathbb N: sum_{i=0}^n i = dfrac 12n(n+1)right}$. (Note $mathbf T subseteq mathbb N.$)
STEP $1$. Since $sum_{i=0}^0 i =0= dfrac 120(0+1)$, then $0 in mathbf T$.
STEP $2$. Suppose for some natural number, $n > 0$, that $n-1 in mathbf T$. Then
$displaystyle sum_{i=0}^{n-1} i = dfrac 12(n-1)(n)$. So
begin{align}
sum_{i=0}^{n} i
&= sum_{i=0}^{n-1} i + sum_{i=n}^{n} i \
&= dfrac 12(n-1)(n) + n \
&= dfrac 12(n^2 - n + 2n) \
&= dfrac 12 n(n+1).
end{align}
Hence $n-1 in mathbf T implies n in mathbf T$.
It follows, from POI, that $mathbf T = mathbb N$. Hence equation $(1)$ is proved.
add a comment |
up vote
0
down vote
What I like about this POI is that it focuses on set membership and not equations. This is what I mean. Consider the equation $$forall n in mathbb N, sum_{i=0}^n i = dfrac 12n(n+1)tag{1}$$ A proof using your version of POI would go as follows.
Let $displaystyle mathbf T = left{n in mathbb N: sum_{i=0}^n i = dfrac 12n(n+1)right}$. (Note $mathbf T subseteq mathbb N.$)
STEP $1$. Since $sum_{i=0}^0 i =0= dfrac 120(0+1)$, then $0 in mathbf T$.
STEP $2$. Suppose for some natural number, $n > 0$, that $n-1 in mathbf T$. Then
$displaystyle sum_{i=0}^{n-1} i = dfrac 12(n-1)(n)$. So
begin{align}
sum_{i=0}^{n} i
&= sum_{i=0}^{n-1} i + sum_{i=n}^{n} i \
&= dfrac 12(n-1)(n) + n \
&= dfrac 12(n^2 - n + 2n) \
&= dfrac 12 n(n+1).
end{align}
Hence $n-1 in mathbf T implies n in mathbf T$.
It follows, from POI, that $mathbf T = mathbb N$. Hence equation $(1)$ is proved.
add a comment |
up vote
0
down vote
up vote
0
down vote
What I like about this POI is that it focuses on set membership and not equations. This is what I mean. Consider the equation $$forall n in mathbb N, sum_{i=0}^n i = dfrac 12n(n+1)tag{1}$$ A proof using your version of POI would go as follows.
Let $displaystyle mathbf T = left{n in mathbb N: sum_{i=0}^n i = dfrac 12n(n+1)right}$. (Note $mathbf T subseteq mathbb N.$)
STEP $1$. Since $sum_{i=0}^0 i =0= dfrac 120(0+1)$, then $0 in mathbf T$.
STEP $2$. Suppose for some natural number, $n > 0$, that $n-1 in mathbf T$. Then
$displaystyle sum_{i=0}^{n-1} i = dfrac 12(n-1)(n)$. So
begin{align}
sum_{i=0}^{n} i
&= sum_{i=0}^{n-1} i + sum_{i=n}^{n} i \
&= dfrac 12(n-1)(n) + n \
&= dfrac 12(n^2 - n + 2n) \
&= dfrac 12 n(n+1).
end{align}
Hence $n-1 in mathbf T implies n in mathbf T$.
It follows, from POI, that $mathbf T = mathbb N$. Hence equation $(1)$ is proved.
What I like about this POI is that it focuses on set membership and not equations. This is what I mean. Consider the equation $$forall n in mathbb N, sum_{i=0}^n i = dfrac 12n(n+1)tag{1}$$ A proof using your version of POI would go as follows.
Let $displaystyle mathbf T = left{n in mathbb N: sum_{i=0}^n i = dfrac 12n(n+1)right}$. (Note $mathbf T subseteq mathbb N.$)
STEP $1$. Since $sum_{i=0}^0 i =0= dfrac 120(0+1)$, then $0 in mathbf T$.
STEP $2$. Suppose for some natural number, $n > 0$, that $n-1 in mathbf T$. Then
$displaystyle sum_{i=0}^{n-1} i = dfrac 12(n-1)(n)$. So
begin{align}
sum_{i=0}^{n} i
&= sum_{i=0}^{n-1} i + sum_{i=n}^{n} i \
&= dfrac 12(n-1)(n) + n \
&= dfrac 12(n^2 - n + 2n) \
&= dfrac 12 n(n+1).
end{align}
Hence $n-1 in mathbf T implies n in mathbf T$.
It follows, from POI, that $mathbf T = mathbb N$. Hence equation $(1)$ is proved.
answered Nov 18 at 1:54
steven gregory
17.6k22257
17.6k22257
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3003021%2finduction-definition%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
I think the definition is technically imprecise. The second property is correct, though it's often stated that if $n in T$ then $n + 1 in T$. The first property technically is not correct since we never require a base case of $n = 0$: some statements work only for, say, integers at least $2$. I do think it's useful to think of $T$ as a subset of $mathbb{N}$ to symbolize that we could be talking about all natural numbers (assuming we start with $0$ or $1$, depending on how you define $mathbb{N}$) or all naturals after some point.
– Matt.P
Nov 18 at 0:54
what is what you called 'more common way'?
– Robson
Nov 18 at 1:00
where property 2 is if n is in T then n+1 is in T. This just seems more useful to me, and the one stated above to me seems more unclear
– Carlos Bacca
Nov 18 at 1:02