small indirect proof problem

[no genius]

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

[psynapse]

Justify by plugging in numbers? say n=2?

[no genius]

no no no. you cant prove something by listing a finite number of numerical examples. i'm no genius, but i know that much

[no genius]

anyone?

[timo]

What was your direct proof ?

[no genius]

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?

[The Thing]

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.

[no genius]

my prof and my textbook (Discrete Mathematics and Its Applications, Rosen), make a distinction between "indirect proof" and "proof by contradiction". the proof by contradiction of this was part c) of the problem.

[Ramsey2879]

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?