# Proof by induction

• Jun 29th 2010, 01:28 PM
minicooper58
Proof by induction
hi the link to this question is here http://i223.photobucket.com/albums/d...f/HPIM0535.jpg
Question 8. I think I was OK in the first part with proving 2n(2n+1) is always odd.
However I am lost with part b p^n. I'm not sure if the answer written on the scan is correct.
Thanks
• Jun 29th 2010, 01:47 PM
MattMan
Let p be an odd integer.
for n=1 $\displaystyle p^1=p$ which is odd.
Suppose $\displaystyle p^k$ is odd.
Now $\displaystyle p^{k+1}=(p^k)p$ which by part a is odd.

So the answer on the sheet was a little off.
• Jun 29th 2010, 05:09 PM
HallsofIvy
Quote:

Originally Posted by minicooper58
hi the link to this question is here http://i223.photobucket.com/albums/d...f/HPIM0535.jpg
Question 8. I think I was OK in the first part with proving 2n(2n+1) is always odd.
However I am lost with part b p^n. I'm not sure if the answer written on the scan is correct.
Thanks

Am I missing something? 2n(2n+1) is always even, not odd. n(2n+1) is an integer so 2n(2n+1) is 2 times an integer- an even number.
• Jun 29th 2010, 06:41 PM
MattMan
The PDF said proving that the product of two odd integers is odd. I'm assuming he meant (2m+1)(2n+1). Though, what he wrote in the thread is also written on the side of the PDF... interesting.
• Jun 30th 2010, 09:11 AM
MoeBlee
The exercise in the photocopied page says to show that the product of two odd numbers is odd.

That is expressed:

Show (2n+1)(2k+1) is odd.

And it's trivial and no induction needed:

(2n+1)(2k+1) = 2n2k + 2n + 2k +1 = 2(2nk + n + k) + 1 is odd
• Jul 1st 2010, 03:13 PM
minicooper58
Part b proof by induction
hi I apologise for confusing the written answer on the PDF. Is two odd numbers written as (2n-1)(2n+1) acceptable as an answer for part a)
For part b) How can I use this answer for the induction proof of p^n.
Thanks
• Jul 1st 2010, 03:26 PM
MoeBlee
Quote:

Originally Posted by minicooper58
Is two odd numbers written as (2n-1)(2n+1) acceptable as an answer for part a)

No, it's not. You're not being asked to prove something about the special case of two consecutive odd numbers, but rather about ANY pair of odd numbers. And I gave the answer just above.

Quote:

Originally Posted by minicooper58
For part b) How can I use this answer for the induction proof of p^n.

Suppose p is odd. Show p^n is odd. Induction on n:

n=1. Then p^n = p is odd.

Suppose p^n is odd. Show p^(n+1) is odd.
p^(n+1) = (p^n)*p. But we have p^n is odd, and p is odd, and the product of two odd numbers is odd, so p^(n+1) is odd.
• Jul 2nd 2010, 03:49 AM
Quote:

Originally Posted by minicooper58
hi the link to this question is here http://i223.photobucket.com/albums/d...f/HPIM0535.jpg
Question 8. I think I was OK in the first part with proving 2n(2n+1) is always odd.

This is not the product of 2 odd numbers as 2n is even.

Let $\displaystyle n$ be odd.

Then $\displaystyle n\pm2k$ is also odd.

P(k)

$\displaystyle n\left(n\pm2k\right)=odd$

P(k+1)

$\displaystyle n\left(n\pm2(k+1)\right)=odd$

Show that P(k) being true will cause P(k+1) to be true

Proof

$\displaystyle n\left(n\pm2k\right)=n^2\pm2kn=odd$ ?

$\displaystyle n\left(n\pm2(k+1)\right)=n^2\pm2kn\pm2n$

If P(k) is true, then $\displaystyle n^2\pm2kn$ is odd,

therefore since 2n is even and odd+even=odd, so P(k+1) is true if P(k) is.

Then test for an initial value, such as n=1.

There's no need to use induction for part (a) but it can be used nevertheless.

Part (b)

p=odd

P(k)

$\displaystyle p^k=odd$

P(k+1)

$\displaystyle p^{k+1}=odd$

Try to show that P(k) being true causes P(k+1) to be true

Proof

$\displaystyle p^{k+1}=(p)\left(p^k\right)=(odd)(odd)$ if P(k) is true

Test for an initial value