Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
5  
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

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
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
2  
Looks good now. :) –  Srivatsan Jan 16 '12 at 6:35
1  
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!

share|improve this answer
    
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 Walters 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) $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.