Transcript Mathematical Proof - College of the Siskiyous | Home

Mathematical Proof
Look what I can make this function do!
p( x)  x 2  x  41.
(No, that’s not the trick.)
p(0)  41
p(1)  43
p(2)  47
p(3)  53
p(0.5)  41.75
These are all prime numbers!
This is neither prime nor composite.
But as long as we stick with counting numbers…
Proposition: The function p(x) defined above will give
prime numbers for every counting number x.
All it would take would be ONE number x to give a composite number p(x),
and the proposition would be false.
Mathematical Proof
But if the proposition is true, I want
1. a way to convince myself,
2. a way to convince a skeptic.
We can expect an argument.
Mathematical Proof
But if the proposition is true, I want
1. a way to convince myself,
2. a way to convince a skeptic.
We can expect an argument.
Mathematical Proof
proof
“An argument is a connected series of statements to establish a definite proposition.”
A mathematical proof is a sequence of statements in which
each statement
• is self-evident to mathematicians, or
• follows from earlier statements by logic with which mathematicians agree.
and
the last statement is the proposition you want to establish.
Mathematical Proof
A mathematical proof is a sequence of statements in which
A well-written
mathematical proof also has an introduction, guiding comments,
each statement
and a
to help
the reader.
• conclusion
is self-evident
to mathematicians,
or
• follows from earlier statements by logic with which mathematicians agree.
To and
see what this means, let me show you two proofs…
the last statement is the proposition you want to establish.
Mathematical Proof
Proof #1: Not well-written.
1.
2.
3.
4.
Hypothesis: A = B
A+ C=A+C
A+C=B+C
If A = B, then A + C = B + C
Mathematical Proof
Proof #2: Better writing.
I will prove that if A = B, then A + C = B + C.
To do this, I will show that if I assume A = B, I can prove that A + C = B + C.
So…
1. A = B
(my hypothesis)
2. A + C = A + C
(reflexive property of equality)
3. A + C = B + C
(replacement property of equality, used on statement 2)
Now I have proven that if I assume A = B, I can prove that A + C = B + C.
Therefore I have proven that
4. If A = B, then A + C = B + C
This concludes the proof.
Mathematical Proof
If you find it easy to follow the proof, the “helpful” parts of the writing may be
unnecessary for you, even distracting.
But when the proof is challenging for you to understand, it helps to know:
1) The goal of the proof,
2) The logical “flow” of the proof, and
3) The reasons that you should agree with the more difficult statements in the
proof.
This is the reason for the “style” of a well-written proof, and this is the reason that
you are learning it.
Mathematical Proof
A more important proof for section 12.4.
I want to prove that this equation is true for every counting number n:
n(n  1)
i

2
i 1
n
To do this, I will use the method of mathematical induction.
First I will prove that the equation is true when n = 1.
1
Left-hand side:
i
i 1
1
Right-hand side:
1(1  1)
2
1
The two sides are equal. The equation is true when n = 1.
Now I will show that for every counting number k, if the equation is true when n = k,
it must also be true when n = k + 1.
To do this, I will show that if I assume that the equation is true for n = k, I can prove
that the equation is also true for n = k + 1.
Mathematical Proof
A more important proof for section 12.4.
I want to prove that this equation is true for every counting number n:
n(n  1)
i

2
i 1
k (k  1)
Inductive hypothesis
1  2  3  4  ...  k 
2
k (k  1)
k (k  1)
Reflexive property of equality
 (k  1) 
 (k  1)
2
2
k (k  1)
1  2  3  4  ...  k  (k  1) 
 (k  1) Replacement of equals
2
k 1
k (k  1) 2(k  1)
k 1
i


(k  1)(k  2)

i
2
2
i 1

2
i 1
2
k 1
k  3k  2
So the equation is true for n = k + 1.
i


2
i 1
n
Mathematical Proof
A more important proof for section 12.4.
I want to prove that this equation is true for every counting number n:
n(n  1)
i

2
i 1
n
I have proven that
• the equation is true for n = 1, and
• for every counting number k, if the equation is true when n = k,
it must also be true when n = k + 1.
Therefore the equation must be true for every counting number n.
QED.
Mathematical Induction
Parts of an induction proof:
1. Introduction (“I will prove by induction that P is true for every counting number n”)
2. Proof of P when n = 1 Textbook calls this “Condition I.”
3. Proof that whenever P is true for n = k, P must also be true for n = k + 1.
Textbook calls this “Condition II.”
A. The inductive hypothesis (“assume P is true for n = k“)
B. From the inductive hypothesis, prove that P must be true for n = k + 1.
4. Conclusion (“…therefore P is true for every counting number n.”)
Technical Challenges:
1. Writing P when n = 1.
2. Writing P when n = k.
3. Writing P when n = k + 1.
4. Proving the case for n = k + 1.