Thread: Help with Proof by Strong Mathematical Induction

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

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

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

4. Re: Help with Proof by Strong Mathematical Induction

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

5. Re: Help with Proof by Strong Mathematical Induction

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!

6. Re: Help with Proof by Strong Mathematical Induction

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.

7. Re: Help with Proof by Strong Mathematical Induction

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.