Proof Techniques

Introduction

Proof techniques: essential tools to verify propositions and theorems in discrete mathematics. Each technique tailored to specific problem structures. Mastery ensures rigorous validation of logical statements and fosters deeper conceptual understanding.

"Proofs are the essence of mathematics, the means by which we ascertain truth beyond doubt." -- Paul Halmos

Direct Proof

Definition

Establish truth of implication "If P then Q" by assuming P and logically deducing Q. Linear, constructive method.

Mechanism

Start with known axioms, definitions, or previously proven results. Apply logical deductions to reach conclusion Q.

Example

Prove: If n is even, then n² is even.

Assume n = 2k, k ∈ ℤ.Then n² = (2k)² = 4k² = 2(2k²).Hence n² is even.

Advantages

Straightforward, intuitive, constructive proof. Preferred when direct reasoning is clear.

Limitations

Not always applicable if conclusion is indirect or complex. May require alternative techniques.

Proof by Contrapositive

Definition

Prove "If P then Q" by proving the logically equivalent "If not Q then not P".

Logical Basis

Equivalence: P → Q ≡ ¬Q → ¬P. Often simpler to prove contrapositive.

Example

Prove: If n² is even, then n is even.

Contrapositive: If n is odd, then n² is odd.Assume n = 2k + 1.Then n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, odd.Hence original statement true.

Advantages

Facilitates proofs where direct approach is complicated. Logical equivalence preserves truth.

Limitations

May be unintuitive. Requires understanding of negations and logical equivalences.

Proof by Contradiction

Definition

Assume the negation of the statement to be proved. Derive a contradiction, thereby proving the original statement.

Logical Basis

Law of excluded middle: A statement is either true or false. Contradiction implies assumption false.

Example

Prove: √2 is irrational.

Assume √2 = p/q, p,q ∈ ℤ, gcd(p,q)=1.Then 2 = p² / q² ⇒ p² = 2q².Hence p² even ⇒ p even.Let p = 2k.Substitute: (2k)² = 2q² ⇒ 4k² = 2q² ⇒ q² = 2k² ⇒ q even.Both p,q even contradict gcd(p,q)=1.Hence √2 irrational.

Advantages

Powerful for proving impossibility or existence indirectly. Applies broadly.

Limitations

Non-constructive: proves existence without explicit example. May be less intuitive.

Mathematical Induction

Definition

Prove property P(n) holds for all integers n ≥ base case by two steps: base case and inductive step.

Structure

Base case: Prove P(n₀).
Inductive step: Assume P(k), prove P(k+1).

Example

Prove: 1 + 2 + ... + n = n(n+1)/2 for n ≥ 1.

Base case n=1: 1 = 1(2)/2 = 1 true.Inductive hypothesis: Assume true for k.Sum to k = k(k+1)/2.For k+1:Sum = k(k+1)/2 + (k+1) = (k(k+1) + 2(k+1)) / 2 = (k+1)(k+2)/2.Hence true for k+1.

Advantages

Systematic, proves infinite sequences. Fundamental in discrete math.

Limitations

Requires well-ordered domain (usually ℕ). Fails if base case or step flawed.

Strong Induction

Definition

Inductive step assumes P(i) true for all i ≤ k, then proves P(k+1).

Difference from Weak Induction

Uses broader hypothesis in inductive step. Useful when each case depends on multiple predecessors.

Example

Prove every integer >1 is product of primes.

Base case: 2 prime.Inductive hypothesis: Assume true for all 2 ≤ i ≤ k.For k+1:If prime, done.If composite, k+1 = a·b, 2 ≤ a,b ≤ k.By hypothesis, a,b product of primes.Hence k+1 product of primes.

Advantages

Effective for sequences with interdependent cases or recursive definitions.

Limitations

More complex assumptions. Requires care in establishing base cases.

Case Analysis

Definition

Divide problem into mutually exclusive cases. Prove statement true in each case.

Mechanism

Identify exhaustive cases covering all possibilities. Handle each scenario logically.

Example

Prove: For integer n, n² ≡ 0 or 1 (mod 4).

Cases:n ≡ 0 (mod 2) ⇒ n=2k ⇒ n²=4k² ≡ 0 (mod 4).n ≡ 1 (mod 2) ⇒ n=2k+1 ⇒ n²=4k²+4k+1 ≡ 1 (mod 4).Hence result.

Advantages

Useful when problem naturally splits into distinct scenarios. Ensures coverage.

Limitations

May become unwieldy with many cases. Requires cases to be mutually exclusive and exhaustive.

Combinatorial Proofs

Definition

Prove identities or inequalities by counting interpretations. Equate two counting methods.

Mechanism

Translate algebraic expression into counting problem. Present bijection or double counting argument.

Example

Prove: C(n, k) = C(n, n-k).

Count k-subsets of n-set.Choosing k elements = choosing which n-k elements to exclude.Hence equal counts.

Advantages

Intuitive, constructive proofs. Bridges algebra and combinatorics.

Limitations

Requires combinatorial insight. Not always applicable to all identities.

Pigeonhole Principle

Definition

If n items placed into m containers, and n>m, then at least one container holds ≥2 items.

Generalized Form

At least one container has at least ⎡n/m⎤ items.

Example

Prove: In any group of 13 people, at least two born in the same month.

Months = 12.People = 13.13 > 12 ⇒ by pigeonhole, ≥2 share birth month.

Applications

Existence proofs, combinatorics, number theory, problem-solving.

Limitations

Non-constructive. Does not identify which container.

Proof by Construction

Definition

Prove existence by explicitly constructing an example satisfying conditions.

Mechanism

Provide algorithm, formula, or object demonstrating statement.

Example

Prove: There exists an even prime number.

Construct example: 2 is prime and even.Hence existence proven.

Advantages

Explicit, constructive, intuitive. Confirms existence decisively.

Limitations

Not always possible to construct example easily. Sometimes existence known but construction difficult.

Common Mistakes

Invalid Assumptions

Assuming what is to be proved (circular reasoning).

Faulty Logic

Incorrect use of logical equivalences or implications.

Incomplete Cases

Failing to cover all cases in case analysis.

Neglecting Base Case

Omitting or incorrectly proving base case in induction.

Ambiguous Definitions

Using undefined or vague terms leading to confusion.

References

• Rosen, K. H., Discrete Mathematics and Its Applications, 7th ed., McGraw-Hill, 2012, pp. 45-120.
• Enderton, H. B., A Mathematical Introduction to Logic, 2nd ed., Academic Press, 2001, pp. 30-85.
• Rudin, W., Principles of Mathematical Analysis, 3rd ed., McGraw-Hill, 1976, pp. 5-25.
• Graham, R. L., Knuth, D. E., Patashnik, O., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994, pp. 89-140.
• Velleman, D. J., How to Prove It: A Structured Approach, 2nd ed., Cambridge University Press, 2006, pp. 1-60.