Chapter 2 defines what a^n means for a group element a and a positive integer n. It then proves the exponent laws: a^m a^n = a^{m+n} and (a^m)^n = a^{mn}. The proof builds up one factor of a at a time, the same way you would prove any statement indexed by the positive integers. Chapter 3's modular-exponentiation preview, and several of chapter 7's consequences of Lagrange's theorem, lean on the same technique again. None of that requires anything beyond ordinary induction on \mathbb{N}. This section just puts weak induction, strong induction, and the well-ordering principle they all rest on back within reach.
Weak induction is a ladder. Reach the first rung, show that standing on any rung lets you reach the next one, and you can climb as high as you like. Strong induction is a similar ladder, except some rungs only hold your weight if you're also still touching several rungs below, not just the one under your feet. You can still climb it. You just get to lean on more of what came before at every step. The well-ordering principle is a separate, simpler idea underneath both ladders. Any pile of positive whole numbers, as long as it isn't empty, has a smallest member, no matter how it was chosen. Handed an infinite ladder with no smallest rung, you could never even take the first step.
Mathematical induction is a proof technique for statements indexed by the positive integers. It comes in two strengths. Weak induction proves P(n) for every n \ge n_0. It needs a base case P(n_0) and a step showing P(k) \Rightarrow P(k+1). Strong induction proves the same conclusion a different way. Its step gets to assume every earlier case P(n_0), \ldots, P(k), not just the one right before it. That is needed whenever building case k+1 might depend on some smaller case other than k itself. This happens, for instance, when a number is split into two smaller factors. Both versions are equivalent to the well-ordering principle: every nonempty set of positive integers has a least element. That link is what makes all three trustworthy at once, instead of three separate leaps of faith. It is also why a proof using either kind counts as a fully valid proof, not a shortcut standing in for one.
Theorem
The Principle of Mathematical Induction
Recalled from College Algebra · The induction principle — first taught there.
Let P(n) be a statement about the integer n, and let n_0 be a fixed starting integer. Suppose both of the following hold:
- Base case. P(n_0) is true.
- Inductive step. For every integer k \ge n_0: if P(k) is true (the inductive hypothesis) then P(k+1) is also true.
Then P(n) is true for every integer n \ge n_0.
This principle isn't derived from something more basic in this course — it's taken as one of the foundational properties of the integers themselves (equivalent to the well-ordering principle: every nonempty set of integers bounded below has a least element, a fact from set theory this course doesn't build). The domino-chain intuition is a genuine guide to why it's believable — P(n_0) is true, and the inductive step means each true case knocks over the next one — but making that intuition airtight for infinitely many dominoes is exactly what the well-ordering principle supplies, and that belongs to a foundations-of-mathematics course, not this one. It's used freely here because every course that reaches integers uses it freely.
Theorem
The Principle of Strong Induction
Recalled from College Algebra · The induction principle — first taught there.
Let P(n) be a statement about the integer n, and let n_0 be a fixed starting integer. Suppose both of the following hold:
- Base case(s). P(n_0) is true (sometimes several consecutive base cases P(n_0), P(n_0+1), \ldots must be checked directly).
- Strong inductive step. For every integer k \ge n_0: if P(n_0), P(n_0+1), \ldots, P(k) are all true, then P(k+1) is also true.
Then P(n) is true for every integer n \ge n_0.
Rather than taking this as a second, separate axiom alongside the Principle of Mathematical Induction, it can be built from that ordinary principle directly — the only genuinely new idea is what statement to induct on.
Given P(n) satisfying strong induction's two hypotheses, define a new statement Q(n): "P(n_0), P(n_0+1), \ldots, P(n) are all true." Q(n_0) holds because that's exactly the base case. And if Q(k) holds — every one of P(n_0) through P(k) is true — then the strong inductive step says P(k+1) is true too, so Q(k+1) (everything through P(k+1)) holds as well. That's the base case and inductive step of the ordinary Principle of Mathematical Induction, applied to Q instead of P — so Q(n) is true for every n \ge n_0. Since Q(n) includes P(n) as one of its conjuncts, P(n) is true for every n \ge n_0 too.
Theorem
The Well-Ordering Principle
Recalled from Discrete Mathematics I — Logic, Proof, and Structure · The well-ordering principle — first taught there.
Every nonempty subset of \mathbb{N} (or, more generally, every nonempty set of integers bounded below) has a least element.
This principle is taken as a foundational property of the natural numbers, not derived from something more basic in this course — it is equivalent to the Principle of Mathematical Induction, and either one can be taken as the starting axiom with the other proved from it.
Sketch of the equivalence. Suppose the Principle of Mathematical Induction holds, and let S be a nonempty set of natural numbers with no least element. Let P(n) be the statement "0, 1, \ldots, n are all not in S." P(0) holds, since if 0 \in S it would trivially be the least element. If P(k) holds (none of 0 through k are in S) and k+1 \in S, then k+1 would be S's least element, contradicting the assumption — so k+1 \notin S either, giving P(k+1). By induction, P(n) holds for every n, meaning no natural number is ever in S — contradicting S nonempty. So every nonempty S must have a least element after all.
Confirm both obligations for a divisibility claim
Confirm the base case and inductive step for: 3 divides 4 to the n minus 1, for every integer n >= 0.
Loading interactive…
Test a pattern before trusting it enough to induct
The claim: for every integer n from 0 to 6, 2 to the n minus 1 is prime. Find the n that breaks it.
Loading interactive…
Worked example
Weak induction: 3 divides 4^n - 1
-
1
Prove that 3 \mid (4^n - 1) for every integer n \ge 0.
-
2
Base case n=0: 4^0 - 1 = 0, and 3 \mid 0.
-
3
Inductive step: assume 4^k - 1 = 3m for some integer m. Then 4^{k+1} - 1 = 4\cdot 4^k - 1 = 4(3m+1) - 1 = 12m + 3 = 3(4m+1).
-
4\boxed{3 \mid (4^{k+1}-1), \text{ so the claim holds for every } n \ge 0}
Chapter 3 revisits exactly this kind of statement when it studies powers of a fixed residue modulo n — the pattern that repeats there is provable the same way.
Worked example
Strong induction: every integer n >= 2 is prime or a product of primes
-
1
Prove that every integer n \ge 2 is either prime or a product of primes.
-
2
Base case n=2: 2 is itself prime, so the claim holds.
-
3
Strong inductive step: assume the claim holds for every integer from 2 through k. If k+1 is prime, done. If not, k+1 = ab with 2 \le a,b \le k, and by the strong hypothesis each of a and b is prime or a product of primes.
-
4\boxed{k+1 = ab \text{ is then a product of primes too, completing the step}}
This is exactly why every prior case, not just k, needed to be available — knowing only that k factors as prime or a product of primes says nothing about a or b, which are both smaller than k+1 but not necessarily equal to k.
Loading interactive…
Where this goes next
Chapter 2: Basic group concepts
The exponent laws for a group element are proved by ordinary induction on the exponent, one factor of a at a time: a^m a^n = a^{m+n} and (a^m)^n = a^{mn} for positive integers m,n. Nothing about the proof changes once a stops being a number and starts being a general group element. The induction never looks inside a at all.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
The inductive hypothesis in an induction proof is...
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The inductive hypothesis is trusted and reused directly inside the inductive step's derivation.
From Discrete Mathematics I — Logic, Proof, and Structure
What are the two obligations of an induction proof?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Induction rests on exactly two parts: establishing the starting case and the step that carries it forward forever.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
Why is it never wrong to use strong induction even when weak induction would suffice?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A strong hypothesis includes the weak one as a special case, so nothing is lost by assuming more than strictly needed.
From Discrete Mathematics I — Logic, Proof, and Structure
In the prime-factorization proof, what does case 2 (k+1 composite) rely on from the strong hypothesis?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Both smaller factors need their own factorizations, supplied by the strong hypothesis covering all values up to k.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
Is the well-ordering principle logically equivalent to the principle of mathematical induction?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The two principles are equivalent ways of stating the same fundamental fact about the natural numbers.
From Discrete Mathematics I — Logic, Proof, and Structure
Why does 'assume a least counterexample exists' only work for claims about natural numbers, not positive reals?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The whole technique depends on well-ordering, which holds for the naturals but fails for the reals.