# Proof by induction

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

minicooper58

#### HallsofIvy

MHF Helper
hi the link to this question is here http://i223.photobucket.com/albums/dd217/arfanrauf/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.

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

Last edited:

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

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

#### MoeBlee

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.

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.

minicooper58

hi the link to this question is here http://i223.photobucket.com/albums/dd217/arfanrauf/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

Last edited:
minicooper58