Math 1510 – Proof Techniques & Introductory Examples (Wk 2, p1)
Introduction & Context
Course: Math 1510 – Proofs & Discrete Mathematics
Session goal: transition from symbolic logic to proof techniques, emphasizing a rigorous approach to mathematical statements.
Classroom logistics briefly mentioned (projectors, slides) ➜ informational, not mathematically relevant.
Review of Quantifiers & Their Negations
A proposition depending on (x) (e.g. ) is a statement whose truth value varies based on the specific element from the domain assigned to (x). It can be true or false for different domain elements.
The specified domain of discourse is crucial:
If domain = (all real numbers), then is true, while is false.
If domain = (the closed interval from -1 to 0), the statement (there exists an x such that P(x) is true) is false, because no number in this domain satisfies . The statement (for all x, P(x) is true) would also be false.
Negation rules (De Morgan‐style for quantifiers): These rules show how to logically negate statements involving quantifiers.
. This means "It is not the case that there exists an x for which P(x) is true" is logically equivalent to "For all x, P(x) is false."
. This means "It is not the case that for all x, P(x) is true" is logically equivalent to "There exists at least one x for which P(x) is false."
Set‐theoretic picture teased: This provides a visual intuition for quantifiers.
Let set be the subset of elements in the domain for which the proposition is true.
The statement is true if and only if the set is equal to the entire domain ().
The statement is true if and only if the set is not empty ().
Proofs vs Calculations
Proof = an essay-like logical argument that demonstrates the truth of a mathematical statement based on definitions, axioms, and previously established theorems. It is not simply a rote computation or finding a numerical answer.
Must be: logically consistent, detailed enough for any reasonably knowledgeable reader to meticulously rebuild your line of reasoning step-by-step.
Use only previously established facts, definitions, rules, or axioms; there is no need to re-derive fundamental arithmetic like . The foundation of a proof rests on what is already known and accepted.
Creative process – there is no guaranteed algorithm or single formula for constructing a proof, unlike applying derivative rules. It often requires insight and strategic thinking.
Catalogue of Proof Methods Introduced
Direct proof: Directly showing that the conclusion follows from the premises.
Mathematical induction (standard & strong): Proving statements about natural numbers.
Proof by contradiction: Assuming the negation of what you want to prove and deriving an impossibility.
Pigeonhole principle: A combinatorial principle stating that if you have more items than categories, at least one category must contain more than one item.
Double counting & other combinatorial tricks: Counting the same set of objects in two different ways to show that two expressions are equal.
Mathematical Induction (Standard)
Domino metaphor: Imagine an infinite line of dominoes, , where represents the statement you want to prove for a given integer (n).
Two steps are required to show that all dominoes fall (i.e., that the statement is true for all natural numbers):
Base case: Prove that is true (the first domino falls). This establishes a starting point for the induction.
Inductive step: Prove that for any arbitrary natural number (k), if is true (the k-th domino falls), then must also be true (the (k+1)-th domino will fall). This establishes the chain reaction.
Then, by the principle of mathematical induction, you can conclude that is true. This method is typically used for statements involving properties of integers, such as sums of series, inequalities, divisibility rules, or properties of sequences and graphs that depend on an integer parameter (n).
Typical domains: formulas depending on an integer parameter (n) (e.g. sequences, sums, graph properties, divisibility statements, inequalities).
Σ-notation refresher
Summation notation: .
The variable (i) is the index of summation.
(a) is the lower limit of summation, and (b) is the upper limit.
is the expression being summed, evaluated at each integer from (a) to (b).
Examples:
. This sums the first 5 natural numbers.
. This sums the squares of the first 5 natural numbers.
Half-integer example: . This sum has (11) terms, starting from up to . Note that the index (i) still increments by 1.
Classic Induction Example – Sum 1+2+…+n
Claim: The sum of the first (n) natural numbers is given by the formula
Base case: For , the sum is just 1. The formula gives . Since , the base case holds. ✓
Inductive step: Assume the formula is true for some arbitrary integer . That is, assume (this is the inductive hypothesis, ). We need to prove that it follows that the formula is true for (). So, we consider the sum up to : . By the inductive hypothesis (), we replace the sum with its assumed formula: Now, we algebraically manipulate this expression to match the formula for . Factor out : . This matches the formula with replaced by . Thus, is proven.
Conclusion: By the principle of mathematical induction, the claim is true for all natural numbers .
Geometric link: This formula has a visual interpretation. The area under the line on the interval [0,1], approximated using Riemann sums with unit width rectangles, can be seen to relate to this sum. More broadly, arranging the numbers in a triangular pattern leads to a rectangle of size , whose area is double the sum.
Other Induction Claims Mentioned
: The factorial of (n) (product of integers from 1 to n) is strictly less than raised to the power of . This can be proven by comparing terms term-wise, for each factor in .
divisible by 4: This statement asserts that for all natural numbers (n), is a multiple of 4. Proving this typically relies on for some integer (m) in the inductive hypothesis.
Fibonacci recurrence : The Fibonacci sequence is defined by its first two terms and a recurrence relation. The identity states that the sum of the first Fibonacci numbers (from to ) equals the -th Fibonacci number minus 1.
Strong Induction
Hypothesis assumes all previous statements: Instead of just assuming to prove , strong induction's hypothesis assumes that all statements are true (). This is a stronger assumption.
Equivalent power, sometimes easier: Strong induction is logically equivalent to standard induction (any proof using one can be converted to the other), but sometimes the proof for naturally depends on earlier cases (e.g., , ) making strong induction conceptually simpler or more direct to apply.
Strong Induction Example – Sequence
Definition: This sequence is defined recursively.
,
: This recurrence relation means the value of depends on an earlier term calculated from the floor of . The floor function gives the greatest integer less than or equal to (x).
Claim: : We want to prove this inequality for all .
Proof outline:
Base cases: When using strong induction, sometimes multiple base cases are needed if the recurrence relation refers to values that would fall outside the standard base case. In this specific claim, the claim starts at . Let's check . We have implicitly defined by . For , the claim is , which is . This is true. ✓
Inductive step: Assume that holds for all integers such that , for some . This is our strong inductive hypothesis. We need to show that .
Let's compute . By definition, . Let . Since , , so . Also, for . Specifically, if , ; if , ; if , . In all cases, . Therefore, we can apply our inductive hypothesis to , so . Substituting this back: Using the hypothesis on the floor index ():
Next, use the property of the floor function: . So, .
.
This shows that , which is exactly what we needed to prove for the inductive step.
Hence, by strong induction, the inequality holds for all .
Proof by Contradiction
Strategy: To prove a statement , you assume its negation is true, and then logically derive a contradiction (a statement that is always false, denoted by ). Since your assumption led to a falsehood, the assumption itself must be false, meaning must be true.
Logical equivalence: The statement (If P then Q) is logically equivalent to (If P is true and Q is false, then a contradiction arises). This equivalence forms the basis for this proof technique, as assuming within the context of and finding a contradiction means must be true if is.
Examples
Factor below for composites: If an integer is composite, it can be written as for integers . The proof by contradiction goes: Assume, for the sake of contradiction, that both factors and are greater than . So, and . Multiplying these inequalities, we get which simplifies to . This is a contradiction ( cannot be strictly greater than itself). Therefore, our initial assumption must be false, meaning at least one of the factors ( or ) must be less than or equal to . This is a crucial result for optimizing primality tests.
Infinitely many primes (Euclid): This classic proof is by contradiction.
Suppose, for a contradiction, that there are only finitely many prime numbers. Let these be (a complete list of all primes).
Consider the number . This number is formed by multiplying all prime numbers on our supposed finite list and adding 1.
By the Fundamental Theorem of Arithmetic, any integer greater than 1 must have at least one prime divisor. So, must have a prime divisor, let's call it .
This prime divisor must be one of the primes on our list (), because we assumed our list contains all primes. Therefore, divides .
If divides and divides , then must also divide their difference: .
So, divides 1. The only positive integer that divides 1 is 1 itself. But 1 is not a prime number. This is a contradiction, as was defined as a prime divisor.
Thus, our initial assumption that there are finitely many primes must be false. Therefore, there are infinitely many prime numbers.
Irrationality of (two proofs):
a. Co-prime fraction method leads to even/odd parity clash: Assume, for contradiction, that is rational. This means for some integers and where and the fraction is in its lowest terms (i.e., and share no common factors other than 1; they are coprime).
Squaring both sides gives , so . This implies is an even number. If is even, then must also be even (because an odd number squared is always odd).
Since is even, we can write for some integer . Substituting this into gives . Dividing by 2, we get . This implies is an even number. If is even, then must also be even.
So, we have deduced that both and are even. This means they both have a common factor of 2. But we initially assumed that and are coprime (have no common factors other than 1). This is a contradiction. Therefore, our initial assumption that is rational must be false. Hence, is irrational.b. Minimal denominator method produces smaller denominator, contradicting minimality: This less common proof assumes where are positive integers and is the smallest possible positive denominator for which can be expressed as a fraction. From , we know must be even. Let . Then . This implies must also be even. So, . Then . Here, . Since is a positive integer, is also a positive integer and . This contradicts our initial assumption that was the smallest possible positive denominator. Therefore, must be irrational.
Pigeonhole Principle (PHP)
Formal Statement: If objects are placed into boxes (or categories or containers), and , then at least one box must contain two or more objects. This is a powerful, yet simple, combinatorial principle.
Simple corollaries:
If you have 13 people, and each person has a birth-month, then by PHP, at least two people must share the same birth-month (13 objects, 12 possible boxes/months; ).
In any group of two or more people, at least two individuals must have the same number of friends within that group (sketched via PHP): Let (N) be the number of people. The number of friends a person can have ranges from 0 to . However, if someone has 0 friends, no one can have friends (as that person would be friends with everyone else). So, the possible number of friends are either or . In both cases, there are possible values for the number of friends. Since there are (N) people (objects) and at most possible friend counts (boxes), at least two people must fall into the same box, meaning they have the same number of friends.
Double Counting Technique
Count a quantity in two independent ways, ensuring both methods enumerate the same set of items or relationships. Since both methods count the same quantity, their results must be equal, leading to a mathematical identity.
Re-derivation of :
Let .
Write the sum forward:
Write the sum backward:
Add the two equations vertically, term-by-term:
Each pair sums to . There are (n) such pairs.Divide by 2 to find S: .
This simple example beautifully illustrates how counting the same sum in two different orders leads to a formula.
Graph Theory Preview & Contrapositive Use
Graph: A mathematical structure consisting of a set of vertices (or nodes) and a set of edges (or links) connecting pairs of vertices. Graphs are used to model relationships or connections between discrete objects.
Degree of a vertex: The number of edges incident to (connected to) that vertex.
Cycle: A closed walk (a sequence of vertices and edges that starts and ends at the same vertex) in which no vertex (other than the start/end vertex) and no edge is repeated. A cycle indicates a closed loop in the graph.
Bipartite graph: A graph whose vertices can be divided into two disjoint and independent sets, and , such that every edge connects a vertex in to one in . No edges exist within or within . This means all cycles in a bipartite graph must have even length.
Theorem pair (contrapositives): Two statements that are logically equivalent, where proving one automatically proves the other.
"If a graph has every vertex degree then it has a cycle" (Original statement).
The contrapositive: "If a graph does not have a cycle (i.e., is acyclic), then it must possess at least one vertex of degree 1 (or 0)". Proving the contrapositive can often be simpler. For example, if a graph is acyclic and connected, it must be a tree, and every tree with more than one vertex has leaves (vertices of degree 1).
Illustration that proving the contrapositive can be easier: Sometimes, directly proving "if P then Q" is difficult. But proving "if not Q then not P" can be more straightforward, especially when "not Q" provides a stronger, more constructive starting point.
Bipartite graphs contain no odd-length cycles (sketch: Consider a cycle in a bipartite graph. As you traverse the cycle, you must alternate between vertices in set and vertices in set . To return to the starting vertex, you must have taken an even number of steps, as each step moves you from one partition to the other and back. Therefore, any cycle length must be even). This property is a fundamental characteristic of bipartite graphs.
Common Logical & Proof Pitfalls
Empirical verification (many cases) proof for all: Testing a statement on many examples, even a million, does not constitute a proof that it holds for all cases. A proof requires a universal argument, not just specific instances.
Confusing statement with its converse: For a statement "If P then Q" (), its converse is "If Q then P" (). These are not logically equivalent. For example, "If it is raining, then the ground is wet" is true. Its converse, "If the ground is wet, then it is raining," is false (e.g., could be dew).
Post hoc fallacy: Short for "post hoc ergo propter hoc" (after this, therefore because of this). This is a logical fallacy where one assumes that because event B happened after event A, then A must have caused B. Correlation or sequence of events does not necessarily imply causation.
Assuming existence of an object not shown to exist: For instance, saying "Let be an integer such that " without first proving such an exists (it doesn't in natural numbers). You must establish the existence of any mathematical object you intend to use in a proof.
Reusing same symbol for distinct objects: Using the same variable name (e.g., ) to represent two different values or concepts within the same scope of a proof leads to ambiguity and logical errors.
Example fallacy: start with false premise (1=0), manipulate algebraically to reach true statement does not validate original premise: If you start a logical argument with a false premise, you can logically deduce any conclusion, including true ones, valid ones, or contradictions. The apparent validity of the deduction does not validate the original false premise. The conclusion is merely consistent with the false premise, but the entire argument is unsound.
Miscellaneous Numerical / Symbolic Facts Referenced
Factorial definition: . For . By definition, . Factorials represent the number of ways to arrange (n) distinct items.
Power notation: . Represents (n) multiplied by itself (n) times. (e.g., ).
Floor function: = the largest integer less than or equal to .
e.g.
The floor function effectively truncates the decimal part of a positive number downwards.
Study Tips for Writing Proofs
Write in full sentences interleaved with mathematical expressions; the reader should be able to follow your argument like a narrative. Use clear prose to connect mathematical ideas and steps.
Justify every non-obvious step with precise references to prior definitions, axioms, established theorems, or basic algebraic rules. Do not skip steps that a reader might question.
Clearly separate assumptions from deductions. Use phrases like "Assume P is true," "By definition of X," "It follows from Theorem Y that…" to guide the reader through your logical flow.
Label variables carefully; avoid overloading symbols by using the same letter for different quantities or concepts within the same part of a proof. Introduce new variables explicitly when needed.
When stuck, consider alternate but equivalent statements (e.g., proving the contrapositive instead of the direct statement), or try a different proof method (e.g., standard induction vs. strong induction vs. contradiction). Sometimes approaching a problem from a different angle reveals a path forward.
Administrative Reminders (from lecture)
Workshops begin this week (check timetable).
Lecture recordings available via Panopto on Canvas.
Recommended text (optional): Proofs & Fundamentals by Johnston & Bao (title mentioned for supplementary reading).