no genius Posted February 13, 2007 Share Posted February 13, 2007 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 More sharing options...

psynapse Posted February 13, 2007 Share Posted February 13, 2007 Justify by plugging in numbers? say n=2? Link to comment Share on other sites More sharing options...

no genius Posted February 13, 2007 Author Share Posted February 13, 2007 no no no. you cant prove something by listing a finite number of numerical examples. i'm no genius, but i know that much Link to comment Share on other sites More sharing options...

no genius Posted February 15, 2007 Author Share Posted February 15, 2007 anyone? Link to comment Share on other sites More sharing options...

timo Posted February 15, 2007 Share Posted February 15, 2007 What was your direct proof ? Link to comment Share on other sites More sharing options...

no genius Posted February 15, 2007 Author Share Posted February 15, 2007 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 More sharing options...

The Thing Posted February 21, 2007 Share Posted February 21, 2007 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 More sharing options...

no genius Posted February 21, 2007 Author Share Posted February 21, 2007 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. Link to comment Share on other sites More sharing options...

Ramsey2879 Posted February 22, 2007 Share Posted February 22, 2007 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 More sharing options...

## Recommended Posts

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