# small indirect proof problem

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

##### Share on other sites

Justify by plugging in numbers? say n=2?

##### Share on other sites

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

anyone?

##### Share on other sites

What was your direct proof ?

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

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

##### Share on other sites

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.

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

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