Thread: 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

Let p be an odd integer.
for n=1 which is odd.
Suppose is odd.
Now which by part a is odd.

So the answer on the sheet was a little off.

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.

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.

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

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

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.

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.

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 be odd.

Then is also odd.

P(k)



P(k+1)



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

Proof

?



If P(k) is true, then 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)



P(k+1)



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

Proof

if P(k) is true

Test for an initial value