Proof Techniques & Mathematical Induction: Direct, Indirect, Contradiction, and Recursion

Core Concepts: Proof Techniques

1. Direct Proof

Definition: A proof where we assume the premise (P) is true and use logical deductions to show the conclusion (Q) must also be true. Structure:

1. Assume P is true.
2. Use definitions, axioms, or known theorems to derive Q.
3. Conclude P → Q.

How it works:

flowchart TD
    A["Assume P is true"] --> B["Apply definitions/theorems"]
    B --> C["Derive Q step-by-step"]
    C --> D["Conclude: P → Q"]

Worked Example 1: Prove "If $n$ is odd, then $n^3$ is odd."

• Assumption: $n$ is odd ⇒ $n=2k+1$ for some integer $k$.
• Derivation: $$n^3=(2k+1{)}^3=8k^3+12k^2+6k+1=2(4k^3+6k^2+3k)+1$$ This is of the form $2m+1$ (odd).
• Conclusion: $n^3$ is odd.

Visual:

2. Indirect Proof (Proof by Contrapositive)

Definition: Prove $P\to Q$ by proving its contrapositive $\neg Q\to \neg P$ (logically equivalent). Why? Often easier to disprove $Q$ than prove $P$.

Worked Example 2: Prove "If $n^2$ is even, then $n$ is even."

• Contrapositive: If $n$ is not even (i.e., odd), then $n^2$ is not even.
• Proof:
  • Let $n=2k+1$.
  • $n^2=4k^2+4k+1=2(2k^2+2k)+1$ (odd).
• Conclusion: Contrapositive holds ⇒ original statement is true.

3. Proof by Contradiction

Definition: Assume $P\to Q$ is false (i.e., $P$ is true and $Q$ is false) and show this leads to a contradiction. Structure:

1. Assume $P$ is true and $Q$ is false.
2. Derive an absurdity (e.g., $1=0$).
3. Conclude $Q$ must be true.

Worked Example 3: Prove "√2 is irrational."

• Assumption: Suppose $\sqrt{2}$ is rational ⇒ $\sqrt{2}=\frac{a}{b}$ (lowest terms).
• Derivation: $$2=\frac{a^2}{b^2}\Rightarrow a^2=2b^2\Rightarrow a^2\text{ is even}\Rightarrow a\text{ is even}.$$ Let $a=2k$. Then $4k^2=2b^2\Rightarrow b^2=2k^2\Rightarrow b$ is even. Contradiction: Both $a$ and $b$ are even, but $\frac{a}{b}$ was in lowest terms.
• Conclusion: $\sqrt{2}$ is irrational.

Visual:

4. Proof by Cases

Definition: Break the proof into disjoint cases that cover all possibilities. Example: Prove "For any integer $n$, $n^2+n$ is even."

• Case 1: $n$ is even ⇒ $n=2k$. $$n^2+n=4k^2+2k=2(2k^2+k)\text{ (even)}.$$
• Case 2: $n$ is odd ⇒ $n=2k+1$. $$n^2+n=4k^2+4k+1+2k+1=2(2k^2+3k+1)\text{ (even)}.$$
• Conclusion: True for all integers $n$.

Mathematical Induction

1. Principle of Mathematical Induction

Definition: A method to prove statements for all natural numbers $n$ by:

1. Base Case: Show the statement holds for $n=1$ (or $n=0$).
2. Inductive Step: Assume it holds for $n=k$ (inductive hypothesis), then prove it for $n=k+1$.

Why it works: If the base case holds and each step "builds" on the previous, the statement holds for all $n$.

Visual:

flowchart TD
    A["Base Case: P(1)"] --> B["Assume P(k) is true"]
    B --> C["Prove P(k+1) using P(k)"]
    C --> D["By induction, P(n) is true for all n ≥ 1"]

2. Strong Induction (Course of Values)

Definition: Assume the statement holds for all $i\le k$ to prove $P(k+1)$. Use case: When the inductive step depends on multiple previous values (e.g., Fibonacci sequence).

Worked Example 4: Prove "The Fibonacci sequence $F_n$ satisfies $F_n\le 2^n$ for all $n\ge 1$."

• Base Cases:
  • $F_1=1\le 2^1=2$.
  • $F_2=1\le 2^2=4$.
• Inductive Step: Assume $F_i\le 2^i$ for all $i\le k$. $$F_{k+1}=F_k+F_{k-1}\le 2^k+2^{k-1}=3\cdot 2^{k-1}\le 2^{k+1}.$$
• Conclusion: By strong induction, $F_n\le 2^n$ for all $n$.

3. Induction and Recursive Algorithms

How it’s used: Prove that a recursive algorithm works for all inputs. Example: Prove the sum of first $n$ positive integers is $\frac{n(n+1)}{2}$.

Worked Example 5: Prove $1+2+\cdots +n=\frac{n(n+1)}{2}$ using induction.

• Base Case ($n=1$): $$1=\frac{1(1+1)}{2}=1.\text{✓}$$
• Inductive Step: Assume true for $n=k$: $$1+2+\cdots +k=\frac{k(k+1)}{2}.$$ Prove for $n=k+1$: $$1+2+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}.$$
• Conclusion: By induction, the formula holds for all $n$.

Real-World Tie-In:

• Ncell Billing: Ncell calculates total call charges recursively (each new call adds to the previous total). Induction proves their billing formula works for any number of calls.
• Daraz Order Processing: If Daraz processes orders in a queue, induction can prove the total time for $n$ orders is $O(n)$.

Comparison Table: Proof Techniques

In the Real World

1. Ncell’s Billing System:

   • Idea Used: Mathematical Induction
   • How: Ncell’s total call charge for $n$ calls is calculated recursively. Induction proves their formula $\text{Total}={\sum }_{i=1}^n{\text{charge}}_i$ works for any $n$, ensuring no customer is overcharged.

2. Daraz’s Order Queue:

   • Idea Used: Proof by Cases + Induction
   • How: Daraz processes orders in a queue. Induction proves the total delivery time for $n$ orders is $O(n)$. Proof by cases handles different order types (standard, express, etc.).

3. Bank Loan Interest (Nepal’s NMB/Global IME):

   • Idea Used: Recurrence Relations + Induction
   • How: Loan interest is often calculated using compound interest formulas (e.g., $A=P(1+r{)}^n$). Induction proves these formulas hold for any term $n$, ensuring accurate repayment schedules.

4. WhatsApp Message Delivery:

   • Idea Used: Proof by Contradiction
   • How: WhatsApp’s end-to-end encryption relies on proofs that messages cannot be decrypted without the key. Contradiction proofs show that any attempt to break encryption leads to a logical inconsistency.

Exam Tip

1. Structure is Key:

   • For direct/indirect proofs, always write:
     • "Assume [P] is true."
     • "We need to show [Q]."
     • "By [definition/theorem], [derivation]."
     • "Thus, [Q] holds."
   • For induction, explicitly state:
     • Base case (with calculation).
     • Inductive hypothesis.
     • Inductive step (show how $P(k)$ leads to $P(k+1)$).

2. Common Pitfalls:

   • Forgetting the base case in induction (loses marks even if the step is correct).
   • Assuming what you need to prove in contradiction (circular reasoning).
   • Miscounting cases in proof by cases (e.g., missing $n=0$).

3. Exam Questions to Practice:

   • Prove statements about divisibility (e.g., "If $n$ divides $a$ and $b$, then $n$ divides $a+b$").
   • Use induction to verify recursive formulas (e.g., factorial, Fibonacci).
   • Apply contradiction to prove irrationality or non-existence (e.g., "No integer $n$ satisfies $n^2=2$").

4. Real-World Application Questions:

   • Expect questions like:
     • "A bank calculates loan interest recursively. Use induction to prove their formula is correct for 5 years."
     • "Daraz uses a priority queue for orders. Prove the total processing time for $n$ orders is $O(n\log n)$."
   • Tip: Relate proofs to algorithms (e.g., sorting networks, divide-and-conquer) or financial calculations (e.g., amortization).

5. Visual Aids in Exams:

   • Draw induction step diagrams (e.g., dominoes falling: base case pushes the first, inductive step ensures the next falls).
   • For contradiction, sketch a table showing assumed vs. derived statements leading to absurdity.