Mathematical Induction Lecture Notes

Introduction to Mathematical Induction

  • Objective: To cover mathematical induction, which will be relevant for the upcoming tutorial sheets.
  • Overview of the module and related proofs:
    • Types of proofs previously covered:
    • Transformational proofs
    • Deductive proofs
      • Applicable in both propositional logic and predicate logic
      • Mention of proof by induction but lack of elaboration in prior discussions.

What is Mathematical Induction?

  • Mathematical induction is a form of formal reasoning used to verify conjectures.
  • Inductive reasoning: Generalization based on a fair sample of experiments.
  • Formal foundation behind mathematical induction, allowing systematic verification of conjectures.
  • Example provided from Nysanka's book (related to a polynomial):
    • Given polynomial:
    • P(n) = n^7 - 28n^6 + 222n^5 + …
    • Claims that substituting positive integers into this polynomial returns the integer itself.
    • Initial tests for specific integers (1, 2, 7) show correct output, but failure for integers (8, 9) indicates that the conjecture does not hold for all integers.
    • Conclusion: Testing a few cases is insufficient.

Reformulating Functions and Recursive Definitions

  • Example function defined as f(n) = 2^n
    • Further explanation of recursive definitions:
    • f(1) = 2
    • f(n) = 2 imes f(n-1) (for n > 1)
    • Demonstration of building the sequence using recursive definitions leading to the conclusion that the sequence can be described in terms of prior values.

Transition to the First Principle of Mathematical Induction

  • Introduction of the first principle:
    • Let P(k) be a predicate. To show that P is true for all natural numbers greater than or equal to a starting number:
    • Base Condition:
    • Show that P(1) is true.
    • Inductive Step:
    • Show that if P(k-1) is true, then P(k) is also true for all k > 1.

The Inductive Hypothesis and Definitions

  • Definitions:
    • Inductive Hypothesis: The assumptions made to prove the next step.
    • The base step asserts the truth of the predicate for the lowest term.
    • Inductive case confirms if the predicate is true for k based on the truth of k-1.
  • Both conditions must hold true for the general statement to be accepted as true.

Example Proof Using Mathematical Induction

Case 1: Example One

  • Sequence defined such that:
    • s(1) = 1
    • For n > 1: s(n) = s(n-1) + 2^{n-1}
  • Conjecture to prove: s(n) = 2^{n} - 1.
  • Steps of proof:
    • Base case (n=1): Holds since both sides equal 1.
    • Induction hypothesis: Assume for k-1: s(k-1) = 2^{k-1} - 1.
    • Find s(k) = s(k-1) + 2^{k-1}; substitute inductive assumption, manipulate algebraically to support conjecture.
  • Conclusion: The proof indicates that the conjecture is true for all n greater than or equal to 1.

Case 2: Example Two - Arithmetic Sequence

  • Defined as:
    • s(1) = 1
    • For n > 1: s(n) = s(n-1) + n.
  • Conjecture: s(n) = \frac{n(n+1)}{2}.
  • Steps of proof:
    • Verified through specific examples (n = 1, 2, 3, 4).
    • Base case verification holds for n=1.
    • Induction hypothesis established for k-1, verified for k.
    • Concludes assertion of the formula is correct for all n >= 1.

Case 3: Sum of Sequence

  • Another conjecture to prove: I/2 = \frac{n^2 + n - 2}{4} for all n >= 2.
  • Base case: Holds for n=2.
  • Confirm conjecture is true for n=3, n=4, n=5 through arithmetic validation.
  • Same structure as previous examples applied for induction step:
  • Concludes that conjecture holds for all k >= 2.

Systematic Approach and Documentation in Mathematical Induction

  • Documenting proofs through well-structured presentation helps in both academic evaluation and understanding of induction principles.
  • Essential to clearly outline conjectures, base cases, inductive hypotheses, and steps taken to reach conclusions in proofs.

Conclusion

  • Recap of the importance of recognizing that a few tested cases often aren't sufficient evidence for truth.
  • Continuous development of mathematical induction skills is essential for advanced topics in mathematics and applications.
  • Reminder: Focus on understanding the structure and adapting claims using the principles of induction as outlined during examples.