Proof Methods

Understanding proofs is fundamental in mathematics and computer science. Proofs provide a systematic way to verify the truth of statements and the correctness of algorithms. This lecture will introduce various proof techniques, including direct proofs, proof by contradiction, proof by contrapositive, and mathematical induction. We will also explore recursion and how it relates to induction, as well as Big-O notation for analyzing algorithm efficiency.

1. Introduction to Proofs
2. Common Mathematical Expressions in Proofs
3. Direct Proofs
4. Proofs Involving Sets
5. Proof by Contrapositive
6. Proof by Contradiction
7. Proof by Cases
8. Mathematical Induction
9. Strong Induction
10. Recursion and Induction
11. Recurrence Relations
12. Big-O Notation
13. Conclusion
14. Practice Problems
15. Additional Notes

• A proof is a logical argument that establishes the truth of a statement.
• Pronunciation: proof (rhymes with roof)
• In mathematics, proofs are essential to validate theorems and propositions.

• Proofs ensure algorithms work correctly.
• They help in verifying the correctness of programs.
• They are crucial for understanding computational complexity.

To construct effective proofs, it’s important to translate statements into precise mathematical language. Below is a summary of common expressions and definitions used in proofs.

• Even Integer:

  • Definition: An integer \( n \) is even if there exists an integer \( k \) such that \( n = 2k \).
  • Example: \( 4 \) is even because \( 4 = 2 \times 2 \).
  • Pronunciation: even integer; n equals two k
  • Alternative Terms: Divisible by 2

• Odd Integer:

  • Definition: An integer \( n \) is odd if there exists an integer \( k \) such that \( n = 2k + 1 \).
  • Example: \( 5 \) is odd because \( 5 = 2 \times 2 + 1 \).
  • Pronunciation: odd integer; n equals two k plus one

• Definition: An integer \( a \) divides an integer \( b \) (written \( a \mid b \)) if there exists an integer \( k \) such that \( b = ak \).
• Example: \( 3 \mid 12 \) because \( 12 = 3 \times 4 \).
• Pronunciation: a divides b; there exists an integer k such that b equals a times k
• Alternative Terms: \( b \) is a multiple of \( a \); \( a \) is a factor of \( b \)

• Prime Number:

  • Definition: An integer \( p > 1 \) is prime if its only positive divisors are \( 1 \) and \( p \).
  • Example: \( 7 \) is prime.
  • Pronunciation: prime number
  • Alternative Terms: None

• Composite Number:

  • Definition: An integer \( n > 1 \) is composite if it is not prime.
  • Example: \( 9 \) is composite because \( 9 = 3 \times 3 \).
  • Pronunciation: composite number
  • Alternative Terms: None

• Rational Number:

  • Definition: A real number \( r \) is rational if there exist integers \( a \) and \( b \neq 0 \) such that \( r = \frac{a}{b} \).
  • Example: \( \frac{1}{2} \) is rational.
  • Pronunciation: rational number; r equals a over b
  • Alternative Terms: None

• Irrational Number:

  • Definition: A real number that is not rational.
  • Example: \( \sqrt{2} \) is irrational.
  • Pronunciation: irrational number
  • Alternative Terms: None

• Definition: Integers \( a \) and \( b \) are congruent modulo \( n \) (written \( a \equiv b \mod n \)) if \( n \mid (a - b) \).
• Example: \( 17 \equiv 5 \mod 12 \) because \( 12 \mid (17 - 5) = 12 \).
• Pronunciation: a is congruent to b modulo n
• Alternative Terms: None

• Floor Function:

  • Definition: \( \lfloor x \rfloor \) is the greatest integer less than or equal to \( x \).
  • Example: \( \lfloor 3.7 \rfloor = 3 \).
  • Pronunciation: floor of x

• Ceiling Function:

  • Definition: \( \lceil x \rceil \) is the least integer greater than or equal to \( x \).
  • Example: \( \lceil 3.2 \rceil = 4 \).
  • Pronunciation: ceiling of x

• Definition: The absolute value of \( x \), denoted \( |x| \), is: [ |x| = \begin{cases} x, & \text{if } x \geq 0 \ -x, & \text{if } x < 0 \end{cases} \]
• Example: \( | -5 | = 5 \).
• Pronunciation: absolute value of x
• Alternative Terms: Modulus

• Transitivity:
  • If \( a > b \) and \( b > c \), then \( a > c \).
• Addition/Subtraction:
  • If \( a > b \), then \( a + c > b + c \).
• Multiplication/Division:
  • If \( a > b \) and \( c > 0 \), then \( ac > bc \).
  • If \( c < 0 \), then \( ac < bc \).

• Distributive Law:
  • \( a(b + c) = ab + ac \).
• Associative Law:
  • Addition: \( (a + b) + c = a + (b + c) \).
  • Multiplication: \( (ab)c = a(bc) \).
• Commutative Law:
  • Addition: \( a + b = b + a \).
  • Multiplication: \( ab = ba \).

• Expressing Statements Precisely:
  • Translate verbal statements into mathematical equations or inequalities.
• Introducing Variables:
  • Assign variables to quantities to simplify expressions.
• Manipulating Equations:
  • Use algebraic techniques to rearrange and simplify equations.
• Working with Definitions:
  • Always refer back to formal definitions when proving statements.

• A direct proof demonstrates the truth of a statement by straightforward logical deductions.
• Pronunciation: dih-rect proof or die-rect proof

1. Assume the hypothesis is true.
2. Use logical steps to arrive at the conclusion.

Statement: The sum of two even integers is even.

Proof:

1. Let \( a \) and \( b \) be even integers.
2. By definition, \( a = 2k \) and \( b = 2m \), where \( k, m \in \mathbb{Z} \).
3. Sum: \( a + b = 2k + 2m = 2(k + m) \).
4. Since \( k + m \in \mathbb{Z} \), \( a + b \) is even.

Statement: The product of two odd integers is odd.

Proof:

1. Let \( a \) and \( b \) be odd integers.
2. By definition, \( a = 2k + 1 \) and \( b = 2m + 1 \), where \( k, m \in \mathbb{Z} \).
3. Product: \( a \cdot b = (2k + 1)(2m + 1) \).
4. Expand: \( 4km + 2k + 2m + 1 = 2(2km + k + m) + 1 \).
5. Since \( 2km + k + m \in \mathbb{Z} \), \( a \cdot b \) is odd.

• Zero is an even number: \( 0 = 2 \times 0 \).
• Negative integers: Evenness and oddness apply to negative integers as well.

Definition: To show that set \( A \) is a subset of set \( B \) (\( A \subseteq B \)), demonstrate that every element of \( A \) is also an element of \( B \).

Statement: Let \( A = \[ x \in \mathbb{Z} \mid 18 \text{ divides } x } \) and \( B = \[ x \in \mathbb{Z} \mid 6 \text{ divides } x } \). Prove that \( A \subseteq B \).

Proof:

1. Let \( x \in A \).
2. Then \( x = 18k \) for some \( k \in \mathbb{Z} \).
3. \( x = 18k = 6(3k) \).
4. Since \( 3k \in \mathbb{Z} \), \( x \) is divisible by \( 6 \).
5. Therefore, \( x \in B \).
6. Hence, \( A \subseteq B \).

Statement: Prove \( A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \).

Proof:

1. To show two sets are equal, prove each is a subset of the other.

2. First, show \( A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C) \).

   • Let \( x \in A \cup (B \cap C) \).
   • Then \( x \in A \) or \( (x \in B \) and \( x \in C) \).
   • If \( x \in A \):
     • \( x \in A \cup B \) and \( x \in A \cup C \).
   • If \( x \in B \) and \( x \in C \):
     • \( x \in A \cup B \) and \( x \in A \cup C \).
   • Therefore, \( x \in (A \cup B) \cap (A \cup C) \).

3. Second, show \( (A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C) \).

   • Let \( x \in (A \cup B) \cap (A \cup C) \).
   • Then \( x \in A \cup B \) and \( x \in A \cup C \).
   • If \( x \in A \):
     • \( x \in A \cup (B \cap C) \).
   • If \( x \in B \) and \( x \in C \):
     • \( x \in B \cap C \).
     • \( x \in A \cup (B \cap C) \).
   • Therefore, \( x \in A \cup (B \cap C) \).

4. Therefore, \( A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \).

• Instead of proving \( p \rightarrow q \), prove its contrapositive \( \lnot q \rightarrow \lnot p \).
• Pronunciation: con-tra-PO-si-tive

Statement: If \( n^2 \) is even, then \( n \) is even.

Proof:

1. Contrapositive: If \( n \) is odd, then \( n^2 \) is odd.
2. Let \( n = 2k + 1 \), where \( k \in \mathbb{Z} \).
3. Compute \( n^2 \): [ n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1. \]
4. Since \( 2k^2 + 2k \in \mathbb{Z} \), \( n^2 \) is odd.
5. Therefore, if \( n^2 \) is even, \( n \) must be even.

• Assume the negation of what you want to prove and derive a contradiction.
• Pronunciation: con-tra-DIC-tion

Statement: \( \sqrt{2} \) is irrational.

Proof:

1. Assume \( \sqrt{2} \) is rational.
2. Then \( \sqrt{2} = \frac{a}{b} \), where \( a \) and \( b \) are coprime integers.
3. Square both sides: [ 2 = \frac{a^2}{b^2} \implies a^2 = 2b^2. \]
4. Therefore, \( a^2 \) is even, so \( a \) is even.
5. Let \( a = 2k \), where \( k \in \mathbb{Z} \).
6. Substitute back: [ (2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2. \]
7. Thus, \( b^2 \) is even, so \( b \) is even.
8. Both \( a \) and \( b \) are even, contradicting that they are coprime.
9. Therefore, \( \sqrt{2} \) is irrational.

• Break the proof into exhaustive cases and prove each one.
• Pronunciation: proof by cases

Statement: For all real numbers \( x \), \( |x| \geq 0 \).

Proof:

1. Case 1: \( x \geq 0 \).
   • Then \( |x| = x \geq 0 \).
2. Case 2: \( x < 0 \).
   • Then \( |x| = -x \).
   • Since \( x < 0 \), \( -x > 0 \).
   • Therefore, \( |x| > 0 \).
3. In both cases, \( |x| \geq 0 \).

To prove that a statement \( P(n) \) holds for all integers \( n \geq k \):

1. Base Case: Verify \( P(k) \) is true.
2. Inductive Step: Assume \( P(n) \) is true for some \( n \geq k \) (induction hypothesis), and prove \( P(n + 1) \) is true.

Statement:

[ \sum_{i=1}^{n} i = \frac{n(n + 1)}{2} \]

Proof:

1. Base Case (\( n = 1 \)):

   • Left side: \( 1 \).
   • Right side: \( \frac{1(1 + 1)}{2} = 1 \).
   • Both sides equal; base case holds.

2. Inductive Step:

   • Assume the formula holds for \( n \): [ \sum_{i=1}^{n} i = \frac{n(n + 1)}{2}. \]
   • Prove it holds for \( n + 1 \): [ \sum_{i=1}^{n+1} i = \left( \sum_{i=1}^{n} i \right) + (n + 1) = \frac{n(n + 1)}{2} + (n + 1). \] [ = \frac{n(n + 1) + 2(n + 1)}{2} = \frac{(n + 1)(n + 2)}{2}. \]
   • Thus, the formula holds for \( n + 1 \).

• Ensure the base case is the smallest integer for which the statement makes sense.
• For statements starting at \( n = 0 \), verify at \( n = 0 \).

• Similar to mathematical induction, but the inductive hypothesis assumes the statement is true for all integers less than or equal to \( n \).
• Pronunciation: strong in-DUC-tion

Statement: Any \( 2^n \times 2^n \) chessboard with one missing square can be tiled with L-shaped tiles.

Proof:

1. Base Case (\( n = 1 \)):

   • A \( 2 \times 2 \) board with one square missing can be tiled with one L-shaped tile.

2. Inductive Step:

   • Assume the statement holds for all sizes up to \( n \).
   • For \( n + 1 \):
     • Divide the \( 2^{n+1} \times 2^{n+1} \) board into four \( 2^n \times 2^n \) sub-boards.
     • Remove one square from one sub-board (the missing square).
     • Place an L-shaped tile at the center to cover one square from each of the other three sub-boards.
     • Now, each sub-board has one square missing.
     • By induction hypothesis, each sub-board can be tiled.
   • Therefore, the board of size \( 2^{n+1} \times 2^{n+1} \) can be tiled.

• A method where the solution to a problem depends on solutions to smaller instances of the same problem.
• Pronunciation: re-CUR-shun

• Recursive definitions can be proven correct using induction.
• Induction validates that recursive steps lead to a correct overall solution.

• Definition:
  • \( 0! = 1 \)
  • \( n! = n \times (n - 1)! \) for \( n > 0 \)

Proof of Correctness:

1. Base Case: \( 0! = 1 \) (given).
2. Inductive Step:
   • Assume \( (n - 1)! \) is correct.
   • Compute \( n! = n \times (n - 1)! \).
   • By induction hypothesis, \( (n - 1)! \) is correct.
   • Therefore, \( n! \) is correctly computed.

• An equation that recursively defines a sequence.
• Pronunciation: re-CUR-ence re-LAY-shun

• Definition:
  • \( F_0 = 0 \)
  • \( F_1 = 1 \)
  • \( F_n = F_{n - 1} + F_{n - 2} \) for \( n \geq 2 \)

1. Assume a solution of the form \( F_n = r^n \).
2. Substitute into the recurrence: [ r^n = r^{n - 1} + r^{n - 2}. \]
3. Simplify: [ r^2 = r + 1. \]
4. Solve the quadratic equation: [ r^2 - r - 1 = 0 \implies r = \frac{1 \pm \sqrt{5}}{2}. \]
5. General solution: [ F_n = c_1 \left( \frac{1 + \sqrt{5}}{2} \right)^n + c_2 \left( \frac{1 - \sqrt{5}}{2} \right)^n. \]
6. Determine constants \( c_1 \) and \( c_2 \) using initial conditions.

• A mathematical notation to describe the upper bound of an algorithm’s running time.
• Pronunciation: big O notation

• \( f(n) = O(g(n)) \) if there exist positive constants \( C \) and \( n_0 \) such that: [ |f(n)| \leq C \cdot |g(n)| \quad \text{for all } n \geq n_0. \]

• Algorithm: Searching an unsorted array.
• Time Complexity: \( O(n) \).

• Algorithm: Bubble sort.
• Time Complexity: \( O(n^2) \).

• Big-O notation ignores constant factors and lower-order terms.
• Focuses on the growth rate as \( n \) becomes large.

Mastering proof techniques and understanding mathematical induction are crucial skills in computer science. They not only help in validating algorithms but also in developing a deeper understanding of computational processes. Recursion and Big-O notation are fundamental concepts for analyzing and designing efficient algorithms.

1. Direct Proof: Prove that the sum of any three consecutive integers is divisible by 3.

   Solution:

   • Let the three consecutive integers be \( n \), \( n + 1 \), and \( n + 2 \).
   • Sum: \( n + (n + 1) + (n + 2) = 3n + 3 = 3(n + 1) \).
   • Since \( 3(n + 1) \) is divisible by 3, the sum is divisible by 3.

2. Proof by Contradiction: Prove that there is no smallest positive rational number.

   Solution:

   • Assume there exists a smallest positive rational number \( r \).
   • Consider \( s = \frac{r}{2} \), which is also a positive rational number.
   • Since \( s < r \), this contradicts the assumption that \( r \) is the smallest.
   • Therefore, there is no smallest positive rational number.

3. Mathematical Induction: Prove that \( 2^n > n \) for all \( n \geq 1 \).

   Solution:

   • Base Case (\( n = 1 \)):
     • \( 2^1 = 2 \), \( n = 1 \), and \( 2 > 1 \).
   • Inductive Step:
     • Assume \( 2^n > n \) for some \( n \geq 1 \).
     • Prove \( 2^{n + 1} > n + 1 \).
     • \( 2^{n + 1} = 2 \cdot 2^n > 2n \) (since \( 2^n > n \)).
     • Since \( n \geq 1 \), \( 2n \geq n + 1 \).
     • Therefore, \( 2^{n + 1} > n + 1 \).

4. Strong Induction: Prove that every amount of postage greater than or equal to 12 cents can be made using 4-cent and 5-cent stamps.

   Solution:

   • Base Cases:
     • \( 12 = 4 \times 3 \)
     • \( 13 = 4 \times 2 + 5 \times 1 \)
     • \( 14 = 4 \times 1 + 5 \times 2 \)
     • \( 15 = 5 \times 3 \)
   • Inductive Step:
     • Assume all amounts from 12 to \( k \) cents can be made.
     • Prove amount \( k + 1 \) can be made.
     • Since \( k - 3 \geq 12 \), the amount \( k - 3 \) can be made.
     • Add a 4-cent stamp to \( k - 3 \) to get \( k + 1 \).
     • Therefore, \( k + 1 \) cents can be made.

5. Recurrence Relation: Solve \( T(n) = 2T\left(\frac{n}{2}\right) + n \) with \( T(1) = 1 \).

   Solution:

   • This recurrence relation corresponds to the Merge Sort algorithm.
   • Using the Master Theorem:
     • \( a = 2 \), \( b = 2 \), \( f(n) = n \), and \( \log_b a = 1 \).
     • Since \( f(n) = n^c \) with \( c = 1 \), and \( \log_b a = c \), case 2 applies.
     • Therefore, \( T(n) = O(n \log n) \).

• Pronunciation Guide:

  • Contrapositive: con-tra-PO-si-tive
  • Contradiction: con-tra-DIC-tion
  • Induction: in-DUC-tion
  • Recursion: re-CUR-shun
  • Coprime: co-PRIME

• Alternative Terms:

  • Edge Cases: Special or extreme cases that require careful consideration.
  • Base Case: The starting point in an inductive proof.

• Tips for Proofs:

  • Always begin by understanding the definitions involved.
  • Translate verbal statements into precise mathematical language.
  • In proofs involving integers, consider parity (evenness or oddness).
  • For divisibility, express numbers in terms of multiples.
  • Use the properties of inequalities when dealing with comparisons.