Jump to content

small indirect proof problem


no genius

Recommended Posts

i have an assignment question where i'm supposed to prove that the square of an odd number is an odd number using both a direct proof and an indirect proof.

 

the direct proof was easy enough, but i'm kinda stuck on the indirect part.

 

so basically i'm supposed to prove that "if n^2 is even then n is even."

 

so i started by stating that .

 

n^2 = 2k

n * n = 2k

n = 2 (k/n) and i'm saying that (k/n) is always an integer

 

but something doesnt seem right about this, especially since i'm not really sure how to justify that (k/n) is an integer.

 

can someone put me on the right path?

 

thank you

Link to comment
Share on other sites

ok, i think i've got it. the original statement, which i've proven directly, was "if n is odd, then n^2 is odd". so basically a statement in the form p -> q. this is logically equivalent to ~p OR q.

 

so i can indirectly prove it by showing that ~p OR q is a tautology.

 

so ~p OR q = "Either n is even or n^2 is odd"

 

n is even OR n^2 is odd <=>

n = 2k OR n^2 = 2j + 1 <=>

n^2 = 2(2k^2) OR n^2 = 2j + 1 <=>

n^2 is even OR n^2 is odd <=> (which has the form "~q OR q")

T

 

 

correct?

Link to comment
Share on other sites

Indirect proofs are proofs by contradiction. So you list out the possibilities, which in this case there are 2: square of an odd number is odd, or it's even.

 

Then, you assume that the square of an odd number is EVEN, bring about a contradiction, which means that this possibility is impossible, then the remaining one possibility, that the square of an odd number is odd, must be true.

 

Judging by your "indirect proof", I'd say your direct proof looked like this probably:

 

Let n=2k+1. Then n^2=4k^2+4k+1=2(2k^2+2k)+1. That's in the form of 2m+1 where m is an integer, which means the expression is odd.

 

Turn it around. Assume that 4k^2+4k+1 is even. Then raise a contradiction.

Link to comment
Share on other sites

i have an assignment question where i'm supposed to prove that the square of an odd number is an odd number using both a direct proof and an indirect proof.

 

the direct proof was easy enough, but i'm kinda stuck on the indirect part.

 

so basically i'm supposed to prove that "if n^2 is even then n is even."

 

so i started by stating that .

 

n^2 = 2k

n * n = 2k

n = 2 (k/n) and i'm saying that (k/n) is always an integer

 

but something doesnt seem right about this, especially since i'm not really sure how to justify that (k/n) is an integer.

 

can someone put me on the right path?

 

thank you

I think you need to use the fundamental theorem of arithmetic. i.e. that there is one and only one way to express an integer greater than 1 as a product of primes. (a difference in the order in which the primes are multiplied does not count as a different way). Thus 30 = 2*3*5 = 3*2*5= 5*2*3 etc. There is one 2, one 3, and one 5 in each expression of 30 as a product of primes so that counts as only one way. What does this say about n*n?

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.