Unlike direct proofs, where the result follows as a logical step, mathematical induction is a form of indirect proof (the only one covered in the IB syllabus). Indirect proofs tend to require a ‘creative’ step, however through training one can recognise most forms of induction.
Proof by induction can always be split up into three components, that together prove the wanted statement:
Common types: f(n) > g(n), f(n) = g(n), f(n) < g(n), Σ, P(n) is a multiple / divisible.
- Write statement in mathematical form
- Assume true for n = k
Hence, since P (1) true and assuming P(k) true, we have shown by the principle of mathematical induction that P(k + 1) true. Therefore, 5 × (7n) − 1 is divisible by 6 for all positive integers.
Induction
- Check for n = 1
4. Write concluding statement
Hence, since n = 1 is true and assuming n = k true, we have shown by the principle of mathematical induction that n = k + 1 true. Therefore,
Mathematical Induction FAQs
Mathematical Induction is a powerful technique used to **prove that a statement, a formula, or a property is true for all natural numbers** (usually starting from 1, 0, or some specific integer). It's a method of proof, not a way to find formulas or patterns. It's like setting up a chain reaction.
It is particularly useful for proving statements about sums, inequalities, divisibility, and properties of sequences defined by recursion.
A standard proof by mathematical induction involves two main steps (often called the Principle of Mathematical Induction):
- Base Case: Show that the statement is true for the initial value (usually \(n=1\) or \(n=0\)). This "starts" the chain reaction.
- Inductive Step: Assume the statement is true for an arbitrary natural number \(k \ge n_0\) (where \(n_0\) is the base case value). This assumption is called the **Inductive Hypothesis**. Then, using this assumption, prove that the statement must also be true for the next natural number, \(k+1\). This proves that if one link in the chain is true, the next link is also true.
Once both steps are completed, you conclude by the Principle of Mathematical Induction that the statement is true for all natural numbers greater than or equal to the base case.
Think of it like an infinite line of dominoes:
- The Base Case is like pushing over the first domino. You prove the statement is true for the starting value.
- The Inductive Step is like showing that if any domino falls (assuming the statement is true for \(k\)), then the next domino will also fall (proving the statement is true for \(k+1\)).
If you can push over the first domino (base case) and show that every domino falling knocks over the next one (inductive step), then you know *all* the dominoes will fall (the statement is true for all applicable natural numbers). It guarantees that the truth "propagates" indefinitely from the base case.
The Principle of Mathematical Induction is the formal statement that justifies the proof technique. It states that if a property \(P(n)\) is true for a base case (e.g., \(P(1)\) is true) and if, for every natural number \(k\), the truth of \(P(k)\) implies the truth of \(P(k+1)\), then the property \(P(n)\) is true for all natural numbers \(n \ge \text{base case}\).
It's the underlying axiom or principle that makes the two-step proof method valid.
Standard (or "weak") induction assumes \(P(k)\) is true to prove \(P(k+1)\).
Strong Induction is a variation where, in the inductive step, you assume that the statement is true for *all* natural numbers from the base case up to \(k\) (i.e., you assume \(P(n)\) is true for all \(n_0 \le n \le k\)). Using this stronger assumption, you then prove the statement is true for \(k+1\).
Despite the name, strong induction is logically equivalent to weak induction; any proof done by strong induction can be done by weak induction, and vice versa. Strong induction is often more convenient or intuitive for certain types of proofs, especially those involving recurrence relations where the truth of \(P(k+1)\) depends on more than just \(P(k)\).
Mathematical induction can be challenging for beginners because it requires a specific logical structure for proofs. Understanding the inductive hypothesis and how to use it effectively in the inductive step is key. It requires careful algebraic manipulation and clear logical reasoning.
However, with practice and understanding the underlying principle (the domino analogy is often helpful), it becomes a very manageable and powerful proof technique.
While the concept of recursive reasoning appears in ancient proofs (like Euclid's proof that there are infinitely many prime numbers), the explicit formulation of mathematical induction as a distinct proof method is generally credited to **Blaise Pascal** in the 17th century, particularly in his work on the "arithmetical triangle" (Pascal's Triangle). Earlier mathematicians like Francesco Maurolico in the 16th century also used similar ideas. The term "induction" was later coined by **Augustus De Morgan** in the 19th century.
You can use mathematical induction to prove a statement that is about **all natural numbers** (or all integers greater than or equal to some starting integer). It's suitable for statements like:
- Formulas for the sum of a series (e.g., \(1+2+\dots+n = n(n+1)/2\)).
- Inequalities involving \(n\).
- Statements about divisibility (e.g., \(n^3 - n\) is divisible by 3 for all natural numbers \(n\)).
- Properties of sequences defined by recurrence relations.
- Properties of algorithms or data structures that proceed in steps.
It's not suitable for proving statements about real numbers in general, or for statements that don't involve a natural number index.