Scribd
Upload
26 views3 pages

Examples of Mathematical Proofs

The document provides various techniques for proving implications in mathematics, specifically in the context of discrete mathematics. It covers methods such as trivial proof, direct proof, indirect proof, proof by contradiction, and proof by cases, with examples for each technique. Each theorem is accompanied by a detailed proof illustrating the method used.

Uploaded by

arijit.maths
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
26 views3 pages

Examples of Mathematical Proofs

The document provides various techniques for proving implications in mathematics, specifically in the context of discrete mathematics. It covers methods such as trivial proof, direct proof, indirect proof, proof by contradiction, and proof by cases, with examples for each technique. Each theorem is accompanied by a detailed proof illustrating the method used.

Uploaded by

arijit.maths
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

PROOF EXAMPLES

MAT229 DISCRETE MATHEMATICS FOR COMPUTER SCIENCE

Here are some examples of techniques used to prove implications in


the form p → q are true. Recall that p is the hypothesis and q is the
conclusion.

1. Trivial Proof
A trivial proof is one in which the conclusion is already known to be
true. For example:
Theorem 1. If n ≥ 0 then n2 ≥ 0.
Proof. Since n2 is always a nonnegative integer when n is an integer,
there is nothing to prove; the conclusion is already true. ¤

2. Direct Proof
Theorem 2. If n is an integer greater than 1, then n2 > n.
Proof.
1<n
=n·1
<n·n
= n2
Therefore n < n2 . ¤
Theorem 3. If n is an odd integer, then 3n is an odd integer.
Proof.
n = 2q + 1 for some integer q
3n = 6q + 3
= 2(3q) + 3
= 2(3q + 1) + 1
Since we’ve expressed 3n in the form 2k + 1 where k is an integer we
know that 3n is an odd integer. ¤
Date: September 2008.
1
2 MAT229 DISCRETE MATHEMATICS FOR COMPUTER SCIENCE

3. Indirect Proof
Theorem 4. If 3n + 10 > 50 then n > 13.
Proof. Assume n ≤ 13. Then 3n ≤ 39 and so 3n+10 ≤ 49, which is the
negation of the hypothesis (recall that ¬q → ¬p is logically equivalent
to p → q). ¤
Theorem 5. If n2 is even then n is even.
Proof. Assume that n is odd. We will show that n2 must also be odd.
If n is odd then there is an integer k such that n = 2k + 1. In this
case
n2 = (2k + 1)2
= 4k 2 + 4k + 1
= 2(2k 2 + 2k) + 1
Since n2 is written as an even number plus one, it must be an odd
number.
We have just directly proved that “if n is odd then n2 is odd” and
thereby indirectly proved our theorem “if n2 is even then n is even.” ¤
4. Proof by Contradiction
√
Theorem 6. 2 is an irrational number.
√
Proof. Assume that 2 rational, in which case it can be expressed as
the ratio of two integers with no factors in common:
√ a
2=
b
where a and b are both integers with no factors in common and with
b 6= 0. Clearing the fraction by multiplying both sides by b and squaring
gives
2b2 = a2
From this we see that a2 must be an even number since it is a multiple
of 2 and from one of the above examples we know that if a2 is even
then a is even. Thus we can write a = 2c for some integer c. Our last
equation then becomes
2b2 = (2c)2
= 4c2
b2 = 2c2
Notice that the last line asserts that b2 is an even number since it is a
multiple of 2, and if b2 is even then we know that b is even.
PROOF EXAMPLES 3
√
We now have a contradiction. We began by assuming that 2 = a/b
where a and b had no common factors but we’ve just found that both
a and b are even numbers, meaning they both have 2 as a√factor. Since
this is impossible, it must be that our assumption that 2 is rational
is false. ¤
Theorem 7. Let g : A → B and f : B → C. If f and f ◦ g are both
one-to-one functions then g is also a one-to-one function.
Proof. Assume that g is not one-to-one. Then ∃x1 , x2 ∈ A such that
g(x1 ) = g(x2 ) = y for some y ∈ B. If f (y) = z for some z ∈ C then
(f ◦ g)(x1 ) = (f ◦ g)(x2 ) = z, contradicting the fact that f ◦ g is one-
to-one. Therefore it must not be possible that g is not one-to-one, and
so g is indeed a one-to-one function. ¤
5. Proof by Cases
Theorem 8. |x| + |y| ≥ |x + y|
Proof. case 1: x ≥ 0, y ≥ 0. In this case |x + y| = x + y = |x| + |y|.
case 2: x ≤ 0, y ≤ 0. Now |x + y| = −(x + y) = −x + (−y) = |x| + |y|.
case 3: x ≥ 0, y ≤ 0.
|x + y| = ||x| − |y||
≤ ||x| + 2|y| − |y||
= ||x| + |y||
= |x| + |y|

case 4: x ≤ 0, y ≥ 0. Here we merely need to reverse the roles of x


and y in case 3.
Since all possible cases have been handled, and in each case we see that
|x| + |y| ≥ |x + y|, we have prove the theorem. ¤

Common questions

Powered by AI

In the proof of √2 being irrational, assuming √2 = a/b with no common factors, it's proven impossible for both a and b to be even because that would imply 2 is a common factor. This contradicts the premise of a/b being in simplest form with no common divisors .

Proof by contradiction is clearer for demonstrating that √2 is irrational because it involves assumptions about the simplest form fractions that lead to contradictions about the nature of integer properties, which can be complex to encapsulate directly .

To prove √2 is irrational using proof by contradiction, one assumes √2 is rational, expressed as a fraction a/b in simplest form. By squaring and manipulating this equation, a contradiction arises when both a and b must be even, contradicting their supposed coprime nature, thereby refuting the initial assumption .

The proof that g is one-to-one when f and f◦g are one-to-one functions relies on contradiction. If g were not one-to-one, for any x₁, x₂ in A with g(x₁) = g(x₂), then for f(y) = z, (f◦g)(x₁) = (f◦g)(x₂) = z, contradicting f◦g being one-to-one. Thus, g must be one-to-one .

In a direct proof, the hypothesis provides a starting point that is used logically and sequentially to reach the conclusion. For example, in proving that "if n is an integer greater than 1, then n² > n," we use the initial condition 1 < n to develop the inequality 1·n < n², thus reaching the conclusion n < n² .

Indirect proof establishes the truth of a mathematical statement by assuming the opposite of what needs to be proven and showing this leads to a contradiction. For example, to prove "if n² is even then n is even," we start by assuming n is odd and show this assumption leads to n² being odd, thus contradicting n² being even .

Understanding the contrapositive aids in indirect proofs because it offers a logically equivalent way to express the implication, often simplifying the proof process. For example, proving "if n² is even then n is even" by showing the contrapositive "if n is odd then n² is odd" is effective because proving integer properties this way provides clear contradiction evidence .

A trivial proof is used in logic to prove implications where the conclusion is already known to be true, making the proof straightforward. For instance, if "n ≥ 0" then "n² ≥ 0" since n² is always a nonnegative integer when n is an integer, thereby requiring no further proof .

Proof by cases establishes the inequality |x| + |y| ≥ |x + y| by considering all possible sign combinations of x and y (both non-negative, both non-positive, one non-negative and one non-positive). In each case, after simplification, the inequality holds true .

An indirect proof ensures logical consistency by assuming the negation of the statement to be proven and demonstrating this leads to a contradiction, thus affirming the original statement. For example, proving "if 3n + 10 > 50 then n > 13" assumes n ≤ 13 and finds a logical inconsistency, reinforcing the original claim .

You might also like