Results 1 to 4 of 4

Math Help - Induction

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    Induction

    The principle of mathematical induction can be extended as follows. A list P_m, P_{m+1}, \cdot \cdot \cdot of propositions is true provided (i) P_m is ture, (ii) P_{n+1} is true whenever P_n is true and n\geq m.

    Question: Is the above what we called the Strong Induction?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by novice View Post
    The principle of mathematical induction can be extended as follows. A list P_m, P_{m+1}, \cdot \cdot \cdot of propositions is true provided (i) P_m is ture, (ii) P_{n+1} is true whenever P_n is true and n\geq m.

    Question: Is the above what we called the Strong Induction?
    It looks like it, but I must say the formulation seems a bit lacking in precision.
    The principle of mathematical induction could be stated, I guess from your question, like this:
    If (i) P_m is true and (ii) for all n\geq m: P_{n+1} is true, provided P_n is true
    then P_n is true for all n\geq m
    Now a somewhat unhappy formulation of the principle of strong induction would be
    If (i) P_m is true and (ii) for all n\geq m: P_{n+1} is true provided P_k is true for all k with m\leq k \leq n
    then P_n is true for all n\geq m
    I wrote "unhappy formulation" because the principle of strong induction should, in my opinion, really be formulated like this:
    If for all n\geq m: P_n is true provided that P_k is true for all k with m\leq k<n
    then P_n is true for all n\geq m
    Note that in this formulation we do not need a separate clause to require that P_m holds, because if you set n := m in the above you can see, that this requires you to be able to prove P_m without presupposing the truth of any other P_k, with k\geq m, since for this choice of n there is no k that satisfies m\leq k<n.

    This would become much clearer if we were allowed to write the above with connectives of implication, conjunction, and quantification from first-order logic, I think.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,792
    Thanks
    1532
    The "strong" principle of induction usually is stated as

    If (1) P(1) is true and (2) if P(k) is true for all [tex]k\le i[/itex] then P(i+ 1) is true
    then P(n) is true for all positive integers n.

    Changing "P(1)" to "P(m)" and asserting that "then P(n) is true for all n\ge m is not precisely the "strong" principle but follows easily from it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by HallsofIvy View Post
    The "strong" principle of induction usually is stated as

    If (1) P(1) is true and (2) if P(k) is true for all [tex]k\le i[/itex] then P(i+ 1) is true
    then P(n) is true for all positive integers n.

    Changing "P(1)" to "P(m)" and asserting that "then P(n) is true for all n\ge m is not precisely the "strong" principle but follows easily from it.
    Is there a name for it?
    You mean using m as basis and prove p(n), n\geq m?
    If P(m) is true, when m\leq n, won't P(n) automatically become true?
    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