Register to reply

Proof by contradiction

by xeon123
Tags: contradiction, proof
Share this thread:
xeon123
#1
Feb18-12, 10:19 AM
P: 81
I never understand the proof by contradiction, because somewhere in the middle I always lost myself.

In this http://www.physicsforums.com/showthread.php?t=523874 there's an example of proof by contradiction.

If n is an integer such that n^2 is odd, then n must be odd.

So assume that n is an integer such that n^2 is odd. There are 2 possible cases: n can be odd or n can be even. If we show that n cannot be even, then it must be odd.
So, assume that n is even, then it has the form n=2k. But then n2=(2k)^2=4k^2=2(2k^2). This has the form 2m (with m=2k^2), thus n^2 is even. But we made the assumption that n^2 was odd, so we have reached a contradiction. So, n cannot be even (otherwise n^2 must be even), hence n must be odd.

We assume that if n^2 is odd than n is odd. This means that if n^2 is even, n can be odd or even. How can I proof a contradiction if n is even? It doesn't tell me nothing.
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
alan2
#2
Feb18-12, 10:46 AM
P: 199
No, n^2 even implies n even. You are trying to show that if n^2 is odd, then n must be odd. So you assume that it's not true, i.e. if n^2 is odd then n is not necessarily odd. The only other choice is n is even. So suppose n^2 is odd and n is even. The result above is that if n is even then n^2 is also even. This contradicts the original assertion that n^2 was odd so it can not be true that if n^2 is odd, then n is even. The only choice left is that if n^2 is odd, then n is odd.


Register to reply

Related Discussions
Proof by Contradiction Calculus & Beyond Homework 1
Proof by contradiction Precalculus Mathematics Homework 2
Proof by contradiction Calculus & Beyond Homework 1
Proof By Contradiction Calculus & Beyond Homework 7