Results 1 to 5 of 5

Math Help - Induction.

  1. #1
    No one in Particular VonNemo19's Avatar
    Joined
    Apr 2009
    From
    Detroit, MI
    Posts
    1,823

    Induction.

    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 S be a set of positive integers with the properties

    a) 1\in{S}
    b) whenever the integer k\in{S}, then k+1\in{S} must also be in S.

    Then S 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 n\in{S}.

    Let's talk guys.
    Last edited by mr fantastic; December 6th 2010 at 03:54 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2010
    Posts
    715
    Thanks
    2
    This thread might help.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    I am not sure I understand your problem...

    I'm having a little trouble understanding why it is that proof by induction constitutes as proof.
    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 a little fuzzy on why this theorem allowa us to verify that certain relations are true for all n\in{S}.
    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.

    Here is how induction theorem is applied. Suppose S = \{n\in\mathbb{Z}^+ \mid 1 + \dots + n = n (n + 1) / 2\}. Obviously, S\subseteq\mathbb{Z}^+. We would like to show that \mathbb{Z}^+\subseteq S. One way to approach this is to fix some n\in\mathbb{Z}^+ and to try to show

    1 + \dots + n = n (n + 1) / 2 (*)

    directly. On the other hand, one can apply the induction theorem. This reduces the task to proving two facts: 1\in S and \forall k\in\mathbb{Z}^+, k\in S\to k+1\in S.

    What have we gained in the second approach? Here we also have to prove k+1\in S for an arbitrary k, i.e.,

    1 + \dots + k + 1 = (k+1)(k + 2) / 2 (**)

    However, compared to (*), we have a powerful induction hypothesis at our disposal:

    1 + \dots + k = k (k + 1) / 2

    This makes proving (**) much easier than proving (*).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    No one in Particular VonNemo19's Avatar
    Joined
    Apr 2009
    From
    Detroit, MI
    Posts
    1,823
    ok. So, let me try and tell me if there are any flaws in my thinking.

    We would like to show by induction that 1+2+...+(n-1)+n=\frac{n(n+1)}{2}.

    So, let S be the be a subset of the natural numbers such that 1+2+...+(n-1)+n=\frac{n(n+1)}{2} is a true statement.

    Or, S=\{n\in\mathbb{Z_+}|1+2+...+(n-1)+n=\frac{n(n+1)}{2}\}

    So, by inspection we see that 1\in{S}.

    Now we nee to show that if k\in{S}, then k+1\in{S}.

    Now assume that k\in{S}. Then we have

    1+2+...+(k-1)+k=\frac{k(k+1)}{2}.

    If we add k+1 to both sides we get

    1+2+...+(k-1)+k+(k+1)=\frac{k(k+1)}{2}+(k+1). But, The right hand side is equivalent to

    \frac{(k+1)[(k+1)+1]}{2} which is exactly what we would expect for the sum of the first k+1 elements.

    Therefore, S=\mathbb{Z_+}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Touché.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2010, 02:08 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 19th 2008, 05:12 PM

Search Tags


/mathhelpforum @mathhelpforum