Thread: 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.

Do you really need to use induction? Write two odd integers as and , where m and n are both integers. Then



which is also an odd integer...

The question itself specifically says to use STRONG mathematical induction. Also, the proof is mostly proving more than 2 integers. Thanks though.

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...

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 {a₁,...,a_n}. without loss of generality, assume the last number is a_n = 2t + 1, for some natural number t.

since a₁a₂...a_n-1 is a (n-1)-fold product of odd numbers, and n-1 < n,

by our inductive hypothesis, this number is odd, so a₁a₂...a_n-1 = 2u + 1, for some natural number u.

therefore a₁a₂....a_n = (a₁a₂...a_n-1)(a_n) = (2u + 1)(2t + 1),

which is odd by our base case. bam!

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 {a₁,...,a_n}. without loss of generality, assume the last number is a_n = 2t + 1, for some natural number t.

since a₁a₂...a_n-1 is a (n-1)-fold product of odd numbers, and n-1 < n,

by our inductive hypothesis, this number is odd, so a₁a₂...a_n-1 = 2u + 1, for some natural number u.

therefore a₁a₂....a_n = (a₁a₂...a_n-1)(a_n) = (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 (a₁...a_i)(a_i+1...a_n) 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.

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 (a₁...a_i)(a_i+1...a_n) 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.