🔢Lower Division Math Foundations Unit 11 – Mathematical Proof: Induction & Counterexamples

Key Concepts

• Mathematical proofs establish the truth of a statement by using logical reasoning and previously established facts
• Induction proves a statement is true for all natural numbers by proving a base case and an inductive step
• The base case shows the statement holds for the first value (usually 0 or 1)
• The inductive step assumes the statement is true for n and proves it for n+1
• Counterexamples disprove a statement by finding a specific instance where it does not hold
• One counterexample is sufficient to disprove a statement
• Inductive proofs and counterexamples are fundamental tools in mathematical reasoning and problem-solving

Types of Mathematical Proofs

• Direct proof starts with the given information and uses logical steps to reach the desired conclusion
• Indirect proof (proof by contradiction) assumes the negation of the statement and derives a contradiction
• Proof by cases considers all possible cases and proves the statement holds for each one
• Proof by induction proves a statement is true for all natural numbers
• Proof by counterexample disproves a statement by finding an instance where it does not hold
• Combinatorial proofs establish the equality of two expressions by counting the same quantity in different ways
• Constructive proofs demonstrate the existence of an object by explicitly constructing it

Understanding Induction

• Induction is a powerful proof technique for statements involving natural numbers
• It proves a statement P(n) is true for all natural numbers n
• The base case establishes P(0) or P(1) is true
• The inductive hypothesis assumes P(n) is true for some arbitrary natural number n
• The inductive step proves that if P(n) is true, then P(n+1) must also be true
  • This is done by using the inductive hypothesis and manipulating the expression for P(n+1)
• By the principle of mathematical induction, P(n) is true for all natural numbers n
• Induction is often used to prove formulas for sums, products, and sequences

Steps in Inductive Proofs

1. State the proposition P(n) to be proved
2. Prove the base case P(0) or P(1) is true
3. State the inductive hypothesis: assume P(n) is true for some arbitrary natural number n
4. Prove the inductive step: show that if P(n) is true, then P(n+1) must also be true
   • Start with the left-hand side of P(n+1)
   • Manipulate the expression using the inductive hypothesis and other known facts
   • Show the resulting expression is equal to the right-hand side of P(n+1)
5. Conclude that by the principle of mathematical induction, P(n) is true for all natural numbers n
6. Clearly communicate each step and provide justifications for any mathematical manipulations

Counterexamples: What and Why

• A counterexample is a specific instance that disproves a general statement
• Counterexamples show that a statement is false by providing an example where it does not hold
• One counterexample is sufficient to disprove a statement
• Counterexamples are used to test conjectures and refine mathematical statements
• They help identify the limitations and necessary conditions for a statement to be true
• Counterexamples can be used to disprove statements about sets, functions, sequences, and more
• Finding counterexamples develops critical thinking and problem-solving skills

Finding and Constructing Counterexamples

• Understand the statement and identify the key components or conditions
• Consider edge cases or extreme values that might violate the statement
• Look for common counterexamples to similar statements (odds, evens, primes, zeroes, etc.)
• Break down the statement into smaller parts and find counterexamples for each part
• Use intuition and experience to guide the search for counterexamples
• Construct a specific instance that satisfies the conditions but violates the conclusion
• Verify that the counterexample indeed disproves the statement
• Generalize the counterexample if possible to create a family of counterexamples

Common Pitfalls and Mistakes

• Proving the base case but not the inductive step, or vice versa
• Assuming the inductive hypothesis holds for values other than the arbitrary natural number n
• Failing to manipulate the expression for P(n+1) correctly in the inductive step
• Not clearly communicating the steps and justifications in an inductive proof
• Claiming a statement is true based on a few examples without a complete proof
• Attempting to prove a false statement without considering counterexamples
• Misinterpreting the scope or conditions of a statement when searching for counterexamples
• Not verifying that a proposed counterexample actually disproves the statement

Practice Problems and Applications

• Prove by induction that the sum of the first n odd natural numbers is $n^2$
• Use a counterexample to disprove the statement: "All prime numbers are odd"
• Prove by induction that for all $n \geq 1$, $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$
• Find a counterexample to the statement: "The product of any two rational numbers is rational"
• Prove by induction that for all $n \geq 0$, $3^n > 2n$
• Disprove the statement using a counterexample: "Every function has an inverse"
• Use induction to prove that for all $n \geq 1$, $1 + \frac{1}{4} + \frac{1}{9} + \cdots + \frac{1}{n^2} < 2$
• Construct a counterexample to disprove: "Every bounded sequence converges"