Results 1 to 7 of 7

Math Help - Help with Proof by Strong Mathematical Induction

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    Ohio
    Posts
    14

    Help with Proof by Strong Mathematical Induction

    Prove by strong mathematical induction:
    The product of two or more odd integers is odd.

    This is what I have:
    Let n>=2 be any integer. Basis Step - The product of 2 odd integers is odd. Inductive Step - Let k>= 2 be any integer and suppose for each integer that 2<= i < k .

    I have no clue where to go from here. Thanks for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,409
    Thanks
    1294

    Re: Help with Proof by Strong Mathematical Induction

    Do you really need to use induction? Write two odd integers as \displaystyle \begin{align*} 2m + 1 \end{align*} and \displaystyle \begin{align*} 2n + 1 \end{align*}, where m and n are both integers. Then

    \displaystyle \begin{align*} (2m + 1)(2n + 1) &= 4mn + 2m + 2n + 1 \\ &= 2\left( 2mn + m + n \right) + 1 \end{align*}

    which is also an odd integer...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2012
    From
    Ohio
    Posts
    14

    Re: Help with Proof by Strong Mathematical Induction

    The question itself specifically says to use STRONG mathematical induction. Also, the proof is mostly proving more than 2 integers. Thanks though.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,409
    Thanks
    1294

    Re: Help with Proof by Strong Mathematical Induction

    Quote Originally Posted by Walshy View Post
    The question itself specifically says to use STRONG mathematical induction. Also, the proof is mostly proving more than 2 integers. Thanks though.
    Showing the product of two odd integers is odd surely implies that multiplying by any further odd numbers will only ever get you something odd...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,325
    Thanks
    699

    Re: Help with Proof by Strong Mathematical Induction

    Quote Originally Posted by Prove It View Post
    Showing the product of two odd integers is odd surely implies that multiplying by any further odd numbers will only ever get you something odd...
    that implication is basically what we're trying to PROVE.

    basically a strong inductive proof will run as follows:

    base case: handled by ProveIt in post #2.

    assume that for 1 < k < n odd numbers, their product is odd.

    suppose we have n odd numbers {a1,...,an}. without loss of generality, assume the last number is an = 2t + 1, for some natural number t.

    since a1a2...an-1 is a (n-1)-fold product of odd numbers, and n-1 < n,

    by our inductive hypothesis, this number is odd, so a1a2...an-1 = 2u + 1, for some natural number u.

    therefore a1a2....an = (a1a2...an-1)(an) = (2u + 1)(2t + 1),

    which is odd by our base case. bam!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Help with Proof by Strong Mathematical Induction

    Quote Originally Posted by Deveno View Post
    basically a strong inductive proof will run as follows:

    base case: handled by ProveIt in post #2.

    assume that for 1 < k < n odd numbers, their product is odd.

    suppose we have n odd numbers {a1,...,an}. without loss of generality, assume the last number is an = 2t + 1, for some natural number t.

    since a1a2...an-1 is a (n-1)-fold product of odd numbers, and n-1 < n,

    by our inductive hypothesis, this number is odd, so a1a2...an-1 = 2u + 1, for some natural number u.

    therefore a1a2....an = (a1a2...an-1)(an) = (2u + 1)(2t + 1),

    which is odd by our base case.
    This proof only uses the induction hypothesis for n - 1, so it can be done with regular induction. I think that the intention of the problem author was not to take associativity of multiplication for granted. Then the product of n numbers has the form (a1...ai)(ai+1...an) for some 1 <= i < n; then n - i < n. The two factors have i and n - i numbers, respectively, so the induction hypothesis is applicable to them. This is where strong induction comes into play.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,325
    Thanks
    699

    Re: Help with Proof by Strong Mathematical Induction

    Quote Originally Posted by emakarov View Post
    This proof only uses the induction hypothesis for n - 1, so it can be done with regular induction. I think that the intention of the problem author was not to take associativity of multiplication for granted. Then the product of n numbers has the form (a1...ai)(ai+1...an) for some 1 <= i < n; then n - i < n. The two factors have i and n - i numbers, respectively, so the induction hypothesis is applicable to them. This is where strong induction comes into play.
    this could very well be true. it's a reasonable guess.

    but if one doesn't take associativity for granted, then the statement:

    "Then the product of n numbers has the form...."

    itself requires an inductive proof (which is surprisingly difficult, not because it's conceptually hard, but because there are a LOT of ways we might form an n-fold product, and the bookkeeping is tedious).

    in fact, ANY strong inductive proof CAN be done with "regular" induction, although it may be "tricky" to put it in the right form (strong induction isn't actually "stronger").

    but, you are probably right, it seems likely that is what the author had in mind.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof using Strong Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 12th 2010, 10:36 PM
  2. Strong Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: August 22nd 2010, 12:40 AM
  3. Proof Using Strong Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 27th 2009, 06:30 AM
  4. Proof Using Strong Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 23rd 2009, 10:26 AM
  5. Strong induction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 7th 2008, 09:48 PM

Search Tags


/mathhelpforum @mathhelpforum