# Help with Proof by Strong Mathematical Induction

• November 6th 2012, 05:21 PM
Walshy
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.
• November 6th 2012, 06:01 PM
Prove It
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...
• November 6th 2012, 06:10 PM
Walshy
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.
• November 6th 2012, 06:50 PM
Prove It
Re: Help with Proof by Strong Mathematical Induction
Quote:

Originally Posted by Walshy
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...
• November 6th 2012, 10:18 PM
Deveno
Re: Help with Proof by Strong Mathematical Induction
Quote:

Originally Posted by Prove It
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!
• November 7th 2012, 03:25 AM
emakarov
Re: Help with Proof by Strong Mathematical Induction
Quote:

Originally Posted by Deveno
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.
• November 7th 2012, 06:52 AM
Deveno
Re: Help with Proof by Strong Mathematical Induction
Quote:

Originally Posted by emakarov
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.