# 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 $\displaystyle x,y\in\mathbb{R},$ $\displaystyle x\geq 1$ and $\displaystyle y\geq 1\Rightarrow x\cdot y\geq 1$

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

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

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

But $\displaystyle y\geq 1$, so $\displaystyle 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

$\displaystyle \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 $\displaystyle x,y\in\mathbb{R},$ $\displaystyle x\geq 1$ and $\displaystyle y\geq 1\Rightarrow x\cdot y\geq 1$

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

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

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

But $\displaystyle y\geq 1$, so $\displaystyle 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 $\displaystyle n^2=2^2=4$ and $\displaystyle n!=2!=2$, $\displaystyle 3^2=9$and $\displaystyle 3!=3*2=6$, $\displaystyle 4^2=16$ and $\displaystyle 4!=4*3*2=24$

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

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

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

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

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

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

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

$\displaystyle n\cdot n! +k+2n+1\in\mathbb{N}$ and so therefore $\displaystyle (n+1)!-(n+1)^2 \in\mathbb{N}$ and so therefore $\displaystyle (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 $\displaystyle m<n$ is by definition equivalent to $\displaystyle (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