1. Mar 12, 2013

### setvectorgroup

1. The problem statement, all variables and given/known data

Write down careful proofs of the following statements:

a) sqrt(6)- sqrt(2) > 1

b) If n is an integer such that n^2 is even, then n is even.

c) If n= m^3- m for some integer m, then n is a multiple of 6

3. The attempt at a solution

I will rely on P - > Q and not Q - > not P to try and prove the above statements.

a) I think I cant use direct proof (P - > Q) here, because no matter how true Q is, it wont say anything important about P which is the statement sqrt(6)- sqrt(2) > 1. Instead, I will use contradiction.

Contradiction: not P - > Q(false), not Q - > P

sqrt(6)- sqrt(2) ≤ 1

6- sqrt(24) + 2 ≤ 1

2sqrt(12) ≤ 3 (false statement). Negating this statement makes sqrt(6)- sqrt(2) > 1 true.

b) n^2 - > n= 2m

If we assume not P, then n^2 can be assumed to be odd: (1+ 2m)^2= 1+ 4m+ 4m^2= 1+ 4(m+m^2) which is false because we are given that n^2 is even.

From here it's obvious that n should be even to avoid contradiction.

c) not P: 1+ 6m = m^3- m where n is not a multiple of 6.

1+ 6m = m^3- m

0= m^3- 7m -1 ( I will assume that this result is false because solving for x introduces imaginary numbers which I am not sure if I am allowed to work with).

Obviously, n is a multiple of 6.

Correct/Wrong?

2. Mar 12, 2013

### Staff: Mentor

You have a mistake above. (√6 - √2)2 = 6 - 2√12 + 2
2√12 ≠ √24
It would be helpful if you included all the information.

n2 is even $\Rightarrow$ n is even

3. Mar 12, 2013

### setvectorgroup

Can I use n^2 is even - > n = 2m, where m is any integer?

As for c) not P: 1+ 6m = m^3- m where n is not a multiple of 6.

To force n to be a non-multiple of 6, we can divide n by 6 such that it yields remainder of 1 or 2. Then n= 1+6m is the non-multiple of 6.

4. Mar 12, 2013

### setvectorgroup

Oh, I see about 2√12 ≠ √24.

First I wrote √24, then 2√12. It should be 2√12.

5. Mar 12, 2013

### Staff: Mentor

Where m is some integer.
It's much simpler to prove this statement directly.
Given: n = m3 - m

Factor the cubic expression and proceed from there.

6. Mar 12, 2013

### setvectorgroup

Thank You.

Before I attempt the direct proof I'd like to know if what I wrote in c) passable as a proof, at least, conceptually? I mean is it correct, but ugly or incorrect and ugly?

7. Mar 12, 2013

### Staff: Mentor

For c, I don't think what you had is correct.

P: n= m3- m for some integer m
Q: n is a multiple of 6

~P: $\forall n$, n ≠ m3- m

If you're intending to prove the contrapositive, then you need to show that ~Q $\Rightarrow$ ~P

If you're doing a proof by contradiction, then show that P ^ ~Q leads to a contradiction. I don't see that you did either of those.

8. Mar 14, 2013

### setvectorgroup

I think what I did above looks a mess. I'd like to redo all that.

Prove: If n is an integer such that n2 is even, then n is even.

1. Will this fly:

Givens: n^2 is even (P)

Goal: P- > Q

I want to use the fact that not Q - > not P to get P - > Q

New Given: not Q

New Goal: not P

Suppose that n = 2m + 1 is odd( not Q). Then n^2 = (2m + 1)^2 = 4m^2 + 4m + 1 = 1 + 4(m^2 + m) (not P). Therefore P - > Q and if n is an integer such that n2 is even, then n is even
.

???

2. If the above is right, how can I better re-wright the bold part?

3. Is the above a proof by contrapositive or contradiction? What's the difference between the two?

4. I tried to do this differently, but got stuck:

Givens: n^2 is even ( P)

Goal: P - > Q

How can I modify n^2 directly so that it yields an even n? Also, if I could do that, would that be considered a direct proof?

Thanks.

9. Mar 14, 2013

### Staff: Mentor

This is correct, but not well organized. You can omit all of the P and Q stuff, and focus on the statements that are involved.
I would organize things like this:

Prove: For an integer n, if n2 is even, then n is even.

Proof by contrapositive:
Suppose n is odd.
Then n = 2m + 1 for some integer m.
n2 = (2m + 1)2 = 4m2 + 4m + 1 = 2(2m2 + 2m) + 1, which is clearly an even integer.
∴ n is an odd integer $\Rightarrow$ n2 is an odd integer.
Since the contrapositive is equivalent to the original proposition, the original proposition is proved.

You mean "rewrite the bold part."
Contrapositive.
If the original proposition is P $\Rightarrow$ Q, its contrapositive is ~Q $\Rightarrow$ ~P.

In a proof by contradiction, which is different, you are starting with the assumption that the original proposition is false. If you then arrive at a contradiction, this means that your assumption must have been incorrect, meaning that the original proposition must actually be true.

In symbols, (P $\Rightarrow$ Q) $\Leftrightarrow$ ~P V Q,
so ~(P $\Rightarrow$ Q) $\Leftrightarrow$ ~(~P V Q) $\Leftrightarrow$ P ^ ~Q.

In a proof by contradiction, you assume that the premise (or hypothesis - the "if" part) is true and that the conclusion is false. The goal is always to arrive at a contradiction.

Last edited: Mar 14, 2013
10. Mar 15, 2013

### eddybob123

You can factor the RHS of n=m^3-m into m(m^2-1), then it is easy proof by exhaustion:
If m=1 mod 6, then m^2 is also 1 mod 6, so m(m^2-1) is a multiple of 6.
If m=2 mod 6, then m^2 is 4 mod 6 so m^2-1 is a multiple of 3, and since m is even, then that means that m(m^2-1) is a multiple of 6.
You can finish up the rest