Results 1 to 2 of 2

Math Help - Strong induction proofs

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    USA
    Posts
    1

    Strong induction proofs

    i'm having trouble understanding strong induction proofs
    i understand how to do ordinary induction proofs and i understand that strong induction proofs are the same as ordinary with the exception that you have to assume that the theorem holds for all numbers up to and including some n (starting at the base case) then we try and show: theorem holds for n+1
    but how do you show this exactly.
    here is a proof by induction:

    Thm: n≥1, 1+6+11+16+...+(5n-4) = [n(5n-3)]/2 Proof (by induction)
    Basis step: for n=1: 5-4=(5-3)/2 ---> 1=1 the basis step holds
    Induction Step: Suppose that for some integer k≥1 1+6+11+16+...+(5k-4) = [k(5k-3)]/2 (inductive hypothesis)
    Want to Show: 1+6+11+16+...+(5k-4)+(5{k+1}-4) = [{k+1}(5{k+1}-3)]/2
    [k(5k-3)]/2 + (5{k+1}-4) = [{k+1}(5{k+1}-3)]/2

    then you just show that they are equal
    so how can i do the same proof using strong induction? what are the things i need to add/change in order for this proof to be a strong induction proof?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Strong induction proofs

    Technically, every proof by regular induction is also a proof by strong induction because in strong induction, you are allowed to use the hypotheses for all numbers up to n; you are not required to use any of them. Of course, for clarity we usually describe only the necessary tools used in a particular proof, so a proof that uses only the induction hypothesis for n is properly described as using regular induction.

    Usually either regular or strong induction is more convenient. Proving the formula for the sum of an arithmetic progression is more convenient using regular induction, and proving that every natural number > 1 can be factorized into primes is more convenient using strong induction. Sometimes it is possible to give both proofs. For example, suppose we want to prove 1 + ... + (5n - 4) = n(5n - 3) / 2 from the hypotheses for all k < n. If n = 2k, then k < n since n ≥ 1. The left-hand side equals

    1 + ... + (5k - 4) + (5k + 1) + ... + (5(2k) - 4) =
    1 + ... + (5k - 4) + 5kČ + 1 + ... + (5k - 4) =
    k(5k - 3) / 2 + 5kČ + k(5k - 3) / 2 =
    10kČ - 3k

    and the right-hand side also equals (2k)(5(2k) - 3) / 2 = 10kČ - 3k. The case when n = 2k + 1 should be considered similarly. However, this proof seems more complicated.

    For another example where both regular and strong inductions are appropriate see this thread.
    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. Strong induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 26th 2010, 01:10 PM
  3. STRONG induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 6th 2009, 08:23 PM
  4. Strong induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 22nd 2008, 01:00 PM
  5. Strong Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 5th 2008, 08:50 AM

Search Tags


/mathhelpforum @mathhelpforum