IB Mathematics AA – Topic 1: Number & Algebra

The Principle of Mathematical Induction

Perfect for:

• Proving formulas for sums of series: \(\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\)
• Divisibility statements: "\(n^3 - n\) is divisible by 6 for all \(n \geq 1\)"
• Inequalities involving natural numbers: "\(2^n > n^2\) for \(n \geq 5\)"
• Properties of sequences defined recursively
• Statements about powers or factorials

⚠ Common Pitfalls:

• Skipping the base case: This is essential! Without it, the proof fails completely.
• Circular reasoning: Don't assume what you're trying to prove in the inductive step.
• Not using the inductive hypothesis: You MUST use \(P(k)\) to prove \(P(k+1)\).
• Proving only one direction: Show \(P(k) \Rightarrow P(k+1)\), not just that \(P(k+1)\) is true.
• Forgetting the conclusion: Always state "By mathematical induction, \(P(n)\) holds for all \(n \geq n_0\)."

💡 Pro Tips:

• Write "Let \(P(n)\) be the statement..." at the beginning to clarify what you're proving
• Clearly label each part: Base Case, Inductive Hypothesis, Inductive Step, Conclusion
• In the inductive step, start with the LHS of \(P(k+1)\) and manipulate to reach the RHS
• Show your algebra explicitly—don't skip steps in exams!
• For divisibility proofs, factor out the divisor to complete the proof

Example 1: Sum Formula Proof

Problem: Prove by mathematical induction that for all positive integers \(n\):

\(\displaystyle\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}\)

Solution:

Let \(P(n)\) be the statement: \(1^2 + 2^2 + 3^2 + \cdots + n^2 = \displaystyle\frac{n(n+1)(2n+1)}{6}\)

Base Case (\(n = 1\)):

LHS: \(1^2 = 1\)

RHS: \(\displaystyle\frac{1(1+1)(2(1)+1)}{6} = \frac{1 \times 2 \times 3}{6} = \frac{6}{6} = 1\)

LHS = RHS, so \(P(1)\) is true. ✓

Inductive Hypothesis:

Assume \(P(k)\) is true for some \(k \geq 1\):

\(1^2 + 2^2 + 3^2 + \cdots + k^2 = \displaystyle\frac{k(k+1)(2k+1)}{6}\)

Inductive Step:

We need to prove \(P(k+1)\) is true:

\(1^2 + 2^2 + \cdots + k^2 + (k+1)^2 = \displaystyle\frac{(k+1)(k+2)(2k+3)}{6}\)

Starting with LHS of \(P(k+1)\):

\(= (1^2 + 2^2 + \cdots + k^2) + (k+1)^2\)

By inductive hypothesis, replace the sum up to \(k\):

\(= \displaystyle\frac{k(k+1)(2k+1)}{6} + (k+1)^2\)

Factor out \((k+1)\):

\(= (k+1)\left[\displaystyle\frac{k(2k+1)}{6} + (k+1)\right]\)

\(= (k+1)\left[\displaystyle\frac{k(2k+1) + 6(k+1)}{6}\right]\)

\(= (k+1)\left[\displaystyle\frac{2k^2 + k + 6k + 6}{6}\right]\)

\(= (k+1)\left[\displaystyle\frac{2k^2 + 7k + 6}{6}\right]\)

Factor the quadratic:

\(= (k+1)\left[\displaystyle\frac{(k+2)(2k+3)}{6}\right]\)

\(= \displaystyle\frac{(k+1)(k+2)(2k+3)}{6}\)

This is exactly the RHS of \(P(k+1)\). ✓

Conclusion:

Since \(P(1)\) is true, and \(P(k)\) true implies \(P(k+1)\) is true, by the principle of mathematical induction, \(P(n)\) is true for all positive integers \(n\).

Therefore: \(\displaystyle\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}\) for all \(n \in \mathbb{Z}^+\)

Example 2: Divisibility Proof (IB-Style)

Problem: Prove by induction that \(7^n - 1\) is divisible by 6 for all positive integers \(n\).

Solution:

Let \(P(n)\) be the statement: \(7^n - 1\) is divisible by 6

Base Case (\(n = 1\)):

\(7^1 - 1 = 7 - 1 = 6 = 6 \times 1\)

Since 6 is divisible by 6, \(P(1)\) is true. ✓

Inductive Hypothesis:

Assume \(P(k)\) is true for some \(k \geq 1\):

\(7^k - 1 = 6m\) for some integer \(m\)

Equivalently: \(7^k = 6m + 1\)

Inductive Step:

We need to prove \(7^{k+1} - 1\) is divisible by 6.

Consider:

\(7^{k+1} - 1 = 7 \cdot 7^k - 1\)

Using the inductive hypothesis, substitute \(7^k = 6m + 1\):

\(= 7(6m + 1) - 1\)

\(= 42m + 7 - 1\)

\(= 42m + 6\)

\(= 6(7m + 1)\)

Since \(7m + 1\) is an integer, \(7^{k+1} - 1\) is divisible by 6.

Therefore, \(P(k+1)\) is true. ✓

Conclusion:

By the principle of mathematical induction, \(7^n - 1\) is divisible by 6 for all positive integers \(n\).

Structure of Proof by Contradiction

Ideal for:

• Proving irrationality: "\(\sqrt{2}\) is irrational"
• Proving infinitude: "There are infinitely many prime numbers"
• Proving uniqueness: "The solution is unique"
• Proving impossibility: "No such object exists"
• Statements with negations that are easier to work with than the positive statement

⚠ Common Pitfalls:

• Not stating the assumption clearly: Always write "Assume, for contradiction, that..."
• Weak contradictions: The contradiction must be genuine and undeniable.
• Circular reasoning: Don't assume what you're trying to prove within the contradiction.
• Forgetting the conclusion: Always state "This is a contradiction, therefore our assumption was false."

💡 Pro Tips:

• Clearly identify what you're assuming at the start
• Use logical reasoning step-by-step until you reach the contradiction
• The contradiction often involves showing something equals two different values
• For irrationality proofs, assume the number is rational (\(\frac{p}{q}\) in lowest terms)

Example 3: Proving Irrationality

Problem: Prove that \(\sqrt{2}\) is irrational.

Solution:

Assume, for contradiction, that \(\sqrt{2}\) is rational.

Then \(\sqrt{2} = \displaystyle\frac{p}{q}\) where \(p, q \in \mathbb{Z}\), \(q \neq 0\), and \(\gcd(p,q) = 1\)

(i.e., \(\frac{p}{q}\) is in lowest terms)

Square both sides:

\(2 = \displaystyle\frac{p^2}{q^2}\)

\(2q^2 = p^2\)

This means \(p^2\) is even (since \(p^2 = 2q^2\)).

If \(p^2\) is even, then \(p\) must be even.

(If \(p\) were odd, \(p^2\) would be odd)

So we can write \(p = 2k\) for some integer \(k\).

Substituting into \(2q^2 = p^2\):

\(2q^2 = (2k)^2\)

\(2q^2 = 4k^2\)

\(q^2 = 2k^2\)

This means \(q^2\) is even, so \(q\) must be even.

CONTRADICTION: We've shown that both \(p\) and \(q\) are even, which means they have a common factor of 2. But we assumed \(\gcd(p,q) = 1\) (the fraction is in lowest terms).

Conclusion:

Since our assumption leads to a contradiction, the assumption must be false.

Therefore, \(\sqrt{2}\) is irrational.

Example 4: Infinitude of Primes (IB-Style)

Problem: Prove that there are infinitely many prime numbers.

Solution:

Assume, for contradiction, that there are only finitely many primes.

Let these primes be \(p_1, p_2, p_3, \ldots, p_n\) (a complete list of all primes).

Consider the number:

\(N = p_1 \times p_2 \times p_3 \times \cdots \times p_n + 1\)

(The product of all primes, plus 1)

Now \(N > 1\), so \(N\) is either prime or composite.

Case 1: \(N\) is prime

Then \(N\) is a prime not in our list (since \(N > p_n\) for any \(p_n\) in the list).

This contradicts our assumption that we have all primes.

Case 2: \(N\) is composite

Then \(N\) must be divisible by some prime \(p_i\) from our list.

But when we divide \(N\) by \(p_i\):

\(\displaystyle\frac{N}{p_i} = \frac{p_1 \times \cdots \times p_n + 1}{p_i} = \frac{p_1 \times \cdots \times p_n}{p_i} + \frac{1}{p_i}\)

The first term is an integer, but \(\frac{1}{p_i}\) is not an integer.

So \(N\) leaves a remainder of 1 when divided by \(p_i\).

This contradicts the statement that \(p_i\) divides \(N\).

Conclusion:

Both cases lead to contradictions. Therefore, our assumption was false.

There must be infinitely many prime numbers.

Using Counterexamples

Key Points:

• Counterexamples DISPROVE universal statements ("for all x...")
• Cannot prove a universal statement—only disprove it
• Cannot disprove existential statements ("there exists x...")—only prove them
• The counterexample must be valid—check all conditions carefully
• Simple counterexamples are best—use small numbers or obvious cases when possible

⚠ Common Pitfalls:

• Using counterexample to prove: Counterexamples only disprove, never prove!
• Invalid counterexample: Make sure your example meets all the conditions of the statement.
• Not verifying: Show your calculations—don't just assert the counterexample works.
• Confusing "for all" with "there exists": These require different approaches.

💡 Strategy for Finding Counterexamples:

• Try simple values first: 0, 1, -1, 2
• Try boundary cases: smallest/largest values in the domain
• Try special values: fractions, negatives, zero
• Consider what makes the statement "almost false"—then modify slightly

Example 5: Simple Counterexample

Problem: Disprove the statement: "For all real numbers \(x\), \(x^2 > x\)."

Solution:

We need to find a real number \(x\) for which \(x^2 \not> x\).

Counterexample: Let \(x = \frac{1}{2}\)

Then \(x^2 = \left(\frac{1}{2}\right)^2 = \frac{1}{4}\)

And \(x = \frac{1}{2}\)

Since \(\frac{1}{4} < \frac{1}{2}\), we have \(x^2 < x\), not \(x^2 > x\).

Conclusion: The statement "For all real numbers \(x\), \(x^2 > x\)" is false.

Note: Other counterexamples work too, such as \(x = 0\) (where \(0^2 = 0\), not greater) or any \(x\) in \((0, 1)\).

Example 6: Multiple Conditions Counterexample

Problem: Disprove the statement: "If \(n\) is a positive integer, then \(n^2 + n + 41\) is prime."

Solution:

This statement claims that for ALL positive integers \(n\), the expression produces a prime.

We need just one value of \(n\) where the result is composite.

Let's try some values:

\(n = 1\): \(1^2 + 1 + 41 = 43\) (prime ✓)

\(n = 2\): \(2^2 + 2 + 41 = 47\) (prime ✓)

...

(This formula actually produces primes for \(n = 1\) to \(n = 40\)!)

Counterexample: Let \(n = 41\)

\(n^2 + n + 41 = 41^2 + 41 + 41\)

\(= 41^2 + 2(41)\)

\(= 41(41 + 2)\)

\(= 41 \times 43\)

\(= 1763\)

Since \(1763 = 41 \times 43\), this is composite (not prime).

Conclusion: The statement is false. The formula does not always produce primes.

Interesting fact: This formula produces primes for the first 40 values, but fails at \(n = 41\) (and many values beyond).

Structure of Direct Proof

Typical Applications:

• Algebraic identities: Proving \((a+b)^2 = a^2 + 2ab + b^2\)
• Divisibility: "If \(n\) is even, then \(n^2\) is even"
• Inequalities: "If \(a > b > 0\), then \(a^2 > b^2\)"
• Properties of numbers: Sum/product of odds/evens
• Geometric proofs: Angle relationships, triangle properties
• Function properties: Even/odd functions, symmetry

⚠ Common Pitfalls:

• Skipping steps: Show all algebraic manipulations explicitly
• Assuming what you're proving: Don't use the conclusion in your proof
• Invalid operations: Ensure all steps are mathematically valid (e.g., don't divide by zero)
• Unclear reasoning: Each step should follow clearly from the previous one
• Missing justification: State which theorem or property you're using

💡 Pro Tips:

• Write in complete sentences, not just equations
• Use words like "therefore," "hence," "thus" to connect steps
• State what property or theorem justifies each step
• Work backward from conclusion to figure out what you need, then write forward
• Keep notation consistent throughout

Example 7: Proving an Algebraic Identity

Problem: Prove that the sum of two consecutive odd integers is always divisible by 4.

Solution:

Let the first odd integer be \(2n + 1\) for some integer \(n\).

Then the next consecutive odd integer is \(2n + 3\).

The sum of these two consecutive odd integers is:

\(S = (2n + 1) + (2n + 3)\)

\(= 2n + 2n + 1 + 3\)

\(= 4n + 4\)

\(= 4(n + 1)\)

Since \(n\) is an integer, \(n + 1\) is also an integer.

Therefore, \(S = 4(n + 1)\) shows that \(S\) is divisible by 4.

Conclusion: The sum of any two consecutive odd integers is divisible by 4.

Example 8: Conditional Statement (IB-Style)

Problem: Prove that if \(n\) is an integer and \(n^2\) is odd, then \(n\) is odd.

Solution:

We'll prove the contrapositive: If \(n\) is even, then \(n^2\) is even.

(A statement and its contrapositive are logically equivalent)

Assume \(n\) is even.

Then \(n = 2k\) for some integer \(k\) (by definition of even).

Now consider \(n^2\):

\(n^2 = (2k)^2\)

\(= 4k^2\)

\(= 2(2k^2)\)

Since \(k\) is an integer, \(2k^2\) is also an integer.

Let \(m = 2k^2\). Then \(n^2 = 2m\), which shows \(n^2\) is even.

Conclusion:

We've proven: If \(n\) is even, then \(n^2\) is even.

By contrapositive, if \(n^2\) is odd, then \(n\) must be odd.

Therefore: If \(n^2\) is odd, then \(n\) is odd.

Writing Proofs in Exams:

• Be explicit: Show every step, even if it seems obvious
• Use proper language: "Therefore," "hence," "thus," "it follows that"
• Label sections: Clearly mark base case, inductive step, etc.
• State conclusions: Always end with a clear conclusion statement
• Check your logic: Each step must follow from the previous ones

Common Exam Phrases:

• "Prove by induction" → Use the 4-step induction structure
• "Show that" or "Prove" → Usually direct proof or contradiction
• "Disprove" or "Show the statement is false" → Find a counterexample
• "Hence or otherwise" → You can use the previous result

Time Management:

• Proof questions typically worth 4-7 marks
• Budget 1-1.5 minutes per mark
• If stuck, move on and return later
• Partial credit is available—show your thinking!