# Mathematical proofs

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Mar 7th 2007, 07:41 AM
Possible actuary
Mathematical proofs
Anyone here good at mathematical proofs and would be willing to help me understand them?
• Mar 7th 2007, 07:46 AM
Jhevon
Quote:

Originally Posted by Possible actuary
Anyone here good at mathematical proofs and would be willing to help me understand them?

depends on what kind of proofs? what do you mean? give me an example of a question
• Mar 7th 2007, 08:27 AM
Aryth
Quote:

Originally Posted by Possible actuary
Anyone here good at mathematical proofs and would be willing to help me understand them?

There are 5 types of proof, and I will give an example of each:

The first type, and the strongest type, is Direct Proof. If you can directly prove it, then it is the best way to prove something.

Theorem. If a divides b and b divides c then a divides c.

Proof. By our assumptions, and the definition of divisibility, there are natural numbers k1 and k2 such that
b = a k1 and c = b k2. Consequently,
c = b k2 = a k1 k2. Let k = k1 k2. Now k is a natural number and c = a k, so by the definition of divisibility, a divides c

The second type, and probably the most used back in the ancient times, is proof by contradiction. We take a theorem that we assume is true, and in order to prove it by contradiction, we assume that our theorem is true when it is false and try to logically work it out that way. If we come up with a contradiction in the proof, then it is true when our original theorem is true and it is false when we assume that our theorem is true when it is false. The most famous proof is probably Eulid's proof that the sqrt(2) is an irrational number.

Theorem. √2 cannot = p/q

Proof. By contradiction we assume that our original Theorem is false:

√2 = p/q

2 = p^2/q^2

2q^2 = p^2

By this we see that p is positive so that:

p = 2r

Now we plug 2r into p^2

2q^2 = 4r^2

q^2/r^2 = 2

q/r =
√2

√2 can't equal both p/q AND q/r, thus we have a contradiction, proving our original theorem true.

The third type of contradiction is Proof by Contrapositive. Where we take the contrapositive of a theorem and prove it.

The difference between the Contrapositive method and the Contradiction method is subtle. Let's examine how the two methods work when trying to prove "If P, Then Q".
• Method of Contradiction: Assume P and Not Q and prove some sort of contradiction.
• Method of Contrapositive: Assume Not Q and prove Not P.
The method of Contrapositive has the advantage that your goal is clear: Prove Not P. In the method of Contradiction, your goal is to prove a contradiction, but it is not always clear what the contradiction is going to be at the start.

Definitions.
1. An integer x is called even (respectively odd) if there is another integer k for which x = 2k (respectively 2k+1).
2. Two integers are said to have the same parity if they are both odd or both even.
For the purpose of this example we will assume as proved that each integer is either even or odd. Theorem. If x and y are two integers for which x+y is even, then x and y have the same parity.
Proof. The contrapositive version of this theorem is "If x and y are two integers with opposite parity, then their sum must be odd." So we assume x and y have opposite parity. Since one of these integers is even and the other odd, there is no loss of generality to suppose x is even and y is odd. Thus, there are integers k and m for which x = 2k and y = 2m+1. Now then, we compute the sum x+y = 2k + 2m + 1 = 2(k+m) + 1, which is an odd integer by definition.

The fourth type of proof is If and only If Proofs. It is just proving two implications.

In this example we will use a very useful fact about integers, the so called Division Algorithm: If n and m are integers, then there are two other integers q and r, where 0 <= r < m, and such that n = qm + r. For example, if n = 103 and m = 15, then 103 = (6)(15) + 13. (That is, if we divide15 into 103, we get a quotient of q = 6, with a remainder of r = 13.) Theorem. If a is an integer, then a is not evenly divisible by 3 if, and only if, a2 -1 is evenly divisble by 3.
Proof. Since this is an "If, and Only If" theorem, we must prove two implications.
("If") We must prove "a is not evenly divisible by 3 if a2 -1 is evenly divisble by 3". So we assume that 3 evenly divides a2 -1 = (a-1)(a+1). Since 3 is a prime number, 3 must evenly divide either a-1 or a+1. In either case, it should be apparent that 3 cannot evenly divide a.
("Only If"). We must prove "a is not evenly divisible by 3 only if a2 -1 is evenly divisble by 3." This means "If a is not evenly divisible by 3, then a2 -1 is evenly divisble by 3". This is where we use the division algorithm stated above. We can write a = 3q + r, where r = 0, 1 or 2. Our assumption that a is not divisible by 3 implies r cannot be 0. If r =1, then a-1 = 3q and so 3 evenly divides a2 -1 = (a-1)(a+1). A similar argument works if r = 2.

The fifth type of proof, and probably the most common, is proof by Induction. It is taking something and then proving it and then proving it for the next consequtive situation using a basic assumption, thus proving it for all situations that follow the same criteria.

Theore. For any positive integer n, 1 + 2 + ... + n = n(n+1)/2.
Proof. (Proof by Mathematical Induction) Let's let P(n) be the statement "1 + 2 + ... + n = (n (n+1)/2." (The idea is that P(n) should be an assertion that for any n is verifiably either true or false.) The proof will now proceed in two steps: the initial step and the inductive step.
Initial Step. We must verify that P(1) is True. P(1) asserts "1 = 1(2)/2", which is clearly true. So we are done with the initial step.
Inductive Step. Here we must prove the following assertion: "If there is a k such that P(k) is true, then (for this same k) P(k+1) is true." Thus, we assume there is a k such that 1 + 2 + ... + k = k (k+1)/2. (We call this the Inductive Assumption.) We must prove, for this same k, the formula 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2.
This is not too hard: 1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k(k+1) + 2 (k+1))/2 = (k+1)(k+2)/2. The first equality is a consequence of the inductive assumption.

And that's about it for proofs, enjoy.
• Mar 7th 2007, 10:46 AM
ThePerfectHacker
There is actually another type of proof, which my favorite mathemation used a lot and developed it.

It is called "Infinite Descent".
• Mar 7th 2007, 04:18 PM
Possible actuary
I am taking a university class titled "Algebraic Structures" and all we have done so far is proofs. I am having a hard time understanding when given something to prove where to start. I understand truth tables, implications and iff. I am having a little trouble stating negations.

An example: Let x be an integer. Prove that if 3 does not divide (x^2+x), then 3 does not divide x and 3 does not divide (x+1).

I am also having some trouble with the 3 (or 2 or whatever #) does or does not divide (something).

Thanks
• Mar 7th 2007, 05:44 PM
Jhevon
Quote:

Originally Posted by Possible actuary
I am taking a university class titled "Algebraic Structures" and all we have done so far is proofs. I am having a hard time understanding when given something to prove where to start. I understand truth tables, implications and iff. I am having a little trouble stating negations.

An example: Let x be an integer. Prove that if 3 does not divide (x^2+x), then 3 does not divide x and 3 does not divide (x+1).

I am also having some trouble with the 3 (or 2 or whatever #) does or does not divide (something).

Thanks

so the negation rules are just rules you have to memorize. the negation of "and" is "or", the negation of "for all" is "there exists", the negation for "A=>B" is "A and ~B", among others, your text should tell you all of these. looking at the problem you gave, here are some general principles you want to follow. unlike with trig identities, which i always tell people to work on the most complicated side, with proofs, you usually want to start with the simpler side. if we do a direct proof with this question, we would have to worry about remainders, since 3 does not divide, and we would have to deal with 3 does not divide x^2 + x. that is not something we want to do, proofs are hard enough as they are, we dont want to make them harder by tackling the more complicated side. here, the contropositive is the best proof (read above for the details), the contropositive says we can prove A=>B (which is the kind of statement we have here, do you see that?) by proving ~B => ~A. this way we dont have to deal with remainders since "does not divide" becomes "divide" and we work with 3|x and 3|x+1 as opposed to working with the quadratic. here goes.

Proof:

Assume by way of the contropositive that 3|x + 1 or 3|x. then x = 3c for some integer c, or x + 1 = 3d for some integer d. thus we have 2 cases:

case 1: x = 3c

=> x^2 + x = (3c)^2 + 3c = 9c^2 + 3c = 3(3c^2 + c)

since 3c^2 + c is an integer, 3|x^2 + x

case 2: x = 3d - 1

=> x^2 + x = (3d - 1)^2 + 3d - 1 = 9d^2 - 6d + 1 + 3d - 1 = 9d^2 - 3d = 3(3d^2 - d)

since 3d^2 - d is an integer, 3|x^2 + x

so we see that in both cases of the contropositive, if 3|x or 3|x + 1 then 3|x^2 + x, and thus the contropositive is true, that is, if if 3 does not divide (x^2+x), then 3 does not divide x and 3 does not divide (x+1)

QED

so in general, when you have a problem with does not divide, it is usually better to use the contropositive to turn it into divides
• Mar 7th 2007, 05:46 PM
Jhevon
Quote:

Originally Posted by Jhevon

Proof:

Assume by way of the contropositive that 3|x + 1 or 3|x. then x = 3c for some integer c, or x + 1 = 3d for some integer d. thus we have 2 cases:

case 1: x = 3c

=> x^2 + x = (3c)^2 + 3c = 9c^2 + 3c = 3(3c^2 + c)

since 3c^2 + c is an integer, 3|x^2 + x

case 2: x = 3d - 1

=> x^2 + x = (3d - 1)^2 + 3d - 1 = 9d^2 - 6d + 1 + 3d - 1 = 9d^2 - 3d = 3(3d^2 - d)

since 3d^2 - d is an integer, 3|x^2 + x

so we see that in both cases of the contropositive, if 3|x or 3|x + 1 then 3|x^2 + x, and thus the contropositive is true, that is, if if 3 does not divide (x^2+x), then 3 does not divide x and 3 does not divide (x+1)

QED

would you like me to explain this proof even more? i can show you the parts as to how truth tables connect with this and such, if necessary
• Mar 7th 2007, 06:16 PM
Possible actuary
I think that I just now got the 3 does or does not divide thing 3 l (x+2) is same as

3
----- = c, c is some integer
(x+2)

When you are doing a contrapositive proof, do you always do ~B=>~A when given A=>B? Would it be safe to say direct proof should be tried first, then contrapositive and then contradiction? Contradiction is what we just started on today.

For contrapositive proofs, if you are given ____ then prove by _____. :

A<=>B then prove by ~B<=>~A?
I can't think of any other cases/possibilities.
• Mar 7th 2007, 06:40 PM
Jhevon
Quote:

Originally Posted by Possible actuary
I think that I just now got the 3 does or does not divide thing 3 l (x+2) is same as

3
----- = c, c is some integer
(x+2)

that's the other way around. that's (x + 2)|3, but in any case it is conventionally written as a product. so for (x + 2)|3, instead of 3/(x + 2) = c, we write 3 = c(x + 2)

Quote:

When you are doing a contrapositive proof, do you always do ~B=>~A when given A=>B?
yes, you always do this. this is what proving by contropositive means

Quote:

Would it be safe to say direct proof should be tried first, then contrapositive and then contradiction? Contradiction is what we just started on today.

no. this is especially ill advised on tests. proofs can be very involved, it is not wise to try several proof techniques hoping one will work. you have to make an educated guess as to which proof to use, this requires more critical thinking than experience. experience helps when several ways of proving something involve pretty much the same amount of work, but one is preferable over the other. direct proofs are generally prefered, however there are other situations when other proof techniques are prefered, even required. for instance, when you want to DISPROVE something, a proof by contradiction is usually the way to go.

Quote:

For contrapositive proofs, if you are given ____ then prove by _____. :

A<=>B then prove by ~B<=>~A?
I can't think of any other cases/possibilities.
you answered this question already. it's given A=>B then prove by ~B=>~A

iff statements (that is statements described by <=>) are proven one implication at a time (in most cases) so the standard definition for contropositive still works
• Mar 7th 2007, 07:21 PM
Possible actuary
Quote:

Originally Posted by Jhevon
would you like me to explain this proof even more? i can show you the parts as to how truth tables connect with this and such, if necessary

I just ran the truth table and I want to make sure I have this logic correct. We can prove P=>Q&R by doing a contrapositive by saying ~Q or ~R => ~P because they are logically equivalent.
• Mar 7th 2007, 07:24 PM
Possible actuary
Quote:

Originally Posted by Jhevon
no this is especially ill advised on tests. proofs can be very involved, it is not wise to try several proof techniques hoping one will work. you have to make an educated guess as to which proof to use, this requires more critical thinking than experience. experience helps when several ways of proving something involve pretty much the same amount of work, but one is preferable over the other. direct proofs are generally prefered, however there are other situations when other proof techniques are prefered, even required. for instance, when you want to DISPROVE something, a proof by contradiction is usually the way to go.

When would be a case when you want to disprove something?
• Mar 7th 2007, 07:30 PM
Possible actuary
Okay how about proofs involving congruence of integers. How the book puts it: For integers a,b and n>or=2, we say that a is congruent to b modulo n. Don't know how to convey the congruent symbol. I have no idea what I am doing here. Could we start with the very basics on congruence and what (mod x) has to do with it?

The proof that she gave on a quiz: Let n be an integer. Prove that if n is not congruent to 0 (mod 3), then n^2 is congruent to 1 (mod 3).

Also, shouldn't I have written 3 l (x+1) as

(x+1)
----- = c therefore 3c=(x+1)
3
• Mar 7th 2007, 07:59 PM
Jhevon
Quote:

Originally Posted by Possible actuary
When would be a case when you want to disprove something?

disprove that sqrt(2) is a rational number

or other statements that begin with "for every" or "there exists"

or

every even integer is the sum of an even and an odd integer, stuff like that
• Mar 7th 2007, 08:17 PM
Jhevon
Quote:

Originally Posted by Possible actuary
Okay how about proofs involving congruence of integers. How the book puts it: For integers a,b and n>or=2, we say that a is congruent to b modulo n. Don't know how to convey the congruent symbol. I have no idea what I am doing here. Could we start with the very basics on congruence and what (mod x) has to do with it?

The proof that she gave on a quiz: Let n be an integer. Prove that if n is not congruent to 0 (mod 3), then n^2 is congruent to 1 (mod 3).

we say a is conguent to b (mod n) if n|(a - b). that is a - b = nc for some integer c. it's basically a way to categorize divisibility based on remainders. example 24 is congruent to 6 (mod 9). that is 9|(24 - 6) so 9|18, which is true

remainders occur when something is not congruent.

Let n be an integer. Prove that if n is not congruent to 0 (mod 3), then n^2 is congruent to 1 (mod 3).

Proof:

We employ a direct proof. assume n is not congruent to 0 (mod 3), then 3 does not divide (n - 0) = n. therefore, n = 3c + r, where r is the remainder when we divide by 3, thus r = 1 or 2 (note, if r is 0 it means the number was divisible by 3, if r is 3, it means the number is divisible by 3). thus we have 2 cases: (1) n = 3c + 1, and (2) n = 3c + 2

case 1: n = 3c + 1

if n = 3c + 1, then n^2 - 1= (3c + 1)^2 - 1 = 9c^2 + 6c + 1 - 1 = 3(3c^2 + 2c).
since 3c^2 + 2c is an integer, 3|n^2 - 1 and so n^2 is congruent to 1 (mod 3).

case 2: n = 3c + 2

if n = 3c + 2, then n^2 - 1 = (3c + 2)^2 - 1 = 9c^2 + 6c + 4 - 1 = 3(3c^2 + 2c + 1)

since 3c^2 + 2c + 1 is an integer, 3|n^2 - 1, and so n^2 is congruent to 1 (mod 3).

So we see in both cases where n is not congruent to 0 (mod 3), n^2 is congruent to 1 (mod 3).

QED

Quote:

Also, shouldn't I have written 3 l (x+1) as

(x+1)
----- = c therefore 3c=(x+1)
3
yes, that's correct. wasnt that what we had last time?
• Apr 3rd 2007, 07:54 PM
Possible actuary
Got another one....
I am having some trouble getting a proof started by proving or disproving.

Given: For every positive irrational number b, there exists an irrational number a with 0<a<b.

I believe that this statement is true. The book suggests that to start the proof by: Let b be a positive irrational number. Consider a=b/2.

I am having a hard time getting this one started.

Thanks
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last