Proof by induction

May 2010
48
20
Texas
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.
 
  • Like
Reactions: minicooper58

HallsofIvy

MHF Helper
Apr 2005
20,249
7,909
May 2010
48
20
Texas
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:
Feb 2010
470
154
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
 
Jun 2010
36
0
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
 
Feb 2010
470
154
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.
 
  • Like
Reactions: minicooper58
Dec 2009
3,120
1,342
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:
  • Like
Reactions: minicooper58