Results 1 to 5 of 5

Math Help - induction

  1. #1
    Newbie
    Joined
    Aug 2007
    Posts
    7

    induction

    Hi,
    can any one give me proof for mathematical induction?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,111
    Thanks
    2
    Hmmm...That's a tough one. What do you mean? Can it be proven that Mathematical Induction works or is valid? The fundamentals lie in the logic. Do you mean just any old proof using Mathematical Induction? It may help if you would provide the actual wording of an actual problem statement. If this is a personal exploration, you're going to have to get substantially more clear.
    Last edited by TKHunny; August 28th 2007 at 08:54 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member kezman's Avatar
    Joined
    Jul 2006
    Posts
    93
    Thanks
    2
    The principle of mathematical induction is usually stated as an axiom of the natural numbers. However, it can be proved in some logical systems. For instance, it can be proved if one assumes:

    The set of natural numbers is well-ordered.
    Every natural number is either zero, or n+1 for some natural number n.
    For any natural number n, n+1 is greater than n.
    To derive simple induction from these axioms, we must show that if P(n) is some proposition predicated of n, and if:

    P(0) holds and
    whenever P(k) is true then P(k+1) is also true
    then P(n) holds for all n.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2007
    Posts
    7

    induction

    I mean how can you say the method of mathematical induction is true.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by ksssudhanva View Post
    I mean how can you say the method of mathematical induction is true.
    Well-Ordering Principle: Let S be a non-empty set of natural numbers. Then S has a smallest element!

    Induction: Let S be a set. Given  0 \in S and that if n\in S\implies n+1\in S. Then S=\mathbb{N}.

    Proof: Let T = \{ x\in \mathbb{N} | x\not \in S \}. Our goal is to show that T is an empty set. Now assume that T is non-empty. By the Well-Ordering Principle there exists a minimial element a\in T. Now a\not = 0 since 0\in S. So a\geq 1. That means it has a predecessor a-1. Since a-1<a it must and a is minimal it means (a-1)\in S. But then (a-1)+1 = a\in S. A contradiction! Thus, T must be empty. Q.E.D.
    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, 01:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 06:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 05:10 PM

Search Tags


/mathhelpforum @mathhelpforum