Proof Methods (extended)

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, along with their logical formulations.

• Even Integer:

  • Definition: An integer \( n \) is even if there exists an integer \( k \) such that \( n = 2k \).
  • Logical Formulation: \( \exists k \in \mathbb{Z},\ n = 2k \)
  • Example 1:
    • \( n = 8 \)
    • \( 8 = 2 \times 4 \), so \( 8 \) is even.
  • Example 2:
    • \( n = -6 \)
    • \( -6 = 2 \times (-3) \), so \( -6 \) is even.
  • Example 3:
    • \( n = 0 \)
    • \( 0 = 2 \times 0 \), so \( 0 \) is even.
  • 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 \).
  • Logical Formulation: \( \exists k \in \mathbb{Z},\ n = 2k + 1 \)
  • Example 1:
    • \( n = 7 \)
    • \( 7 = 2 \times 3 + 1 \), so \( 7 \) is odd.
  • Example 2:
    • \( n = -9 \)
    • \( -9 = 2 \times (-5) + 1 \), so \( -9 \) is odd.
  • Example 3:
    • \( n = 1 \)
    • \( 1 = 2 \times 0 + 1 \), so \( 1 \) is odd.
  • 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 \).
• Logical Formulation: \( a \mid b \iff \exists k \in \mathbb{Z},\ b = ak \)
• Example 1:
  • \( 5 \mid 20 \) because \( 20 = 5 \times 4 \).
• Example 2:
  • \( -3 \mid 9 \) because \( 9 = (-3) \times (-3) \).
• Example 3:
  • \( 4 \mid 0 \) because \( 0 = 4 \times 0 \).
• 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 \).
  • Logical Formulation: \( p > 1 \land \forall d \in \mathbb{N},\ (d \mid p \implies d = 1 \lor d = p) \)
  • Example 1:
    • \( p = 2 \) is prime.
  • Example 2:
    • \( p = 13 \) is prime.
  • Example 3:
    • \( p = 17 \) is prime.
  • Pronunciation: prime number

• Composite Number:

  • Definition: An integer \( n > 1 \) is composite if it is not prime.
  • Logical Formulation: \( n > 1 \land \exists d \in \mathbb{N},\ 1 < d < n,\ d \mid n \)
  • Example 1:
    • \( n = 4 \) because \( 2 \mid 4 \).
  • Example 2:
    • \( n = 15 \) because \( 3 \mid 15 \) and \( 5 \mid 15 \).
  • Example 3:
    • \( n = 21 \) because \( 3 \mid 21 \) and \( 7 \mid 21 \).
  • Pronunciation: composite number

• Rational Number:

  • Definition: A real number \( r \) is rational if there exist integers \( a \) and \( b \neq 0 \) such that \( r = \frac{a}{b} \).
  • Logical Formulation: \( \exists a, b \in \mathbb{Z},\ b \neq 0,\ r = \frac{a}{b} \)
  • Example 1:
    • \( r = 0.5 = \frac{1}{2} \).
  • Example 2:
    • \( r = -3 = \frac{-3}{1} \).
  • Example 3:
    • \( r = 0 = \frac{0}{1} \).
  • Pronunciation: rational number; r equals a over b

• Irrational Number:

  • Definition: A real number that is not rational.
  • Logical Formulation: \( \lnot (\exists a, b \in \mathbb{Z},\ b \neq 0,\ r = \frac{a}{b}) \)
  • Example 1:
    • \( r = \pi \).
  • Example 2:
    • \( r = e \) (Euler’s number).
  • Example 3:
    • \( r = \sqrt{3} \).
  • Pronunciation: irrational number

• Definition: Integers \( a \) and \( b \) are congruent modulo \( n \) (written \( a \equiv b \mod n \)) if \( n \mid (a - b) \).
• Logical Formulation: \( a \equiv b \mod n \iff n \mid (a - b) \)
• Example 1:
  • \( 14 \equiv 2 \mod 12 \) because \( 12 \mid (14 - 2) = 12 \).
• Example 2:
  • \( -1 \equiv 4 \mod 5 \) because \( 5 \mid (-1 - 4) = -5 \).
• Example 3:
  • \( 100 \equiv 0 \mod 10 \) because \( 10 \mid (100 - 0) = 100 \).
• Pronunciation: a is congruent to b modulo n

• Floor Function:

  • Definition: \( \lfloor x \rfloor \) is the greatest integer less than or equal to \( x \).
  • Logical Formulation: \( \lfloor x \rfloor = \text{max} { n \in \mathbb{Z} \mid n \leq x } \)
  • Example 1:
    • \( \lfloor 2.9 \rfloor = 2 \).
  • Example 2:
    • \( \lfloor -1.2 \rfloor = -2 \).
  • Example 3:
    • \( \lfloor 5 \rfloor = 5 \).
  • Pronunciation: floor of x

• Ceiling Function:

  • Definition: \( \lceil x \rceil \) is the least integer greater than or equal to \( x \).
  • Logical Formulation: \( \lceil x \rceil = \text{min} { n \in \mathbb{Z} \mid n \geq x } \)
  • Example 1:
    • \( \lceil 3.1 \rceil = 4 \).
  • Example 2:
    • \( \lceil -0.7 \rceil = 0 \).
  • Example 3:
    • \( \lceil 6 \rceil = 6 \).
  • 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} \]
• Logical Formulation:
  • \( |x| = x \) if \( x \geq 0 \).
  • \( |x| = -x \) if \( x < 0 \).
• Example 1:
  • \( |7| = 7 \).
• Example 2:
  • \( |-3| = 3 \).
• Example 3:
  • \( |0| = 0 \).
• Pronunciation: absolute value of x
• Alternative Terms: Modulus

• Transitivity:

  • Definition: If \( a > b \) and \( b > c \), then \( a > c \).
  • Logical Formulation: \( (a > b \land b > c) \implies a > c \)
  • Example 1:
    • If \( 5 > 3 \) and \( 3 > 1 \), then \( 5 > 1 \).
  • Example 2:
    • If \( -2 > -5 \) and \( -5 > -8 \), then \( -2 > -8 \).
  • Example 3:
    • If \( x > y \) and \( y > z \), then \( x > z \).
  • Pronunciation: transitivity of inequalities

• Addition/Subtraction:

  • Definition: If \( a > b \), then \( a + c > b + c \).
  • Logical Formulation: \( (a > b) \implies (a + c > b + c) \)
  • Example 1:
    • \( 4 > 2 \implies 4 + 3 > 2 + 3 \) (i.e., \( 7 > 5 \)).
  • Example 2:
    • \( -1 > -3 \implies -1 - 2 > -3 - 2 \) (i.e., \( -3 > -5 \)).
  • Example 3:
    • \( x > y \implies x - k > y - k \).
  • Pronunciation: addition property of inequalities

• Multiplication/Division:

  • Definition:
    • If \( a > b \) and \( c > 0 \), then \( ac > bc \).
    • If \( c < 0 \), then \( ac < bc \).
  • Logical Formulation:
    • \( (a > b \land c > 0) \implies ac > bc \).
    • \( (a > b \land c < 0) \implies ac < bc \).
  • Example 1:
    • \( 3 > 1 \) and \( 2 > 0 \) imply \( 3 \times 2 > 1 \times 2 \) (i.e., \( 6 > 2 \)).
  • Example 2:
    • \( -2 > -4 \) and \( -1 < 0 \) imply \( -2 \times -1 < -4 \times -1 \) (i.e., \( 2 < 4 \)).
  • Example 3:
    • If \( x > y \) and \( c < 0 \), then \( xc < yc \).
  • Pronunciation: multiplication property of inequalities

• Distributive Law:

  • Definition: \( a(b + c) = ab + ac \)
  • Logical Formulation: For all \( a, b, c \in \mathbb{R} \), \( a(b + c) = ab + ac \)
  • Example 1:
    • \( 2(3 + 4) = 2 \times 3 + 2 \times 4 \).
  • Example 2:
    • \( -1(x - y) = -x + y \).
  • Example 3:
    • \( k(m + n) = km + kn \).
  • Pronunciation: distributive law

• Associative Law:

  • Addition:
    • Definition: \( (a + b) + c = a + (b + c) \)
    • Logical Formulation: For all \( a, b, c \in \mathbb{R} \), \( (a + b) + c = a + (b + c) \)
  • Multiplication:
    • Definition: \( (ab)c = a(bc) \)
    • Logical Formulation: For all \( a, b, c \in \mathbb{R} \), \( (ab)c = a(bc) \)
  • Example 1 (Addition):
    • \( (1 + 2) + 3 = 1 + (2 + 3) \).
  • Example 2 (Multiplication):
    • \( (2 \times 3) \times 4 = 2 \times (3 \times 4) \).
  • Example 3 (Variables):
    • \( (x + y) + z = x + (y + z) \).
  • Pronunciation: associative law

• Commutative Law:

  • Addition:
    • Definition: \( a + b = b + a \)
    • Logical Formulation: For all \( a, b \in \mathbb{R} \), \( a + b = b + a \)
  • Multiplication:
    • Definition: \( ab = ba \)
    • Logical Formulation: For all \( a, b \in \mathbb{R} \), \( ab = ba \)
  • Example 1 (Addition):
    • \( 5 + 7 = 7 + 5 \).
  • Example 2 (Multiplication):
    • \( 4 \times 9 = 9 \times 4 \).
  • Example 3 (Variables):
    • \( x \times y = y \times x \).
  • Pronunciation: commutative law

• Expressing Statements Precisely:

  • Example 1:
    • Verbal: “The square of an odd integer is odd.”
    • Mathematical: If \( n = 2k + 1 \), then \( n^2 = 2m + 1 \) for some \( m \in \mathbb{Z} \).
  • Example 2:
    • Verbal: “The sum of two rational numbers is rational.”
    • Mathematical: \( \forall a, b \in \mathbb{Q},\ a + b \in \mathbb{Q} \).
  • Example 3:
    • Verbal: “The product of a non-zero rational number and an irrational number is irrational.”
    • Mathematical: \( \forall r \in \mathbb{Q},\ r \neq 0,\ \forall s \in \mathbb{R} \setminus \mathbb{Q},\ rs \in \mathbb{R} \setminus \mathbb{Q} \).
  • Pronunciation: expressing statements precisely

• Introducing Variables:

  • Example 1:
    • Let \( n \in \mathbb{N} \) represent an arbitrary natural number.
  • Example 2:
    • Suppose \( x \in \mathbb{R} \) is such that \( x > 0 \).
  • Example 3:
    • Let \( \epsilon > 0 \) be given.
  • Pronunciation: introducing variables

• Manipulating Equations:

  • Example 1:
    • Given \( a + b = c \), then \( b = c - a \).
  • Example 2:
    • If \( x^2 = y \), then \( x = \pm \sqrt{y} \).
  • Example 3:
    • From \( ab = ac \), if \( a \neq 0 \), then \( b = c \).
  • Pronunciation: manipulating equations

• 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 an odd integer and an even integer is even.

Proof:

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

Statement: The sum of two rational numbers is rational.

Proof:

1. Let \( r = \frac{a}{b} \) and \( s = \frac{c}{d} \), where \( a, b, c, d \in \mathbb{Z} \) and \( b \neq 0 \), \( d \neq 0 \).
2. Sum: \( r + s = \frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{bd} \).
3. Since \( ad + bc \) and \( bd \) are integers and \( bd \neq 0 \), \( r + s \) is rational.

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: Let \( A = { x \in \mathbb{R} \mid x > 5 } \) and \( B = { x \in \mathbb{R} \mid x > 0 } \). Prove that \( A \subseteq B \).

Proof:

1. Let \( x \in A \).
2. Then \( x > 5 \).
3. Since \( x > 5 > 0 \), \( x > 0 \).
4. Therefore, \( x \in B \).
5. Hence, \( A \subseteq B \).

Statement: Let \( A = { f \mid f \text{ is a differentiable function} } \) and \( B = { f \mid f \text{ is continuous} } \). Prove that \( A \subseteq B \).

Proof:

1. Let \( f \in A \).
2. Then \( f \) is differentiable.
3. By the properties of real analysis, differentiable functions are continuous.
4. Therefore, \( f \in B \).
5. Hence, \( A \subseteq B \).

• 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.

Statement: If a function \( f \) is not injective, then there exist \( x_1 \neq x_2 \) such that \( f(x_1) = f(x_2) \).

Proof:

1. Contrapositive: If for all \( x_1 \neq x_2 \), \( f(x_1) \neq f(x_2) \), then \( f \) is injective.
2. This is the definition of injectivity.
3. Therefore, the original statement holds.

Statement: If \( ab = 0 \), then \( a = 0 \) or \( b = 0 \).

Proof:

1. Contrapositive: If \( a \neq 0 \) and \( b \neq 0 \), then \( ab \neq 0 \).
2. Since \( a \neq 0 \) and \( b \neq 0 \), their product \( ab \neq 0 \).
3. Therefore, if \( ab = 0 \), at least one of \( a \) or \( b \) must be zero.

• 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.

Statement: There are infinitely many prime numbers.

Proof:

1. Assume, for contradiction, that there are finitely many prime numbers \( p_1, p_2, \dots, p_n \).
2. Consider the number \( Q = p_1 p_2 \dots p_n + 1 \).
3. \( Q \) is greater than any of the listed primes.
4. \( Q \) is either prime or composite.
   • If \( Q \) is prime, it is a prime not in our list, contradiction.
   • If \( Q \) is composite, it has a prime divisor not in our list.
5. In either case, we have a contradiction.
6. Therefore, there must be infinitely many primes.

Statement: The sum of a rational number and an irrational number is irrational.

Proof:

1. Let \( r \in \mathbb{Q} \) (rational) and \( s \notin \mathbb{Q} \) (irrational).
2. Assume, for contradiction, that \( r + s \in \mathbb{Q} \).
3. Then \( s = (r + s) - r \).
4. Since \( r + s \) and \( r \) are rational, their difference is rational.
5. This contradicts that \( s \) is irrational.
6. Therefore, \( r + s \) must be 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 > 0 \).
3. In both cases, \( |x| \geq 0 \).

Statement: For any integer \( n \), the product \( n(n+1) \) is even.

Proof:

1. Case 1: \( n \) is even.
   • Let \( n = 2k \).
   • \( n(n+1) = (2k)(2k + 1) = 2k(2k + 1) \).
   • The product is even because it’s divisible by 2.
2. Case 2: \( n \) is odd.
   • Let \( n = 2k + 1 \).
   • \( n(n+1) = (2k + 1)(2k + 2) = (2k + 1)(2(k + 1)) \).
   • The product is even because it includes a factor of 2.
3. In both cases, \( n(n+1) \) is even.

Statement: For any integer \( n \), \( n^2 \equiv 0 \) or \( 1 \mod 4 \).

Proof:

1. Case 1: \( n \) is even.
   • Let \( n = 2k \).
   • \( n^2 = (2k)^2 = 4k^2 \).
   • \( n^2 \mod 4 = 0 \).
2. Case 2: \( n \) is odd.
   • Let \( n = 2k + 1 \).
   • \( n^2 = (2k + 1)^2 = 4k(k + 1) + 1 \).
   • \( n^2 \mod 4 = 1 \).
3. Thus, \( n^2 \equiv 0 \) or \( 1 \mod 4 \) in all cases.

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:

[Provided in previous answer.]

Statement:

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

Proof:

1. Base Case (\( n = 1 \)):
   • Left side: \( 2(1) - 1 = 1 \).
   • Right side: \( 1^2 = 1 \).
   • Both sides equal; base case holds.
2. Inductive Step:
   • Assume the formula holds for \( n \): \[ \sum_{i=1}^{n} (2i - 1) = n^2. \]
   • Prove it holds for \( n + 1 \): \[ \sum_{i=1}^{n+1} (2i - 1) = n^2 + [2(n+1) - 1] = n^2 + 2n + 1 = (n + 1)^2. \]
   • Thus, the formula holds for \( n + 1 \).

Statement:

\[ \sum_{i=0}^{n} 2^i = 2^{n+1} - 1 \]

Proof:

1. Base Case (\( n = 0 \)):
   • Left side: \( 2^0 = 1 \).
   • Right side: \( 2^{0+1} - 1 = 2 - 1 = 1 \).
   • Both sides equal; base case holds.
2. Inductive Step:
   • Assume the formula holds for \( n \): \[ \sum_{i=0}^{n} 2^i = 2^{n+1} - 1. \]
   • Prove it holds for \( n + 1 \): \[ \sum_{i=0}^{n+1} 2^i = \left( \sum_{i=0}^{n} 2^i \right) + 2^{n+1} = [2^{n+1} - 1] + 2^{n+1} = 2^{n+2} - 1. \]
   • Thus, the formula holds for \( n + 1 \).

• 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:

[Provided in previous answer.]

Statement: Any amount of postage of 8 cents or more can be formed using 3-cent and 5-cent stamps.

Proof:

1. Base Cases:
   • \( 8 = 3 \times 1 + 5 \times 1 \).
   • \( 9 = 3 \times 3 + 5 \times 0 \).
   • \( 10 = 3 \times 0 + 5 \times 2 \).
2. Inductive Step:
   • Assume that postage amounts from 8 up to \( k \) cents can be formed.
   • Prove that postage \( k + 1 \) can be formed.
   • Since \( k - 2 \geq 8 \), the amount \( k - 2 \) can be formed.
   • Add a 3-cent stamp to \( k - 2 \) to get \( (k - 2) + 3 = k + 1 \).
   • Thus, \( k + 1 \) cents can be formed.
3. Therefore, any amount \( n \geq 8 \) can be formed.

Statement: Every integer greater than 1 can be written as a product of prime numbers.

Proof:

1. Base Case (\( n = 2 \)):
   • \( 2 \) is prime; it’s a product of itself.
2. Inductive Step:
   • Assume every integer \( m \) with \( 2 \leq m < n \) can be written as a product of primes.
   • If \( n \) is prime, done.
   • If \( n \) is composite, \( n = a \times b \), where \( 2 \leq a, b < n \).
   • By induction hypothesis, \( a \) and \( b \) are products of primes.
   • Thus, \( n \) is a product of primes.
3. Therefore, every integer \( n > 1 \) can be written as a product of primes.

• 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:

[Provided in previous answer.]

Statement: The recursive Euclidean algorithm correctly computes the greatest common divisor (GCD) of two positive integers \( a \) and \( b \).

Proof:

1. Base Case: When \( b = 0 \), \( \gcd(a, 0) = a \).
2. Recursive Step:
   • The algorithm computes \( \gcd(a, b) = \gcd(b, a \mod b) \).
   • Assume \( \gcd(b, a \mod b) \) correctly computes the GCD.
   • By the Euclidean algorithm, \( \gcd(a, b) = \gcd(b, a \mod b) \).
3. Therefore, the recursive algorithm correctly computes \( \gcd(a, b) \).

Statement: For the recursively defined sequence \( a_0 = 1 \), \( a_{n+1} = 2a_n + 1 \), prove that \( a_n = 2^{n+1} - 1 \).

Proof:

1. Base Case (\( n = 0 \)):
   • \( a_0 = 1 \).
   • Right side: \( 2^{0+1} - 1 = 2^1 - 1 = 1 \).
2. Inductive Step:
   • Assume \( a_n = 2^{n+1} - 1 \).
   • Compute \( a_{n+1} = 2a_n + 1 = 2(2^{n+1} - 1) + 1 = 2^{n+2} - 2 + 1 = 2^{n+2} - 1 \).
3. Thus, the formula holds for \( n + 1 \).

• 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 \)

Solution:

[Provided in previous answer.]

Statement: Solve \( T(n) = T(n - 1) + n \) with \( T(1) = 1 \).

Solution:

1. Recognize that \( T(n) = 1 + 2 + \dots + n = \frac{n(n + 1)}{2} \).
2. Use induction to prove the formula.

Statement: Solve \( T(n) = 2T(n - 1) \) with \( T(0) = 1 \).

Solution:

1. Unfold the recurrence: \[ T(n) = 2^n T(0) = 2^n \times 1 = 2^n. \]
2. Thus, \( T(n) = 2^n \).

• 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) \).

Statement: Show that \( f(n) = 3n^2 + 2n + 1 \) is \( O(n^2) \).

Proof:

1. For \( n \geq 1 \): \[ f(n) = 3n^2 + 2n + 1 \leq 3n^2 + 2n^2 + n^2 = 6n^2. \]
2. Choose \( C = 6 \) and \( n_0 = 1 \).
3. Therefore, \( f(n) \leq C n^2 \) for all \( n \geq n_0 \).

Statement: Show that \( f(n) = n \log n + 5n \) is \( O(n \log n) \).

Proof:

1. For \( n \geq 2 \), \( \log n \geq 1 \).
2. Then \( f(n) = n \log n + 5n \leq n \log n + 5n \log n = 6n \log n \).
3. Choose \( C = 6 \) and \( n_0 = 2 \).
4. Therefore, \( f(n) \leq C n \log n \) for all \( n \geq n_0 \).

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 product of two even integers is divisible by 4.

2. Proof by Contradiction: Prove that \( \sqrt{3} \) is irrational.

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

4. Strong Induction: Prove that every positive integer \( n \geq 2 \) can be represented as a sum of \( 2 \)’s and \( 3 \)’s.

5. Recurrence Relation: Solve \( T(n) = T(n/2) + 1 \) with \( T(1) = 1 \).

• 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.