# Mathematical Induction and “the product of odd numbers is odd”

I am extremely poor at proofs and logical manipulation so I am stuck on a lot of these questions especially induction.

The question below I have been stuck at for a little over 1 hour and I can't get it, I have tried various substitutions and forms but I am stuck..

Using mathematical induction: An integer is odd if it can be written as $n=2k+1$. Use induction to prove that the product of $m$ many odd integers is odd for every $m \geq 2$.

I have tried doing $(2k+1)(2(k+1)+1)$ and substituting $k=1$ for my basis step after that I am lost.

-
Try doing the induction on $m$, not on $k$. – Gerry Myerson Jan 16 '12 at 6:04
@Raynos People have provided answers to your problem so here is a little joke that may cheer you up. Three people (mathematician, physicist, engineer) have been asked to prove that the product of $m$ odd integers for $m\geq 2$ is odd. Physicist: Within experimental error, the product is always odd. Mathematician: By mathematical induction, the product is always odd. Engineer (Most direct proof): An odd number times an odd number is odd, so this odd number times another odd number is odd, etc... – user38268 Jan 16 '12 at 8:01

For the base case, we consider when $m=2$. For $a,b \in \mathbb{Z}$, that is, $(2a +1)(2b +1) = 4ab +2a+2b +1 = 2(2ab + a + b) +1$, where $2ab + a + b \in \mathbb{Z}$, so it is true for $m=2$.

By induction, we assume for arbitrary $k \in \mathbb{Z}$ that, $$\prod_{i=1}^{k}(2a_{i} +1)=2l+1$$ where $l \in \mathbb{Z}$. Since by our basis step we have that two odd numbers multiplied together gives two odd numbers, then for the $k+1^{th}$ odd integer $c$, we have that $$(2l+1)(2c+1)=2(2lc + l + c) +1$$ So, since $2lc + l + c \in \mathbb{Z}$, we have that $$\prod_{i=1}^{k+1}(2a_{i}+1)=2j+1$$ where $j \in \mathbb{Z}$. Therefore, by the Principle of Mathematical Induction, the product of $m$ odd integers is again odd.

-
I'm clearly too tired for this, editing now... – Samuel Reid Jan 16 '12 at 6:30
@Srivatsan: How is the notation now? – Samuel Reid Jan 16 '12 at 6:34
Looks good now. :) – Srivatsan Jan 16 '12 at 6:35
Thank you guys for helping me out! I am understanding this a little more now. – Raynos Jan 16 '12 at 12:36

The way induction works is you show that some property, $P(n)$ holds for $n=1$, and you also show that if $P(n)$ holds for some $n$, then it also holds for $P(n+1)$. In this way you've shown that $P(1)$ holds, by the second condition $P(1+1)=P(2)$ holds, etc. This proves that the property $P(n)$ holds for all $n \in \mathbb{N}$.

The first thing that you want to show is the base case, which corresponds to m=2. To show this you just need to prove that the product of two integers is odd. We may write the product of two odd integers as

$$(2k_{1}+1)(2k_{2}+1)=4k_{1}k_{2}+2k_{1}+2k_{2}+1=2(2k_{1}k_{2}+k_{1}+k_{2})+1$$

Since $2k_{1}k_{2}+k_{1}+k_{2} \in \mathbb{Z}$, this finishes the base case.

Next we need to prove that if the product of $m$ integers is odd, then the product of $m+1$ integers is also odd. Informally, this is true because if there are no factors of two in the first $m$ integers, and there isn't a factor of two in the next integer, there won't be a factor of two anywhere in the product, and the product of $m+1$ integers will be odd.

Rigorously, we need to first assume that the product of $m$ odd integers is odd. Then we note that the product of $m+1$ odd integers looks like this: $\displaystyle \prod_{i=1}^{m+1} a_{i}=a_{m+1}\prod_{i=1}^{m} a_{i}$, $a_{i}$ odd for $1 \le i \le m+1$. Since we are assuming the product of $m$ integers is odd, we can write the product $\displaystyle \prod_{i=1}^{m} a_{i}=2\alpha+1$, $\alpha \in \mathbb{Z}$. Since $a_{m+1}$ is odd, we may write $a_{m+1}=2\beta+1$, $\beta \in \mathbb{Z}$. Thus, $\displaystyle \prod_{i=1}^{m+1} a_{i}=(2\beta+1)(2\alpha+1)=4\alpha\beta+2\alpha+2\beta+1=2(2\alpha\beta+\alpha+\beta)+1$, which is odd. This completes the proof.

HTH!

-
I think you did more than you needed to at the end. Once you reduce the product of m+1 odd integers to the product of 2 odd integers, you've already proven for the base case that the product of 2 odd integers is odd. – Mike Jan 16 '12 at 8:16
Yea, I left that part out at first since they are essentially the same proof, but when I think when you're answer questions you need to appeal to the OP. I don't think the added thoroughness is a bad thing for someone taking their first proof's course. – Jackson Jan 16 '12 at 10:24

HINT $\rm\ mod\ 2\$ it is simply $\rm\ 1^n\equiv 1\$ with base $1\equiv 1$ and induction $\rm 1^n\equiv 1\ \Rightarrow\ 1^{n+1}\equiv 1\cdot 1\equiv 1\:.$

Without mod arithmetic it's still simple, the inductive step $\ 1\cdot 1\equiv 1\$ is odd $\cdot$ odd = odd, since

$$\rm\ (1 + 2\ j)\ (1 + 2\ k)\ =\ 1 + 2\ (j + k + 2\ j\ k)$$

-