# Contrapositive proof

• Sep 26th 2009, 07:10 AM
Kasperloeye
Contrapositive proof
Hey New here on the forum. I have a small problem with some contrapositive proofs..

I have to make a contrapositive proof that:
∀x, y ∈ R : x · y < 1 ⇒ x < 1 ∨ y < 1

I can logically see what I'm supposed to do.. and that the statement is correct.. but how do i prove it?? I know that the normal way is to prove that http://upload.wikimedia.org/math/7/2...53a3799b9a.png .. but I'm a little stuck from there.. anyone here who can help?
• Sep 26th 2009, 07:42 AM
artvandalay11
So you must prove that For all $x,y\in\mathbb{R},$ $x\geq 1$ and $y\geq 1\Rightarrow x\cdot y\geq 1$

Idk how rigororous you need this proof to be...

The general idea is Let $x,b\in\mathbb{R}$ with $x,y\geq 1$

So we can multiply both sides of $x\geq 1$ by y to get $xy\geq y$

But $y\geq 1$, so $xy\geq y\geq 1$
• Sep 26th 2009, 07:55 AM
Plato
Quote:

Originally Posted by Kasperloeye
Hey New here on the forum. I have a small problem with some contrapositive proofs..
I have to make a contrapositive proof that:
∀x, y ∈ R : x · y < 1 ⇒ x < 1 ∨ y < 1

$\left( {x \geqslant 1 \wedge y \geqslant } \right)\; \Rightarrow \;\left( {x \cdot y \geqslant 1} \right)$
• Sep 27th 2009, 12:19 AM
Kasperloeye
Thanks ^^
Quote:

Originally Posted by artvandalay11
So you must prove that For all $x,y\in\mathbb{R},$ $x\geq 1$ and $y\geq 1\Rightarrow x\cdot y\geq 1$

Idk how rigororous you need this proof to be...

The general idea is Let $x,b\in\mathbb{R}$ with $x,y\geq 1$

So we can multiply both sides of $x\geq 1$ by y to get $xy\geq y$

But $y\geq 1$, so $xy\geq y\geq 1$

Thanks that really cleared things for me ^^ all hail the mighty proofmaster (Bow) Hehe.. but then i have another question..

Is it possible to make a contrapositive proof to prove that n² <= n! ? and by that i mean for which nonnegative integers would the statement apply.
• Sep 27th 2009, 05:56 AM
artvandalay11
Quote:

Originally Posted by Kasperloeye
Thanks that really cleared things for me ^^ all hail the mighty proofmaster (Bow) Hehe.. but then i have another question..

Is it possible to make a contrapositive proof to prove that n² <= n! ? and by that i mean for which nonnegative integers would the statement apply.

Are you familiar with proof by induction?

You wouldn't use a contrapositive proof, you would use proof by induction. You're base case would be n=4 since this fails for n=2 as $n^2=2^2=4$ and $n!=2!=2$, $3^2=9$and $3!=3*2=6$, $4^2=16$ and $4!=4*3*2=24$

So above we showed $n^2\leq n!$ for n=4

Now we assume $n^2\leq n!$ for some n and show it is true for $(n+1)$

So consider $(n+1)!-(n+1)^2=(n+1)n!-(n^2+2n+1)$ (we need to show this quantity is a natural number)

$=n\cdot n!+n!-n^2+2n+1$

By our assumption $n^2\leq n!$ so $n!-n^2\geq 0$

So $n\cdot n!+n!-n^2+2n+1=n\cdot n! +k+2n+1$ for some $k\geq 0$

And now since $n\in\mathbb{N},$ $n\cdot n!\in\mathbb{N}$ and $2n\in\mathbb{N}$ and $1\in\mathbb{N}$ so

$n\cdot n! +k+2n+1\in\mathbb{N}$ and so therefore $(n+1)!-(n+1)^2 \in\mathbb{N}$ and so therefore $(n+1)!\geq (n+1)^2$

so by induction we are done

Now thats just an outline, you would need to "know/prove" that the sum of two natural numbers is a natural number and that the product of two natural numbers is a natural number, and something should be said like if k=0, nothing changes and if k>1 then k is a natural number

You also need to be aware that $m is by definition equivalent to $(m-n)\in\mathbb{N}$
• Sep 27th 2009, 06:24 AM
Kasperloeye
So I'm not in a totally wrong direction when I did this:

Quote:

Originally Posted by CompuChip
In your particular problem, you could consider a statement like "For all n >= 2, n2 <= (n!)".

Hehe that's where it get's funny.. because n>= 2, n²<=n! is like 2²<=2! 4 <= 2 .. so it has to n /= 2

So Basis should be n=4 since

4²<=4!
16 <=24

SO: For n=k, k²<=k!

but if we take it with n= k+1 it's (k+1)² <=(k+1)!
(k+1)² <= (k+1)(k!)
(k+1) <= k!
but our hypothasis says k^2 <= k!, and because k+1 <= k^2 (for k>=4) then
k+1 <= k^2 <= k!.

right??
• Sep 27th 2009, 07:36 AM
artvandalay11
yes that's also valid but for a rigorous proof you would need to state that k+1>0 and then need to prove that statement k+1<=k^2

but yes your ideas and logic are sound