Mathematical Induction

Introduction to Induction

• Mathematical induction is a proof technique similar to knocking over a line of dominoes.
• Prove that if one term is true, the next term is also true.
• This method allows us to iterate forward, proving subsequent terms.

Steps of Mathematical Induction

1. Base Case: Show that the first term is true (usually for n = 1).
   • Example: For odd numbers, show that the sum of the first odd number equals 1 squared.
2. Inductive Hypothesis: Assume the statement is true for some integer k (k can be any integer).
3. Inductive Step: Show that if the statement is true for k, it is also true for k + 1.
   • If the statement holds for k, prove it holds for k + 1.

Example: Sum of Odd Numbers

• Claim: The sum of the first n odd numbers equals n squared.
• Base Case: For n = 1, sum of first odd number (1) = 1 = 1^2. True.
• Inductive Hypothesis: Assume true for n = k.
  • Sum of first k odd numbers = k^2.
• Inductive Step: Show for n = k + 1.
  • Sum becomes: 1 + 3 + 5 + ... + (2k - 1) + (2(k + 1) - 1).
  • This simplifies to: k^2 + (2k + 1) = (k + 1)^2.
  • Conclusion: If true for k, then true for k + 1.

Important Notes

• Treat the inductive hypothesis as a fact to complete the proof.
• This method cannot prove for every integer directly; it shows a pattern or rule that will always hold.
• Induction shows that if the base case is true and the inductive step applies, the statement holds for all natural numbers.

Conclusion

• Induction is a powerful tool in mathematics, especially in proving formulas related to sequences and series.
• Understanding induction is crucial for progressing in calculus and higher mathematics.