Proof Techniques: Direct, Contrapositive, Contradiction, Induction & Cases

TAKEAWAYS:

• Direct proofs start with premises and apply logical rules to reach the conclusion, ideal for "if P then Q" statements.
• Contrapositive proofs rewrite "if P then Q" as "if not Q then not P" and are often easier to prove.
• Proof by contradiction assumes the opposite of the statement and derives a contradiction, useful for uniqueness proofs.
• Mathematical induction proves statements for all natural numbers by showing a base case and an inductive step.
• Proof by cases breaks a statement into exhaustive, mutually exclusive scenarios and proves each separately.
• Real-world tie-ins include WhatsApp’s end-to-end encryption (proofs of security protocols), Ncell’s billing algorithms (induction for recursive fee calculations), and NEPSE’s stock price validation (contradiction for fraud detection).

1. Introduction to Proof Techniques

Proof techniques are the backbone of mathematics and computer science. They allow us to verify the correctness of algorithms, validate logical statements, and ensure the reliability of systems. In this unit, we focus on five key methods:

1. Direct Proof
2. Proof by Contrapositive
3. Proof by Contradiction
4. Mathematical Induction
5. Proof by Cases

Each method has its strengths and is suited to specific types of problems. Let’s explore them one by one.

2. Direct Proof

Definition

A direct proof starts with the given premises (assumptions) and uses logical deductions, definitions, and previously established theorems to arrive at the conclusion. It follows the structure:

Given: Premise $P$ To Prove: Conclusion $Q$ Proof: If $P$ is true, then by [logical steps], $Q$ must also be true.

How It Works

1. Assume the hypothesis $P$ is true.
2. Apply definitions, axioms, or known theorems to derive intermediate statements.
3. Conclude with $Q$.

Worked Example: Even + Even = Even

Statement: If $a$ and $b$ are even integers, then $a+b$ is even. Proof:

1. Let $a=2k$ and $b=2m$ for some integers $k,m$ (definition of even).
2. Then, $a+b=2k+2m=2(k+m)$.
3. Since $k+m$ is an integer, $a+b$ is even by definition.

Visual: Direct Proof Flow

flowchart TD
    A["Given: P is true"] --> B["Apply definitions/theorems"]
    B --> C["Derive intermediate statements"]
    C --> D["Conclude Q is true"]

When to Use

• When the statement is of the form "If $P$, then $Q$."
• When definitions or algebraic manipulations directly lead to the conclusion.

Real-World Example: WhatsApp Encryption

WhatsApp uses Signal Protocol for end-to-end encryption. The correctness of its key exchange relies on direct proofs to show that:

If Alice and Bob follow the protocol correctly, then an eavesdropper cannot decrypt their messages. This is proven by assuming the protocol steps (premises) and showing that the final ciphertext is secure (conclusion).

3. Proof by Contrapositive

Definition

The contrapositive of a statement "If $P$, then $Q$" is "If not $Q$, then not $P$." These two statements are logically equivalent. A proof by contrapositive assumes the negation of the conclusion and shows that it leads to the negation of the hypothesis.

Why Use It?

Sometimes, proving the contrapositive is easier than proving the original statement directly.

Worked Example: Rational Numbers

Statement: If $x^2$ is irrational, then $x$ is irrational. Contrapositive: If $x$ is rational, then $x^2$ is rational. Proof:

1. Assume $x$ is rational, so $x=\frac{p}{q}$ where $p,q$ are integers with no common factors.
2. Then, $x^2=\frac{p^2}{q^2}$, which is rational by definition.

Visual: Contrapositive Logic

flowchart TD
    A["Original: If P, then Q"] -->|"Logically Equivalent"| B["Contrapositive: If not Q, then not P"]
    B --> C["Easier to prove in some cases"]

Real-World Example: Ncell Billing System

Ncell’s billing system uses recursive algorithms to calculate charges. To prove that:

If a customer’s usage exceeds the threshold, then they are charged extra, the contrapositive is: If a customer is not charged extra, then their usage did not exceed the threshold. This is easier to verify in code by checking the billing logic’s conditions.

4. Proof by Contradiction

Definition

In a proof by contradiction, we assume the opposite of what we want to prove and show that this assumption leads to a contradiction (a statement that is always false, like $1=0$). If the assumption leads to a contradiction, it must be false, and the original statement must be true.

Structure

1. Assume $\neg Q$ (the negation of the conclusion).
2. Show that this leads to a contradiction (e.g., $1=0$ or $P\wedge \neg P$).
3. Conclude that $Q$ must be true.

Worked Example: Square Root of 2 is Irrational

Statement: $\sqrt{2}$ is irrational. Proof:

1. Assume $\sqrt{2}$ is rational, so $\sqrt{2}=\frac{p}{q}$ where $p,q$ are coprime integers.
2. Then, $2=\frac{p^2}{q^2}$, so $p^2=2q^2$.
3. $p^2$ is even, so $p$ is even. Let $p=2k$.
4. Substituting: $(2k{)}^2=2q^2$ → $4k^2=2q^2$ → $q^2=2k^2$.
5. $q^2$ is even, so $q$ is even.
6. But $p$ and $q$ are both even, contradicting the assumption that they are coprime.
7. Thus, $\sqrt{2}$ is irrational.

Visual: Contradiction Proof Steps

flowchart TD
    A["Assume ¬Q"] --> B["Derive intermediate statements"]
    B --> C["Reach contradiction (e.g., P ∧ ¬P)"]
    C --> D["Conclude Q must be true"]

Real-World Example: NEPSE Fraud Detection

NEPSE (Nepal Stock Exchange) uses contradiction proofs to detect fraudulent transactions. For example:

If a stock price is reported as $x$, but the proof shows that assuming $x$ is valid leads to a contradiction (e.g., violating market rules), then $x$ must be invalid. This ensures only valid trades are recorded.

5. Mathematical Induction

Definition

Mathematical induction is used to prove statements about all natural numbers (or recursively defined structures). It consists of two steps:

1. Base Case: Prove the statement is true for the initial value (usually $n=0$ or $n=1$).
2. Inductive Step: Assume the statement holds for some arbitrary $n=k$ (inductive hypothesis), and then prove it holds for $n=k+1$.

If both steps are satisfied, the statement is true for all natural numbers.

Structure

1. Base Case: Show $P(0)$ is true (or $P(1)$).
2. Inductive Hypothesis: Assume $P(k)$ is true for some $k\ge 0$.
3. Inductive Step: Prove $P(k+1)$ is true using $P(k)$.

Worked Example: Sum of First $n$ Natural Numbers

Statement: $1+2+\cdots +n=\frac{n(n+1)}{2}$ for all $n\ge 1$. Proof:

1. Base Case ($n=1$): LHS = 1, RHS = $\frac{1\cdot 2}{2}=1$. True.
2. Inductive Step: Assume $1+2+\cdots +k=\frac{k(k+1)}{2}$ (inductive hypothesis). Then, $1+2+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}$. This matches the formula for $n=k+1$.

Visual: Induction Process

flowchart TD
    A["Base Case: Prove P(0)"] --> B["Inductive Hypothesis: Assume P(k) is true"]
    B --> C["Inductive Step: Prove P(k+1) using P(k)"]
    C --> D["Conclusion: P(n) is true for all n"]

Real-World Example: Daraz Order Processing

Daraz uses recursive algorithms to process orders. The total cost of an order with $n$ items can be proven using induction:

1. Base Case: 1 item → cost is straightforward.
2. Inductive Step: Assume the cost formula works for $k$ items. For $k+1$ items, add the new item’s cost to the previous total. This ensures the billing system works correctly for any number of items.

6. Proof by Cases

Definition

A proof by cases divides the problem into exhaustive and mutually exclusive scenarios and proves the statement for each case separately. It is useful when the statement behaves differently under different conditions.

Structure

1. Identify all possible cases (e.g., $x>0$, $x=0$, $x<0$).
2. Prove the statement for each case individually.

Worked Example: Absolute Value Definition

Statement: For any real number $x$, $|x|=x$ if $x\ge 0$, and $|x|=-x$ if $x<0$. Proof:

1. Case 1: $x\ge 0$. By definition, $|x|=x$.
2. Case 2: $x<0$. By definition, $|x|=-x$. Since these cases cover all real numbers, the statement is proven.

Visual: Proof by Cases

flowchart TD
    A["Identify all cases"] --> B["Case 1: Prove P"]
    A --> C["Case 2: Prove P"]
    A --> D["Case n: Prove P"]
    B --> E["Conclusion: P holds in all cases"]
    C --> E
    D --> E

Real-World Example: Kathmandu Traffic Light Control

Traffic lights in Kathmandu use proof by cases to manage vehicle flow:

1. Case 1: If the sensor detects a vehicle at a red light, the light turns green.
2. Case 2: If no vehicle is detected, the light remains red.
3. Case 3: If a pedestrian presses the button, the light changes after a delay. Each case is programmed separately to ensure smooth traffic flow.

Comparison Table: Proof Techniques

7. Common Mistakes and Pitfalls

1. Skipping the Base Case in Induction: Forgetting to verify the base case invalidates the entire proof. Always check $n=0$ or $n=1$.

2. Assuming What You Need to Prove: In induction, do not use the conclusion $P(k+1)$ to prove $P(k+1)$. Only the inductive hypothesis $P(k)$ is allowed.

3. Non-Exhaustive Cases: In proof by cases, ensure all possible scenarios are covered. Missing a case means the proof is incomplete.

4. Logical Fallacies in Direct Proofs: Avoid circular reasoning (e.g., proving $P$ by assuming $P$).

8. Step-by-Step Proof Template

Use this template to structure your proofs in exams:

For Direct/Contrapositive Proofs:

1. State the given: Clearly write the hypothesis $P$.
2. State the goal: Clearly write the conclusion $Q$.
3. Apply definitions: Rewrite $P$ using definitions or algebraic manipulations.
4. Derive $Q$: Show how the steps lead to $Q$.
5. Conclude: Write "Therefore, $Q$ is true."

For Proof by Contradiction:

1. Assume the opposite: Write "Assume $\neg Q$."
2. Derive consequences: Show how this leads to a contradiction.
3. Conclude: Write "This is a contradiction, so $Q$ must be true."

For Mathematical Induction:

1. Base Case: Prove for $n=0$ or $n=1$.
2. Inductive Hypothesis: Assume $P(k)$ is true.
3. Inductive Step: Prove $P(k+1)$ using $P(k)$.
4. Conclusion: State that by induction, $P(n)$ is true for all $n$.

9. In the Real World

Discrete mathematics and proof techniques are everywhere in technology and everyday life. Here’s how they apply to products and systems students interact with:

1. WhatsApp End-to-End Encryption (Contrapositive & Contradiction)

• Idea Used: Proof by contradiction ensures security.
• How:
  • WhatsApp’s Signal Protocol uses ephemeral keys and double ratchet algorithms.
  • To prove security, WhatsApp’s team assumes an attacker can decrypt messages (contradiction assumption) and shows this leads to breaking mathematical assumptions (e.g., the hardness of the Diffie-Hellman problem).
  • Since no known method exists to break these assumptions, the original statement ("messages are secure") holds.

2. Ncell Billing System (Mathematical Induction)

• Idea Used: Recursive fee calculation.
• How:
  • Ncell’s billing system calculates charges for calls, SMS, and data using recursive functions.
  • Example: If a call costs Rs. $x$ for the first minute and Rs. $y$ for each additional minute, the total cost for $n$ minutes can be proven using induction:
    1. Base Case: 1 minute costs $x$.
    2. Inductive Step: Assume $n=k$ minutes cost $x+(k-1)y$. Then for $n=k+1$, the cost is $x+ky$.
  • This ensures the billing algorithm works for any call duration.

3. Daraz Order Processing (Proof by Cases)

• Idea Used: Handling different order scenarios.
• How:
  • Daraz’s checkout system processes orders based on:
    1. Case 1: Single item → apply discount if eligible.
    2. Case 2: Multiple items → calculate subtotal, tax, and shipping separately.
    3. Case 3: Bulk order → apply volume discount.
  • Each case is programmed separately to ensure correct pricing.

4. NEPSE Stock Validation (Contradiction)

• Idea Used: Fraud detection.
• How:
  • NEPSE uses contradiction to validate stock prices. For example:
    • Statement: A reported price $p$ is valid only if it satisfies market rules.
    • Proof: Assume $p$ is valid but violates a rule (e.g., exceeds daily limit). This leads to a contradiction with the exchange’s policies, so $p$ must be invalid.
  • This ensures only legitimate trades are recorded.

5. Kathmandu Traffic Light System (Proof by Cases)

• Idea Used: Managing traffic scenarios.
• How:
  • Traffic lights at busy intersections use proof by cases:
    1. Case 1: Vehicle detected → turn green.
    2. Case 2: Pedestrian button pressed → delay and turn red for vehicles.
    3. Case 3: No activity → keep lights as is.
  • Each case is handled by sensors and timers to optimize flow.

6. Bank Loan Interest Calculation (Mathematical Induction)

• Idea Used: Recursive interest computation.
• How:
  • Banks calculate compound interest using the formula: $A=P{\left(1+\frac{r}{n}\right)}^{nt}$.
  • To verify this for $n$ compounding periods, induction is used:
    1. Base Case: 1 period → $A=P(1+r)$.
    2. Inductive Step: Assume it holds for $k$ periods, then prove for $k+1$.

10. Exam Tip

What Examiners Look For

1. Clarity: Clearly state what you are proving and why.
2. Structure: Follow the logical flow of the proof technique.
3. Rigor: Every step must be justified (e.g., "by definition," "by algebraic manipulation").
4. Completeness:
   • For induction, show both base case and inductive step.
   • For cases, cover all scenarios.
5. Avoid Assumptions: Do not assume what you need to prove (e.g., in induction, do not use $P(k+1)$ to prove $P(k+1)$).

Common Exam Questions and How to Answer

Sample Exam Answer Structure

Question: Prove that the sum of the first $n$ odd numbers is $n^2$ using mathematical induction.

Answer:

1. Base Case ($n=1$): Sum = 1, and $1^2=1$. ✔️
2. Inductive Hypothesis: Assume the sum of the first $k$ odd numbers is $k^2$.
3. Inductive Step: Sum of first $k+1$ odd numbers = $k^2+(2k+1)=(k+1{)}^2$.
4. Conclusion: By induction, the statement holds for all $n\ge 1$.

This note covers all subtopics of Unit 8: Proof Techniques with definitions, examples, real-world ties, and exam strategies. Practice constructing proofs for each method to master the unit!