This thread might help.
Hey everyone.
I'm having a little trouble understanding why it is that proof by induction constitutes as proof. If anyone could spare a little of their time and discuss this with me, I'd be much obliged.
Here's my understanding...
I was given this Theorem from my abstract algebra text (I know, i'm studying abstract and I can't even prove using induction...I'm screwed). The concepts of the algebra are easy to master, but I'm american, so I've never been instruced in the art of proof.
Theorem:
Let be a set of positive integers with the properties
a)
b) whenever the integer , then must also be in .
Then is the set of all positive integers.
O.K. So, the book goes on to prove this theorem by employing the Well-Ordering Principle. I understand the proof, but I'm a little fuzzy on why this theorem allowa us to verify that certain relations are true for all .
Let's talk guys.
I am not sure I understand your problem...
Because induction is a theorem. In fact, you provided its statement in your post. This theorem has a proof; again, you said you understand it. Invoking proved theorems in other proofs is legitimate.I'm having a little trouble understanding why it is that proof by induction constitutes as proof.
First, you probably mean, "to verify that certain relations are true for all positive integers". The induction theorem has the form, "For all S, if ..., then S is the set of positive integers". So unless one defines his/her own set S in order to apply the induction theorem to it, there is no S; certainly there is no S that is universally accepted.I'm a little fuzzy on why this theorem allowa us to verify that certain relations are true for all .
Here is how induction theorem is applied. Suppose . Obviously, . We would like to show that . One way to approach this is to fix some and to try to show
(*)
directly. On the other hand, one can apply the induction theorem. This reduces the task to proving two facts: and .
What have we gained in the second approach? Here we also have to prove for an arbitrary k, i.e.,
(**)
However, compared to (*), we have a powerful induction hypothesis at our disposal:
This makes proving (**) much easier than proving (*).
ok. So, let me try and tell me if there are any flaws in my thinking.
We would like to show by induction that .
So, let be the be a subset of the natural numbers such that is a true statement.
Or,
So, by inspection we see that .
Now we nee to show that if , then .
Now assume that . Then we have
.
If we add to both sides we get
. But, The right hand side is equivalent to
which is exactly what we would expect for the sum of the first elements.
Therefore,