Detailed Overview of Mathematical Induction

Mathematical Induction

• Definition: A technique used to prove statements of the form "… is true for all integers larger than a particular number."

Concept of Mathematical Induction

• Imagery: Imagine an infinite chain of dominoes:
  • If the first domino topples (1), and each toppling domino causes the next one to topple (2), then all dominoes will fall.
  • This corresponds to proving a claim for all integers $n \geq a$:
    • First Domino: Corresponds to $n = a$.
    • Subsequent Dominoes: Correspond to $n = a + 1$, $n = a + 2$, etc.

Principle of Mathematical Induction

• Setup: Let $D = { n \in \mathbb{Z} | n \geq a }$.
• Claim Requirements:
  • Claim must be true for $n = a$.
  • If true for $n = k$, then true for $n = k + 1$.
• Conclusion: If both conditions hold, the claim is true for all $n \in D$.

Proof by Induction Template

1. Basis Step: Show the claim holds when $n = a$.
2. Inductive Hypothesis: Assume the claim is true for a fixed integer $k \geq a$.
3. Inductive Step: Show it holds when $n = k + 1$ based on the inductive hypothesis.
4. Conclusion: By induction, the claim holds for all integers $n \geq a$.

Important Considerations in Inductive Proofs

• Interpretation:
  • Basis Step: Show claim for specific $n = a$, not just stating it.
  • Induction Hypothesis: Assume the claim holds for the fixed integer $k$, not all integers.
  • Induction Step: Prove the claim holds for $n = k + 1$, specifically, not just assuming it.

Strategies for the Inductive Step

• Begin with what you want to prove ($n = k + 1$).
• Write this in terms of the inductive hypothesis ($n = k$).
• Use the inductive hypothesis explicitly.
• Try to link parts together through forwards and backwards reasoning.

Example 1: Summation Formula Proof

• Goal: Show that for every positive integer $n$, $1 + 2 + ext{…} + n = \frac{n(n + 1)}{2}$.
• Steps:
  1. Basis Step: For $n = 1$, $1 = \frac{1(1 + 1)}{2}$ holds true.
  2. Inductive Hypothesis: Assume true for $n = k$: $1 + 2 + … + k = \frac{k(k + 1)}{2}$.
  3. Inductive Step: Show for $n = k + 1$:
     • $1 + 2 + … + k + (k + 1) = \frac{k(k + 1)}{2} + (k + 1)$
     • Simplifying gives:
       $\frac{(k + 1)(k + 2)}{2}$ which matches the formula for $n = k + 1$.
  4. Conclusion: By induction, it follows that $1 + 2 + … + n = \frac{n(n + 1)}{2}$ for all positive integers $n$.

Example 2: Geometric Series Formula Proof

• Goal: Show $1 + r + r^2 + … + r^n = \frac{r^{n+1} - 1}{r - 1}$ for $r \neq 1$.
• Steps:
  1. Basis Step: Check for $n = 0$: $1 = \frac{r^{0+1} - 1}{r - 1}$ is true.
  2. Inductive Hypothesis: Assume it true for $n = k$:
     $1 + r + r^2 + … + r^k = \frac{r^{k+1} - 1}{r - 1}$.
  3. Inductive Step: Prove for $n = k + 1$:
     • Show $1 + r + r^2 + … + r^{k+1} = \frac{r^{k+2} - 1}{r - 1}$ holds.
  4. Conclusion: Thus, by induction, the statement is true for every integer $n \geq 0$.

Practice Problems

• Find the following sums:
  • $1 + 2 + 3 + … + 100$
  • $11 + 12 + 13 + … + 100$
  • $2 + 4 + 6 + … + 100$
  • $1 + 3 + 5 + … + 99$
  • $1 + 2 + 4 + … + 2^{n-1}$
  • $9 + 27 + 81 + … + 380$
  • $\sum_{k=0}^{1000} 10^{3k + 2}$

Summation Examples and Solutions

• Example:
  • $1 + 2 + 3 + … + 100 = \frac{100(100 + 1)}{2} = 5050$
  • $11 + 12 + 13 + … + 100 = 4995$
  • $2 + 4 + 6 + … + 100 = 2550$
  • $1 + 3 + 5 + … + 99 = 2500$
  • $1 + 2 + 4 + … + 2^{n-1} = 2^n - 1$
  • $9 + 27 + 81 + … + 380 = \frac{381 - 9}{2}$
  • $\sum_{k=0}^{1000} 10^{3k + 2} = 10^{1000 + 1} - 10^2 \div 10^3 - 1$