- #1
Korisnik
- 62
- 1
I'm not sure if I'm posting in the right subforum because there is one about proofs, but it requires the question not to be homework-like, but I also need an explanation...
Prove by mathematical induction:
Let [itex]m[/itex] be the smallest element of [itex]A\subseteq\mathbb{N}[/itex]. If [itex]A[/itex] contains [itex]k+1[/itex] whenever it contains a natural number [itex]k[/itex], then [itex]A=\left\{n\in\mathbb{N}:n\geq m\right\}[/itex].
Now, what I don't understand here is how is this related to mathematical induction. I get some parts and my friend "slipped" me a clue so I'm afraid I couldn't understand it on my own... So if someone also knows where I could find more examples of mathematical induction of this kind, I'd be very grateful.
Axiom of mathematical induction (which allows us to conclude, from some properties of subset [itex]M\subseteq\mathbb{N}[/itex], that [itex]M=\mathbb{N}[/itex]):
Let [itex]M[/itex] be a subset of a set of natural numbers [itex]\mathbb{N}[/itex].
Let's assume that [itex]M[/itex] has these properties:
1) [itex]1\in M[/itex],
2) if [itex]n\in M[/itex] then so is [itex]n+1\in M[/itex].
Conclusion: [itex]M=\mathbb{N}[/itex].
Now 10 questions before this one were just some [itex]1+2+\dots+n=\frac{n}{2}(1+n)[/itex] easy problems which I solved using the method: 1) check the base of the induction (first element in the sequence, in this case n=1), then (2) understand that [itex](1+2+\dots+n)+(n+1)=\left[\frac{n}{2}(1+n)\right]+(n+1)[/itex], and last - check if the result is the same for [itex]n+1[/itex], so:[itex]\left[\frac{n}{2}(1+n)\right]+(n+1)=\frac{n+1}{2}(1+(n+1))[/itex]. (I know that the second step is just replacing the variable's name, but I skip that since this is a faster way.)
In the original problem, however, I cannot identify the pattern. My best *guess* is that the first step would be 1) [itex]k=m[/itex], because that's the first element of set [itex]A[/itex]. So it's trivially true that [itex]k\in A[/itex] since it's its first element. The second step would be 2) [itex]k\geq m[/itex], because if it's true for [itex]n[/itex], then it's true for [itex]k[/itex]: [itex]A=\left\{k\in\mathbb{N}:k\geq m\right\}[/itex]. Since it's true for any [itex]k[/itex], by the definition "it's true for [itex]k+1[/itex] whenever it's true for [itex]k[/itex]", it's true for [itex]k+1[/itex]: [itex]A=\left\{k+1\in\mathbb{N}:k+1\geq m\right\}[/itex].
So can someone explain what exactly is mathematical induction in this problem, and how to solve the original problem.
(I think mathematical induction is (by axiom) finding the conditions to support that *whatever* is true for [itex]\mathbb{N}[/itex], except if defined otherwise (for example, prove for [itex]n\geq4[/itex]).)
Homework Statement
Prove by mathematical induction:
Let [itex]m[/itex] be the smallest element of [itex]A\subseteq\mathbb{N}[/itex]. If [itex]A[/itex] contains [itex]k+1[/itex] whenever it contains a natural number [itex]k[/itex], then [itex]A=\left\{n\in\mathbb{N}:n\geq m\right\}[/itex].
Now, what I don't understand here is how is this related to mathematical induction. I get some parts and my friend "slipped" me a clue so I'm afraid I couldn't understand it on my own... So if someone also knows where I could find more examples of mathematical induction of this kind, I'd be very grateful.
Homework Equations
Axiom of mathematical induction (which allows us to conclude, from some properties of subset [itex]M\subseteq\mathbb{N}[/itex], that [itex]M=\mathbb{N}[/itex]):
Let [itex]M[/itex] be a subset of a set of natural numbers [itex]\mathbb{N}[/itex].
Let's assume that [itex]M[/itex] has these properties:
1) [itex]1\in M[/itex],
2) if [itex]n\in M[/itex] then so is [itex]n+1\in M[/itex].
Conclusion: [itex]M=\mathbb{N}[/itex].
The Attempt at a Solution
Now 10 questions before this one were just some [itex]1+2+\dots+n=\frac{n}{2}(1+n)[/itex] easy problems which I solved using the method: 1) check the base of the induction (first element in the sequence, in this case n=1), then (2) understand that [itex](1+2+\dots+n)+(n+1)=\left[\frac{n}{2}(1+n)\right]+(n+1)[/itex], and last - check if the result is the same for [itex]n+1[/itex], so:[itex]\left[\frac{n}{2}(1+n)\right]+(n+1)=\frac{n+1}{2}(1+(n+1))[/itex]. (I know that the second step is just replacing the variable's name, but I skip that since this is a faster way.)
In the original problem, however, I cannot identify the pattern. My best *guess* is that the first step would be 1) [itex]k=m[/itex], because that's the first element of set [itex]A[/itex]. So it's trivially true that [itex]k\in A[/itex] since it's its first element. The second step would be 2) [itex]k\geq m[/itex], because if it's true for [itex]n[/itex], then it's true for [itex]k[/itex]: [itex]A=\left\{k\in\mathbb{N}:k\geq m\right\}[/itex]. Since it's true for any [itex]k[/itex], by the definition "it's true for [itex]k+1[/itex] whenever it's true for [itex]k[/itex]", it's true for [itex]k+1[/itex]: [itex]A=\left\{k+1\in\mathbb{N}:k+1\geq m\right\}[/itex].
So can someone explain what exactly is mathematical induction in this problem, and how to solve the original problem.
(I think mathematical induction is (by axiom) finding the conditions to support that *whatever* is true for [itex]\mathbb{N}[/itex], except if defined otherwise (for example, prove for [itex]n\geq4[/itex]).)