Proof by Mathematical Induction: Sum of Integers

Goal

Prove that (1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}) for all integers (n \geq 1).

Steps in the Proof

1. Base Case

• Definition: The simplest case to verify the statement.
• Case: (n = 1)
  • Left-hand side (LHS): (1)
  • Right-hand side (RHS): (\frac{1(1+1)}{2} = \frac{2}{2} = 1)
  • Verification: LHS = RHS, so the base case holds true.

2. Induction Hypothesis

• Assumption: Assume the statement is true for (n = k).
  • (1 + 2 + 3 + \ldots + k = \frac{k(k+1)}{2})

3. Induction Step

• Goal: Prove the statement for (n = k + 1).
• Setup: Start with the left-hand side for (n = k + 1):
  • (1 + 2 + 3 + \ldots + k + (k+1))
• Use Hypothesis: Replace the sum up to (k) using the hypothesis:
  • (\frac{k(k+1)}{2} + (k+1))
• Common Denominator:
  • Multiply ((k+1)) by (\frac{2}{2}) to combine terms:
  • (\frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{k(k+1) + 2(k+1)}{2})

4. Simplifying the Expression

• Distribute:
  • (k(k+1) + 2(k+1) = k^2 + k + 2k + 2)
  • Combine like terms: (k^2 + 3k + 2)
• Right-hand side for (k + 1):
  • ((k+1)(k+2) = k^2 + 2k + k + 2)
  • Simplifies to: (k^2 + 3k + 2)

5. Verification

• Equality: Both sides simplify to (k^2 + 3k + 2), proving equal numerators.
• Conclusion: Given LHS = RHS for (n = k + 1), the proof holds.

Conclusion

• By induction, the statement holds for all (n \geq 1).
• Successfully proved (1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}).

Additional Information

• Stay tuned for more math tutorials from Learn Math Tutorials.
• Subscribe for more educational content!