Mathematics Induction for Divisibility and Inequality

Introduction

• Topic: Mathematics Induction
• Applications: Divisibility, Inequality
• Recap of previous lecture: Basic Step, Inductive Step
• Focus: Applying induction to problems related to inequalities and divisibility

Divisibility Concept

• Definition: Statements such as 'D divides N'
• Example: 12 is divisible by 3
  • Notation: 3 | 12 or 12 is divisible by 3
  • Example Calculation: 12 / 3 = 4
  • Relation: N = D * K (e.g., 12 = 3 * 4)
  • Key Points: Multiple of D, D is a factor of N

Examples of Divisibility Using Mathematical Induction

Example 1: Prove n³ - n is divisible by 3

• Base Step:
  • Let n = 1: 1³ - 1 = 0
  • 0 is divisible by 3
• Inductive Step:
  • Assume true for n = k: k³ - k is divisible by 3
  • Prove for n = k + 1: (k + 1)³ - (k + 1)
  • Simplify and show it is divisible by 3

Example 2: Prove 2²ⁿ - 1 is divisible by 3 for n ≥ 1

• Base Step:
  • Let n = 1: 2² * 1 - 1 = 3 (divisible by 3)
• Inductive Step:
  • Assume true for n = k: 2²ᵏ - 1 is divisible by 3
  • Prove for n = k + 1: (2²ᵏ + 1 - 1)
  • Simplify using properties of exponents and prove divisibility

Introduction to Inequalities

• Definition: Expressions where equality does not hold but relations are given by <, >, ≤, ≥, or ≠

Example 3: Prove 2n + 1 < 2ⁿ for n ≥ 3

• Base Step:
  • Let n = 3: 2 * 3 + 1 = 7, 2³ = 8
  • 7 < 8 (True)
• Inductive Step:
  • Assume true for n = k: 2k + 1 < 2ᵏ
  • Prove for n = k + 1: Evaluate 2(k + 1) + 1 and compare with 2ᵏ⁺¹
  • Simplify and validate

Example 4: For n ≥ 1, prove (1 + x)ⁿ ≥ 1 + nx

• Base Step:
  • Let n = 2, check left side and right side and compare
• Inductive Step:
  • Assume true for n = k: (1 + x)ᵏ ≥ 1 + kx
  • Prove for n = k + 1: Evaluate (1 + x)ᵏ * (1 + x)
  • Use binomial expansion and properties

Final Examples of Mathematical Induction on Sequences

Example 5: Sequence (a₁, a₂, a₃...), with given terms

• Verify sequence formula using induction

Example 6: Sequence (d₁, d₂, d₃...), with given terms

• Prove the sequence satisfies the given formula by induction

Conclusion

• Recap of dividing concepts, inequalities, and how to use mathematical induction effectively to prove various types of mathematical statements and sequences.
• Questions and clarifications can be asked in the comments.