Proof by Induction Study Notes

Proof by induction is a powerful method used to establish mathematical statements. In the IB Mathematics Analysis and Approaches (AA) curriculum, proof techniques are essential for connecting mathematical ideas and building a deeper understanding of complex concepts. These study notes cover proof by induction, proof by contradiction, and the use of counterexamples, along with connections to other areas of mathematics.

Content Guidance, Clarification, and Syllabus Links:

Proof by Mathematical Induction:

This technique should be applied throughout the course where appropriate. It is particularly useful for topics like:

• Complex numbers
• Differentiation
• Sums of sequences
• Divisibility

The process of proof by induction generally involves the following steps:

1. 1. Base Case: Verify the statement is true for an initial value, typically \( n = 1 \).
   2. Inductive Hypothesis: Assume the statement is true for \( n = k \).
   3. Inductive Step: Prove the statement is true for \( n = k + 1 \) using the hypothesis.

Proof by Contradiction:

Involves assuming the opposite of what needs to be proved and showing this leads to a contradiction. Examples include:

• • Irrationality Proofs:

    Prove that \( \sqrt{3} \) and the cube root of 5 are irrational.

  • Euclid’s Proof: Demonstrate the existence of an infinite number of prime numbers.
  • Combination of Rational and Irrational Numbers:

    Prove that if \( a \) is rational and \( b \) is irrational, then \( a + b \) is irrational.

Use of Counterexamples:

A counterexample disproves a statement by providing a specific case where the statement is false. It is insufficient to only provide the example; an explanation of why it contradicts the statement is required.

• • Example 1: Consider the set \( P \) of numbers of the form \( n^2 + 41n + 41 \), \( n \in \mathbb{N} \). Show that not all elements of \( P \) are prime.
  • Example 2: Prove that the statement “there are no positive integer solutions to \( x^2 + y^2 = 10 \)” is not always true by finding a counterexample and explaining it.

Connections:

• Other Contexts: Explore the Four-Colour Theorem.
• International-Mindedness: Investigate how the Pythagoreans discovered that \( \sqrt{2} \) is irrational.
• Theory of Knowledge (TOK):
  • What role does the mathematical community play in determining the validity of a proof?
  • Do mathematical proofs provide us with completely certain knowledge?
  • How does the inductive method in science differ from proof by induction in mathematics?

Examples:

• Example 1: Prove by induction that the sum of the first \( n \) integers is \( \frac{n(n+1)}{2} \).

  Base Case: For \( n = 1 \), \( \frac{1(1+1)}{2} = 1 \). True.

  Inductive Hypothesis: Assume it is true for \( n = k \), i.e., \( \frac{k(k+1)}{2} \).

  Inductive Step: For \( n = k+1 \), show \( \frac{(k+1)(k+2)}{2} \). Calculation confirms the hypothesis.