2.2 Proof

Helpful Tools for Calculus, Chapter 2: Helpful Tools for the Mathematics of Calculus

Previous Section: 2.1 Logic

Terminology

In mathematics, proof is an important piece of any topic. A mathematician may develop theories and identify patterns, but a proof may be what solidifies the knowledge in a concrete way. Often, there are many different ways to prove any one idea. In this section we will discuss three main methods of proof and some examples of each in mathematics.
Before we begin discussing methods, some terminology may be helpful. The following vocabulary is often used when discussing mathematical proofs and helps to identify differences between them:

A Theorem is a statement that can be proved and has been shown to be true.
A Proposition is a less important theorem, sometimes called a fact.
An Axiom is a statement, sometimes called a postulate, that we assume to be true.
A Lemma is a smaller theorem often used to help with a series of more complicated proofs. Sometimes multiple lemmas are proved to make a more general statement about a larger topic.
A Corollary is an easily drawn conclusion or a somewhat obvious proposition.
A Conjecture is a statement that is proposed to be true, but has not been shown to be true yet.

Something that may be important to note is that many of the proofs in this text may be sufficient for the level of mathematics being studied, but in more advanced mathematics our reasoning and proofs may need to be more formalized.

Direct Proof

A Direct Proof is a proof that begins with some premises and shows a conclusion follows directly from it. This is the most obvious approach to any problem.

Example 1: Prove that if a whole number, n, is even that n^2 must also be even.

Solution: Let n=2k for some k∈Z, since n is even. Thus, n^2=(2k)^2=4k^2=2(2k^2 )=2m where m=(2k^2 ). Since k∈Z, k^2∈Z and 〖2k〗^2∈Z thus n^2=2m for some m∈Z and n^2 is even.

Example 2: Prove that given two odd integers, their product is also odd.

Solution: Let x=2a+1 and y=2b+1 for some a,b ∈Z. Then
xy=(2a+1)(2b+1)
=4ab+2a+2b+1
=2(2ab+a+b)+1
=2(c)+1
Since a,b∈Z we can conclude that 2ab+a+b∈Z and with c=2ab+a+b then xy is also odd.

Example 3: Prove the Pythagorean Theorem Algebraically.

Solution: Using the following image
//picture
We can say 〖(a+b)〗^2=4∙1/2 ab+c^2 because 〖(a+b)〗^2 is the area of the entire square and there are four triangles whose areas are 1/2 ab and a square with area c^2 inside of it.
Thus,
〖(a+b)〗^2=4∙1/2 ab+c^2
a^2+2ab+b^2=2ab+c^2
a^2+b^2=c^2

Indirect Proof (Proof by Contradiction)

An Indirect Proof is a proof by contraction. It begins by assuming something we hope to disprove, or that we know to be wrong. We follow this assumption in order to show that something that cannot be true follows (the contradiction). Thus, the assumption was wrong and the conclusion is the opposite.

Example 4: Prove that if n^2 is even then n must be even too (Note that this is different than example 1).

Solution:

Let n^2 be even, so n^2=2k,k∈Z. Assume that n is odd, so n=2a+1,a∈Z. Thus,
n^2=〖(2a+1)〗^2
=4a^2+4a+1
=2(2a^2+2a)+1
=2(b)+1,b∈Z
So, n^2 is odd. This contradicts the original claim that n^2 is even. So n cannot be odd and must be even.

Example 5: Prove that √2 is irrational.

Solution:

Let us begin by assuming that √2 is rational. That is to say, there exists some integers that define it: ∃p,q∈Z so that p/q=√2 and p/q is in simplified form.
Then, since p/q=√2 we can do the following:
p/q=√2
p=q√2
p^2=2q^2
Thus p^2 is even. By the previous example, we know that p is also even. So, p=2k,k∈Z.
p^2=2q^2
〖(2k)〗^2=2q^2
〖4k〗^2=2q^2
2k^2=q^2
Thus q^2 and q are both even as well. Let’s say that q=2m,m∈ZThat means:
p/q=√2
2k/2m=√2
Which simplifies to k/m=√2. This is a contradiction to our original claim that p/q is in simplified form. Thus, √2∉ Q.

Example 6: Prove that there are infinitely many prime numbers.

Solution: (Note: This proof is a simplified version of a more complex argument, but should be satisfactory for this introduction to proof)

Let’s assume that there are finitely many prime numbers p_1,…,p_n with p_n being the last prime number. Let n=p_1∙… ∙ p_n+1. Thus n is not divisible by any of the prime numbers and must be a prime number itself and n is larger than p_n. This contradicts the claim that p_n is the last prime number. Thus, there are an infinite number of prime numbers.

Proof by Induction

This is the most confusing and tricky of the cases we will discuss. There are three main steps, and I find that a staircase metaphor helps:
First we begin by checking that a base case is true. That is to say, we plug in the smallest possible number or check the simplest possible case that we are making a claim about and see if our conclusion is true. This is like checking if we can get onto the first step of a staircase. Can we climb a single stair?
Second we assume that some arbitrary case is true and check if it follows that the next case is also true. If it works for some number (k), does it work for the next number (k+1)? This is similar to asking whether or not, given we are on the staircase, we can get to next stair on the staircase. This step relies heavily on using the assumption for the kth step, which is called the induction hypothesis.
Third, by combining the two previous ideas (the first step works, and any step leads to the next step) then we can conclude that all of the infinitely many steps that follow are also true. Thus, the statement is true for all values or cases in our domain.

Example 7: Prove 1+2+⋯+(n-1)+n= 1/2 n(n+1), ∀n∈N

Solution:
Base Case: n=1
1=1/2∙2
=1/2 1(1+1)

Induction Hypothesis: Let 1+2+⋯+(k-1)+k= 1/2 k(k+1),k∈N
Induction Step: Then 1+2+⋯+(k-1)+k+(k+1)=1/2 k(k+1)+(k+1)
=1/2 k^2+1/2 k+k+1
=1/2 k^2+3/2 k+1
=1/2(k^2+3k+2)
=1/2 (k+1)(k+2)

Thus 1+2+⋯+(n-1)+n= 1/2 n(n+1), ∀n∈N

Example 8: Prove 5^(2n+1)+2^(2n+1) is divisible by 7 for all n≥0

Solution:
Base Case: n=0
5^(2(0)+1)+2^(2(0)+1)=5^1+2^1
=7

Induction Hypothesis: 5^(2k+1)+2^(2k+1)=7m, k,m∈N
Induction Step: 5^(2(k+1)+1)+2^(2(k+1)+1)=5^(2k+3)+2^(2k+3)
=5^2∙5^(2k+1)+〖2^2∙2〗^(2k+1)
=25∙5^(2k+1)+〖4∙2〗^(2k+1)
=21∙5^(2k+1)+〖4∙5〗^(2k+1)+〖4∙2〗^(2k+1)
=7(3∙5^(2k+1) )+4(5^(2k+1)+2^(2k+1))
=7(3∙5^(2k+1) )+4 (7m)
=7(3∙5^(2k+1)+4m)
=7x, x∈N
Thus, 5^(2n+1)+2^(2n+1) is divisible by 7 for all n≥0

Example 9: Prove 1/(1∙2)+1/(2∙3)+⋯+1/(n∙(n+1) )=n/(n+1), ∀n∈N

Solution:
Base Case: n=1
1/(1∙2)=1/2
=1/(1+1)

Induction Hypothesis: 1/(1∙2)+1/(2∙3)+⋯+1/(k∙(k+1) )=k/(k+1), k∈N
Induction Step: 1/(1∙2)+1/(2∙3)+⋯+1/(k∙(k+1) )+1/((k+1)∙((k+1)+1))=k/(k+1)+1/((k+1)∙((k+1)+1))
=k/(k+1)+1/((k+1)(k+2))
=(k(k+2))/((k+1)(k+2))+1/((k+1)(k+2))
=(k(k+2)+1)/((k+1)(k+2))
=(k^2+2k+1)/((k+1)(k+2))
=((k+1)(k+1))/((k+1)(k+2))
=((k+1))/((k+2))
=((k+1))/((k+1)+1)
Thus, 1/(1∙2)+1/(2∙3)+⋯+1/(n∙(n+1) )=n/(n+1), ∀n∈N

Review