Mathematical Induction and "the product of odd numbers is odd"

Question

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.

Answer 1

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.

Answer 2

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!

Answer 3

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) $$