MGU Mathematics Series — Discrete Mathematics

Part II: Proof, Induction, and Number Structures

Base Cases · Inductive Steps · Recursive Definitions · Algorithms

Chapter 5 of 14

MGU Mathematics Series · Discrete Mathematics · Library Textbook Edition

Chapter 5:
Mathematical Induction
and Recursion

Proving claims for all whole numbers, defining sequences and algorithms step by step, and understanding why induction and recursion are mirror images of each other

■ Part II: Proof, Induction, and Number Structures ■

■ 14 Sections • Chapter 5 of 14 ■

Follows Chapter 4: Methods of Proof · Prepares students for Chapter 6: Integers, Divisibility, and Modular Arithmetic

Chapter 5 — Front Matter

Purpose and Overview

This chapter introduces one of the most important proof methods in all of mathematics: mathematical induction. Induction is the tool mathematicians use when a claim is stated for every whole number — not just one particular number, but infinitely many of them. Because no proof can list infinitely many cases, induction provides a structured argument that handles all of them at once.

Alongside induction, this chapter introduces recursion: the technique of defining something by referring back to smaller versions of itself. Induction and recursion are mirror images of each other. Induction proves claims that unfold step by step. Recursion defines objects by building them step by step. Together, they give students essential tools for reasoning about sequences, algorithms, structures that grow, and any process that repeats in a systematic pattern.

This chapter remains algebra-based throughout. It draws on sums, divisibility, inequalities, sequences, and function notation. No limits, derivatives, or integrals are needed.

Opening Question

Suppose someone claims: “No matter how many times you add the first n odd numbers together, the result is always a perfect square.” You can check a few cases: 1 = 1², (1+3) = 4 = 2², (1+3+5) = 9 = 3², (1+3+5+7) = 16 = 4². The pattern seems clear. But checking four cases does not prove the claim for every whole number n. There are infinitely many values of n. How can you prove a claim about all of them at once? Mathematical induction answers this question. By the end of this chapter, you will be able to prove this claim — and many others like it — with complete rigor.

14Sections

9Objectives

14Key Terms

12+Worked Examples

Learning Objectives

1Explain why ordinary verification of examples is not sufficient to prove a claim for all whole numbers.
2Identify statements that are candidates for proof by induction.
3Write a complete proof by mathematical induction, including a base case, inductive hypothesis, and inductive step.
4Apply strong induction to problems where the inductive step depends on more than one prior case.
5Write and interpret recursive definitions of sequences, functions, and structures.
6Trace recursive algorithms on small inputs.
7Explain the relationship between induction and recursion.
8Prove summation identities, divisibility claims, and simple inequalities using induction.
9Identify and avoid common mistakes in induction proofs.

Chapter 5 — Contents

Sections at a Glance

5.1Why Induction Is NeededLimits of verification; infinite claims; the domino argument; why checking cases is never enough
5.2Statements Indexed by Whole NumbersThe P(n) notation; recognizing induction-suitable claims; summations, divisibility, inequalities
5.3Base CasesWhat a base case is; why it is required; choosing the right starting value; direct verification
5.4Inductive HypothesesAssuming P(k); writing the hypothesis in full; why this is not circular reasoning
5.5Inductive StepsProving P(k+1) from P(k); using the hypothesis; algebraic techniques; worked summation example
5.6Writing a Complete Induction ProofSix-step structure; proof of the odd-number sum identity; the QED convention
5.7Strong InductionWhen ordinary induction is insufficient; assuming all prior cases; Fibonacci-type sequences
5.8Recursive DefinitionsBase cases and recursive rules; factorial; powers; what makes a definition complete
5.9Recursive SequencesRecurrence relations; the Fibonacci sequence; computing terms; proposing and verifying closed forms
5.10Recursion in AlgorithmsRecursive algorithm structure; base and recursive cases; tracing the factorial algorithm
5.11Structural Recursion as an IntroductionRecursive structures; lists; arithmetic expressions; compilers; data structures
5.12Induction in Sums, Patterns, and DivisibilitySum of squares; inequality proof; divisibility proof; three complete worked examples
5.13Common Induction and Recursion MistakesSix recurring errors; the all-horses paradox; why inductive steps must be checked at small values
5.14Preparing for Counting and CombinatoricsBridge to Part III; induction in combinatorial identities; recursion in algorithms and data structures

Section 5.1

Why Induction Is Needed

In mathematics, a claim about numbers often takes a general form: it says something is true not just for one specific number, but for all whole numbers, or for all integers greater than some starting value. No finite collection of examples proves a claim for all values. There is always the possibility that the pattern breaks down at some large, unchecked value of n.

Mathematical induction is the proof technique designed for exactly this situation. Rather than checking cases one by one, induction proves the claim by showing two things: (1) the claim is true for the first value, and (2) whenever the claim is true for some value n = k, it must also be true for the next value n = k+1. If both hold, the claim is true for every value — because it holds at the start, and once it holds anywhere, it must hold at the next step, and the next, without end.

Three Claims That Require Induction

Claim A. For every positive integer n, the sum of the first n odd numbers equals n².

Claim B. For every integer n ≥ 0, the number 2⊃n > n.

Claim C. For every integer n ≥ 1, the number 6⊃n − 1 is divisible by 5.

The Domino Argument

The most vivid way to understand why induction works is the domino analogy. Imagine an infinite row of dominoes, one for each whole number. To guarantee a chain reaction, you need exactly two things: the first domino falls (base case), and whenever any domino falls, the next one falls too (inductive step). If both conditions hold, every domino eventually falls — even the ones you never touched directly. Induction works exactly the same way.

Key Insight

You do not prove the claim for infinitely many cases directly. You prove a structural connection: if one case holds, then the next must hold. Combined with the starting point, this forces every case to hold.

Section 5.2

Statements Indexed by Whole Numbers

A statement is suitable for induction when it can be written in the form P(n), where n ranges over whole numbers or integers starting from some value. The notation P(n) means “the statement P applied to the specific value n.”

Illustration 5.2.1

Reading P(n) notation

SetupLet P(n) be: “The sum of the first n positive odd numbers equals n².”
P(1)Sum of first 1 odd number = 1. Right side: 1² = 1. True.
P(2)1 + 3 = 4 = 2². True.
P(3)1 + 3 + 5 = 9 = 3². True.
GoalInduction proves P(n) is true for every positive integer n — not just the first several cases.

Claim Type	Description	Example
Summation formula	A closed form for a sum of n terms	1 + 2 + … + n = n(n+1)/2
Divisibility claim	An expression always divisible by a fixed number	5 \| (6⊃n − 1) for all n ≥ 1
Inequality	One expression is always larger than another	2⊃n ≥ n + 1 for all n ≥ 1
Sequence property	Every term of a recursive sequence satisfies a bound	Fibonacci terms satisfy F⊂n ≤ 2⊃n

Student Warning

Induction proves that a claim holds for every whole number starting from the base case. It does not automatically apply to all real numbers or all integers. Always check the stated domain before choosing your starting value.

Practice 5.1–5.2Concept Check

Explain in your own words why checking 1,000 specific cases does not prove a claim for all whole numbers.
For each of the following, write the statement P(n) and evaluate P(1), P(2), and P(3): (a) The sum of the first n even positive integers equals n(n+1). (b) For all n ≥ 1, 7 | (8⊃n − 1).
Which of the following statements has the form suitable for proof by induction? Explain your reasoning for each: (a) Every prime number greater than 2 is odd. (b) For all positive integers n, n² + n + 41 is prime. (c) For all n ≥ 0, 3 | (n³ − n).

Section 5.3

Base Cases

The base case is the first step of an induction proof. It proves that the claim P(n) is true for the smallest value in the domain — usually n = 1 or n = 0, but sometimes another starting value depending on what the claim asserts. The base case is not optional. Without it, the chain has no starting point and the argument collapses entirely. The base case must be checked directly, by substituting the specific value and verifying that the claim holds.

Example 5.3.1

Checking a base case

ProblemLet P(n) be: “The sum of the first n positive integers equals n(n+1)/2.” Verify the base case P(1).
ThinkSubstitute n = 1 on both sides and check for equality.
SolveLeft side (sum of first 1 integers): 1 Right side (formula at n = 1): 1·2/2 = 1
CheckBoth sides equal 1. P(1) is satisfied.

Answer: The base case P(1) holds.

Choosing the Right Base Case

If the claim says “for all n ≥ 2,” the base case is n = 2, not n = 1. If the claim says “for all n ≥ 0,” check n = 0. Read the stated domain first. Never skip this step, even when it seems trivially obvious — a missed base case invalidates the entire proof.

Section 5.4

Inductive Hypotheses

After establishing the base case, the next component is the inductive hypothesis. The inductive hypothesis is an assumption: you assume, temporarily, that the claim P(k) is true for some arbitrary but fixed value k in the domain.

Students often feel this is circular reasoning — you seem to be assuming the very thing you want to prove. However, this is not circular. The inductive hypothesis does not assume P(n) for all n. It assumes P(k) for a single, unspecified value k. The goal is then to prove that P(k+1) must also be true. This conditional structure — “if P(k), then P(k+1)” — is what gives induction its power.

Writing the Inductive Hypothesis

State the hypothesis in both words and symbols. For example:

“Assume that P(k) is true for some integer k ≥ 1. That is, assume that:”

1 + 2 + 3 + ··· + k = k(k+1)/2

The symbolic form is especially important because it is what you will use algebraically in the inductive step.

Section 5.5

Inductive Steps

The inductive step is the heart of the proof. Having assumed that P(k) is true, you must now prove that P(k+1) is true. This is a conditional proof: you are proving “if P(k), then P(k+1).” You are not proving P(k+1) from scratch — you are using the assumption P(k) as a tool. The most common technique is to start with the left side of P(k+1), manipulate it algebraically, and substitute the inductive hypothesis at the right moment.

Example 5.5.1

Inductive step for a summation identity

ClaimFor all positive integers n: 1 + 2 + 3 + ··· + n = n(n+1)/2
HypothesisAssume P(k): 1 + 2 + ··· + k = k(k+1)/2. We must show P(k+1): 1 + 2 + ··· + k + (k+1) = (k+1)(k+2)/2.
Solve 1 + 2 + ··· + k + (k+1) = [k(k+1)/2] + (k+1) ← inductive hypothesis = (k+1)[k/2 + 1] = (k+1) · (k+2)/2 = (k+1)(k+2)/2 ← right side of P(k+1) ✓
CheckThe inductive hypothesis was used exactly once. All algebraic steps are valid.

Conclusion: P(k+1) follows from P(k). The inductive step is complete.

Look for the Hypothesis

In the inductive step, you must use the inductive hypothesis somewhere. If you have not used it, you have not connected P(k) to P(k+1). Look for the moment when you substitute the inductive hypothesis expression into your work — this is the key link in the chain.

Section 5.6

Writing a Complete Induction Proof

A complete induction proof follows a standard six-step structure that should be written in full every time. Skipping components or combining them creates ambiguity and makes errors harder to detect.

The Six-Step Induction Structure

1. State the claim precisely, including the domain.

2. State the proof method: “We proceed by mathematical induction on n.”

3. Base case: Verify P(starting value) directly by substitution.

4. Inductive hypothesis: Assume P(k) for some k ≥ starting value, and write it out in full.

5. Inductive step: Prove P(k+1) using the inductive hypothesis.

6. Conclusion: State that by mathematical induction, P(n) holds for all n in the domain.

Complete Proof — Example 5.6.1

The sum of the first n odd numbers equals n²

Claim For every integer n ≥ 1: (2·1−1) + (2·2−1) + ··· + (2n−1) = n².

Method We proceed by mathematical induction on n.

Base Case (n = 1) The sum of the first 1 odd number is 2(1)−1 = 1. The right side is 1² = 1. Since both sides equal 1, P(1) holds.

Inductive Hypothesis Assume P(k) is true for some integer k ≥ 1. That is, assume:

(2\cdot1-1) + (2\cdot2-1) + \cdot\cdot\cdot + (2k-1) = k²

Inductive Step We must show P(k+1): the sum of the first k+1 odd numbers equals (k+1)².

Sum of first (k+1) odd numbers = [Sum of first k odd numbers] + (2(k+1)-1) = k² + (2k + 2 - 1) \leftarrow inductive hypothesis = k² + 2k + 1 = (k+1)² ✓

Conclusion By the principle of mathematical induction, for every positive integer n, the sum of the first n odd numbers equals n².

■

The QED Symbol

The solid square ■ (or Q.E.D., from the Latin quod erat demonstrandum) marks the end of a proof. It signals that the argument is complete. Use it consistently to close every formal proof you write.

Practice 5.3–5.6Writing Induction Proofs

Prove by induction: For all positive integers n, 1 + 2 + 3 + ··· + n = n(n+1)/2.
Prove by induction: For all integers n ≥ 1, 1 + 2 + 4 + 8 + ··· + 2⊃(n−1) = 2⊃n − 1.
For each proof below, identify whether the base case, inductive hypothesis, or inductive step (or more than one) contains an error: (a) A student verifies the base case n=1 for a claim stated “for all n ≥ 3.” (b) A student assumes P(k+1) midway through proving P(k+1). (c) A student carries out the inductive step without substituting the inductive hypothesis anywhere.

Section 5.7

Strong Induction

The form of induction described so far assumes P(k) to prove P(k+1). Sometimes the inductive step requires assuming not just P(k), but all of P(1), P(2), …, P(k) simultaneously. This more powerful form is called strong induction (also called complete induction). It is logically equivalent to ordinary induction but is often the more natural form to apply.

	Ordinary Induction	Strong Induction
Base case	Verify P(starting value)	Verify P(starting value); sometimes verify several
Hypothesis	Assume P(k) for a fixed k	Assume P(j) for all j with 1 ≤ j ≤ k
Goal	Prove P(k+1)	Prove P(k+1)
Use when	Step depends only on the immediately prior case	Step depends on two or more prior cases (e.g. Fibonacci)

Complete Proof — Example 5.7.1

Bounding a recursive sequence using strong induction

Claim Define a⊂1; = 1, a⊂2; = 3, and a⊂n; = a⊂(n−1); + a⊂(n−2); for n ≥ 3. Then a⊂n; ≤ 3⊃n for all n ≥ 1.

Method We proceed by strong induction on n.

Base Cases

n = 1: a\subset1; = 1 \leq 3\supset1 = 3. ✓ n = 2: a\subset2; = 3 \leq 3\supset2 = 9. ✓

Inductive Hypothesis Assume a⊂j; ≤ 3⊃j for every integer j with 1 ≤ j ≤ k, where k ≥ 2.

Inductive Step We must show a⊂(k+1); ≤ 3⊃(k+1).

a\subset(k+1); = a\subsetk; + a\subset(k-1); \leftarrow recursive definition \leq 3\supsetk + 3\supset(k-1) \leftarrow inductive hypothesis (j=k and j=k-1) = 3\supset(k-1)(3 + 1) = 4 \cdot 3\supset(k-1) \leq 9 \cdot 3\supset(k-1) \leftarrow since 4 \leq 9 = 3\supset2 \cdot 3\supset(k-1) = 3\supset(k+1) ✓

Conclusion By strong induction, a⊂n; ≤ 3⊃n for all integers n ≥ 1.

■

Student Warning — Two Base Cases Required

When the recurrence reaches back two steps (as in this example), two base cases must be verified. A student who checks only n = 1 leaves the step from n = 1 to n = 2 unsupported. Always match the number of base cases to the depth of the recurrence.

Practice 5.7Strong Induction

Let a⊂1; = 1, a⊂2; = 2, and a⊂n; = a⊂(n−1); + a⊂(n−2); for n ≥ 3. Prove by strong induction that a⊂n; ≤ 2⊃n for all n ≥ 1.
Suppose P(1) and P(2) are both true, and that for all k ≥ 2, P(k−1) and P(k) together imply P(k+1). Explain why P(n) holds for all positive integers n.
Let b⊂1; = 1, b⊂2; = 3, and b⊂n; = 2b⊂(n−1); + b⊂(n−2); for n ≥ 3. Compute b⊂3;, b⊂4;, b⊂5;. Then prove by strong induction that b⊂n; ≤ 5⊃n for all n ≥ 1.

Section 5.8

Recursive Definitions

A recursive definition defines an object by specifying a base case (one or more explicitly given values) and a recursive rule (how to compute or construct later values from earlier ones). Recursive definitions appear in mathematics, programming, linguistics, data structures, and logic. They define objects not all at once but step by step, building on what has already been established.

Factorial — A Recursive Definition

0! = 1 (base case) n! = n \cdot (n-1)! for n \geq 1 (recursive rule)

Example 5.8.1

Computing 5! using the recursive definition

ThinkApply the recursive rule until the base case is reached, then unwind from the inside out.
Solve 5! = 5 · 4! = 5 · 4 · 3! = 5 · 4 · 3 · 2! = 5 · 4 · 3 · 2 · 1! = 5 · 4 · 3 · 2 · 1 · 0! = 5 · 4 · 3 · 2 · 1 · 1 = 120
CheckThe recursion bottoms out at the base case 0! = 1. Multiplications then resolve from the inside out.

Answer: 5! = 120

Powers — A Recursive Definition

a\supset0 = 1 (base case) a\supsetn = a \cdot a\supset(n-1) for n \geq 1 (recursive rule)

Student Warning

Recursive definitions always require both a base case and a recursive rule. Without the base case, the recursion has no stopping point. Without the recursive rule, the definition is incomplete. Never omit either component.

Section 5.9

Recursive Sequences

A recursive sequence is a sequence in which each term is defined in terms of one or more previous terms. The recursive rule is often called a recurrence relation. To compute terms of a recursive sequence, you must start at the base case and work forward; you cannot skip ahead without computing all intermediate values because each term depends on prior ones.

The Fibonacci Sequence

F\subset1; = 1, F\subset2; = 1, F\subsetn; = F\subset(n-1); + F\subset(n-2); for n \geq 3

First several terms: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … Each term is the sum of the two before it. The Fibonacci sequence appears in nature, art, computer science, and combinatorics. Because it requires two prior terms, strong induction (Section 5.7) is the natural tool for proving properties about it.

Example 5.9.1

Computing terms of a recurrence

ProblemLet a⊂1; = 2 and a⊂n; = 3a⊂(n−1); − 1 for all n ≥ 2. Compute a⊂1; through a⊂5;.
Solve a⊂1; = 2 a⊂2; = 3(2) − 1 = 5 a⊂3; = 3(5) − 1 = 14 a⊂4; = 3(14) − 1 = 41 a⊂5; = 3(41) − 1 = 122

Answer: 2, 5, 14, 41, 122

Example 5.9.2

Verifying a proposed closed form

ProblemThe sequence above has proposed closed form a⊂n; = (3⊃n + 1)/2. Verify for n = 1, 2, 3.
Solve n=1: (3⊃1 + 1)/2 = 4/2 = 2 = a⊂1; ✓ n=2: (3⊃2 + 1)/2 = 10/2 = 5 = a⊂2; ✓ n=3: (3⊃3 + 1)/2 = 28/2 = 14 = a⊂3; ✓
NoteVerification of three cases supports the formula but does not prove it. A complete proof by induction is left as an exercise.

Answer: The proposed closed form matches all three checked terms.

Section 5.10

Recursion in Algorithms

Recursive thinking is fundamental to algorithm design. A recursive algorithm calls itself on a smaller input. To avoid infinite loops, every recursive algorithm must have one or more base cases that are solved directly, and one or more recursive cases that reduce the problem toward the base case. The proof that a recursive algorithm terminates is itself an induction argument: identify a quantity that strictly decreases with each call and cannot decrease below the base case.

Example 5.10.1

Recursive factorial algorithm — pseudocode and trace

Algorithm Algorithm Factorial(n): Input: A non-negative integer n Output: The value n! if n = 0 then return 1 ← base case else return n × Factorial(n − 1) ← recursive case
TraceRunning Factorial(4) — see table below.

Call	n	Returns
Factorial(4)	4	4 × Factorial(3)
Factorial(3)	3	3 × Factorial(2)
Factorial(2)	2	2 × Factorial(1)
Factorial(1)	1	1 × Factorial(0)
Factorial(0)	0	1 (base case)

Resolving outward: Factorial(1)=1, Factorial(2)=2, Factorial(3)=6, Factorial(4)=24

Answer: Factorial(4) = 24 = 4!

The Waiting Chain

Each recursive call waits for the smaller call to finish before it can complete. Calls chain inward to the base case, then results unwind outward to the original call. This is the universal pattern of recursive algorithm execution.

Section 5.11

Structural Recursion as an Introduction

Mathematical recursion extends beyond sequences and numbers. It also applies to structures: trees, lists, expressions, and other objects that are built from smaller instances of themselves. This idea is called structural recursion.

A list of numbers is either the empty list (base case), or a number followed by another list (recursive case). An arithmetic expression is either a single number (base case), or two expressions joined by an operation such as +, −, ×, or ÷ (recursive case). The expression (3 + 4) × (7 − 2) is built by combining (3 + 4) and (7 − 2) using ×. Each piece is itself an expression built from smaller pieces, eventually reaching individual numbers.

Compilers and interpreters for programming languages use structural recursion to parse, evaluate, and transform programs. Every time code is compiled, recursive structure processing happens behind the scenes. Properties of these structures are proved by structural induction, which follows the same two-step pattern as ordinary induction.

MGU Library Connection

Structural recursion and recursive data structures appear in the MGU Computer Science sequence, including data structures (trees, linked lists, grammars) and compilers.
The mathematical foundations introduced here carry directly into those topics.
See also: Chapter 10 (Graph Theory Foundations) and Chapter 11 (Trees and Network Optimization) for recursive tree structures and proof.

Practice 5.8–5.11Recursion and Algorithms

Write a recursive definition for the sequence a⊂n; = 2n for n ≥ 1.
Define c⊂1; = 1, c⊂n; = c⊂(n−1); + 2 for n ≥ 2. Compute c⊂1; through c⊂6;. Propose a closed form and verify it for n = 1, 2, 3.
Write a recursive algorithm for computing 1⊃2 + 2⊃2 + ··· + n⊃2 for a positive integer n. Trace the algorithm for n = 4.
A recursive algorithm Mystery(n) is defined as: if n = 0, return 0; else return n + Mystery(n−1). (a) Trace Mystery(5). (b) What does Mystery(n) compute? (c) Prove your answer using induction.
Explain in your own words why a recursive algorithm that never reaches a base case will run forever. What structural property guarantees termination?

Section 5.12

Induction in Sums, Patterns, and Divisibility

This section presents three complete induction proofs across three important categories. Each example illustrates the full six-step structure applied to a different type of claim. Study each proof as a model before attempting the exercises.

Summation Formulas

Complete Proof — Example 5.12.1

Sum of squares formula

Claim For every positive integer n: 1² + 2² + 3² + ··· + n² = n(n+1)(2n+1)/6

Base Case (n = 1) Left side: 1² = 1. Right side: 1·2·3/6 = 1. ✓

Inductive Hypothesis Assume for some integer k ≥ 1:

1² + 2² + \cdot\cdot\cdot + k² = k(k+1)(2k+1)/6

Inductive Step We must show the formula holds for k+1:

1² + 2² + \cdot\cdot\cdot + k² + (k+1)² = k(k+1)(2k+1)/6 + (k+1)² \leftarrow inductive hypothesis = (k+1)[k(2k+1)/6 + (k+1)] = (k+1)[k(2k+1) + 6(k+1)] / 6 = (k+1)[2k² + k + 6k + 6] / 6 = (k+1)[2k² + 7k + 6] / 6 = (k+1)(k+2)(2k+3) / 6 ✓

Conclusion By mathematical induction, the sum-of-squares formula holds for all positive integers n.

■

Inequalities

Complete Proof — Example 5.12.2

Proving an inequality by induction

Claim For every integer n ≥ 1: 2⊃n ≥ n + 1.

Base Case (n = 1) 2⊃1 = 2 ≥ 1 + 1 = 2. True (equality holds). ✓

Inductive Hypothesis Assume 2⊃k ≥ k + 1 for some integer k ≥ 1.

Inductive Step We must show 2⊃(k+1) ≥ k + 2.

2\supset(k+1) = 2 \cdot 2\supsetk \geq 2(k + 1) \leftarrow inductive hypothesis = 2k + 2 \geq k + 2 \leftarrow since k \geq 1 implies k \geq 0 ✓

Conclusion By mathematical induction, 2⊃n ≥ n + 1 for all integers n ≥ 1.

■

Divisibility

Complete Proof — Example 5.12.3

Divisibility claim by induction

Claim For every integer n ≥ 1: 5 | (6⊃n − 1). That is, 6⊃n − 1 is divisible by 5.

Base Case (n = 1) 6⊃1 − 1 = 5 = 5 · 1. Divisible by 5. ✓

Inductive Hypothesis Assume 5 | (6⊃k − 1) for some k ≥ 1. Write 6⊃k − 1 = 5m for some integer m, so 6⊃k = 5m + 1.

Inductive Step We must show 5 | (6⊃(k+1) − 1).

6\supset(k+1) - 1 = 6 \cdot 6\supsetk - 1 = 6(5m + 1) - 1 \leftarrow substituting 6\supsetk = 5m + 1 = 30m + 6 - 1 = 30m + 5 = 5(6m + 1) ✓ (6m+1 is an integer)

Conclusion By mathematical induction, 5 | (6⊃n − 1) for all integers n ≥ 1.

■

Section 5.13

Common Induction and Recursion Mistakes

Mistake 1 — Omitting the Base Case

"The base case is obvious — I'll skip straight to the inductive step."

Always verify the base case directly. Substitute the starting value and check the claim explicitly. A proof missing the base case is formally invalid, even if the inductive step is entirely correct.

Mistake 2 — Proving the Wrong Statement

Writing out P(k) again in the inductive step instead of P(k+1).

Before beginning the inductive step, write out in full exactly what P(k+1) says. Keep this target statement visible as you work.

Mistake 3 — Circular Reasoning

Using the statement P(k+1) in the middle of proving P(k+1).

The inductive step allows you to assume P(k), not P(k+1). If you find yourself using the conclusion you are trying to prove, stop and reconsider your approach entirely.

Mistake 4 — Not Using the Inductive Hypothesis

Completing the inductive step without referencing P(k) anywhere.

Check that the inductive hypothesis appears somewhere in your reasoning. Without it, the argument has not connected P(k) to P(k+1) and is missing its essential link.

Mistake 5 — Missing Base Cases in Strong Induction

Checking only n = 1 for a recurrence that depends on two prior terms.

When the recursive rule reaches back two steps (like Fibonacci), verify both n = 1 and n = 2. Match the number of base cases to the depth of the recurrence.

Mistake 6 — Infinite Recursion

A recursive definition or algorithm has no path to the base case.

Before finalizing any recursive algorithm, ask: what is the base case, and does every recursive call make the problem strictly smaller (closer to the base case)?

A Famous Fallacy: All Horses Are the Same Color

A well-known faulty argument claims to “prove” that all horses are the same color using induction. The base case is valid (a set of 1 horse trivially has all horses the same color), and the inductive step sounds plausible: remove one horse from a group of k+1, the remaining k share a color by hypothesis, put that horse back and remove a different one — the remaining k again share a color, so all k+1 horses share a color.

The error appears precisely at k = 1 (the step from n = 1 to n = 2). When k = 1, removing one horse and then a different horse gives two disjoint single-horse sets with no overlap. The two horses are never in the same group of k, so the inductive hypothesis cannot link their colors. The argument only works when k ≥ 2, because only then do the two overlapping groups share at least one horse in common.

This puzzle shows that an argument can sound like induction, have a valid base case, and a plausible inductive step — and still be wrong. The inductive step must be checked carefully, especially at small values of k. Never wave your hand at the inductive step and assume it works.

Section 5.14

Preparing for Counting and Combinatorics

Mathematical induction will reappear throughout this textbook. In Chapter 6, it will be used to prove divisibility results in number theory. In Chapters 7, 8, and 9, it will appear in proofs of combinatorial identities and counting formulas. In Chapter 11, it will appear in proofs about trees and graphs. In Chapter 12, it will appear in the analysis of recursive algorithms.

Recursion is equally pervasive. Recursive sequences, recursive algorithms, recursive data structures, and recursive definitions of grammars and languages are central topics in computer science and discrete mathematics.

The connection between induction and recursion is fundamental. Induction proves properties of recursively defined objects. Recursion defines the objects that induction proves things about. As you move into counting and combinatorics in Part III, watch for induction in the background: it underlies many of the formulas you will use, and understanding why those formulas are true — not just how to use them — depends on exactly the proof techniques practiced in this chapter.

MGU Library Connection — Bridge to Computer Science and Higher Mathematics

Algorithm correctness: nearly every correctness proof for a recursive algorithm is an induction proof on the structure of inputs.
Termination proofs: the well-ordering principle applied to a strictly decreasing measure on recursive calls.
Recursive data structures: trees, linked lists, and grammars — all defined structurally, all proved inductively.
Asymptotic analysis: Chapter 12 introduces recurrences for divide-and-conquer algorithms; solving and verifying them uses induction directly.
Cryptography: properties of prime numbers and modular arithmetic established in Chapter 6 rely on inductive arguments.
Artificial intelligence foundations: recursive grammars, tree-structured data, and probabilistic graphical models all rest on recursive definitions proved by induction.

Chapter 5 — Back Matter

Chapter Summary

Sec 5.1Induction is needed because no finite collection of examples proves a claim for all whole numbers. The domino argument explains why: a base case plus a chain reaction covers every case.
Sec 5.2The P(n) notation frames a general claim as a family of statements indexed by n. Induction is suited for summation formulas, divisibility claims, inequalities, and sequence properties.
Sec 5.3The base case verifies P(n⊂0;) directly by substitution. It must match the stated domain. It is never optional and should always be written out explicitly, even when it seems trivial.
Sec 5.4The inductive hypothesis assumes P(k) for an arbitrary fixed k. This is not circular reasoning: it assumes one case, then proves the next. Write the hypothesis in full, in both words and symbols.
Sec 5.5The inductive step derives P(k+1) from P(k). The inductive hypothesis must appear somewhere. Start from the expression for P(k+1), manipulate algebraically, and substitute the hypothesis when the relevant sum or expression appears.
Sec 5.6A complete induction proof states the claim, declares the method, verifies the base case, states the hypothesis, proves the inductive step, and states the conclusion. The ■ symbol marks the end.
Sec 5.7Strong induction assumes P(j) for all j ≤ k, not just j = k. It is needed when the recurrence reaches back more than one step. Multiple base cases are typically required.
Sec 5.8Recursive definitions specify base cases and a recursive rule. Factorial and powers are canonical examples. Both components are required; either missing renders the definition incomplete.
Sec 5.9Recurrence relations define each term from prior terms. Computing requires starting at the base and working forward. A closed form computes the n-th term directly; verifying it for several cases supports but does not prove it.
Sec 5.10Recursive algorithms call themselves on smaller inputs and bottom out at base cases. Tracing a call on a small input shows how the chain of waiting calls resolves from the base case outward.
Sec 5.11Structural recursion defines objects such as lists and expressions by their construction from smaller instances. Compilers use structural recursion to process code. Structural induction proves properties of these objects.
Sec 5.12Three complete proofs: sum of squares (summation), 2⊃n ≥ n+1 (inequality), and 5|(6⊃n−1) (divisibility). Each illustrates the full six-step induction structure applied to a different type of claim.
Sec 5.13Six common mistakes: skipping the base case, proving the wrong statement, circular reasoning, not using the hypothesis, insufficient base cases in strong induction, and infinite recursion. The all-horses paradox shows that inductive steps must be scrutinized at small values of k.
Sec 5.14Induction and recursion appear throughout the remainder of this book: number theory, counting, graphs, trees, algorithms, and complexity. They are companion tools — one proves, the other defines — and both are central to computing and higher mathematics.

Key Terms Review

base case

The starting value at which the claim P(n) is verified directly, establishing the foundation of an induction proof.

closed form

A formula that computes the n-th term of a sequence directly, without requiring prior terms to be computed first.

domino argument

An analogy for induction: if the first domino falls and each falling domino knocks the next, every domino eventually falls.

Fibonacci sequence

The recursive sequence F⊂1;=1, F⊂2;=1, F⊂n;=F⊂(n−1);+F⊂(n−2);, appearing widely in mathematics, nature, and computing.

inductive hypothesis

The assumption that P(k) holds for a fixed but arbitrary k, used as a tool to prove P(k+1) in the inductive step.

inductive step

The part of an induction proof in which P(k+1) is derived from the inductive hypothesis P(k).

mathematical induction

A proof method for claims of the form “for all n ≥ n⊂0;, P(n) holds,” consisting of a base case and an inductive step.

recurrence relation

A rule that defines each term of a sequence in terms of one or more earlier terms.

recursion

Defining or computing something by referring to smaller instances of the same object or process.

recursive definition

A definition consisting of one or more base cases and a recursive rule that builds later objects from earlier ones.

recursive sequence

A sequence in which each term is defined by a recurrence relation applied to one or more prior terms.

structural recursion

Recursive definitions and proofs that operate on the structure of an object such as a list or expression tree, rather than on an integer index.

strong induction

A form of induction in which the inductive hypothesis assumes the claim for all prior values, not just the immediately preceding one.

well-ordering principle

Every non-empty set of non-negative integers has a smallest element; this principle underlies the validity of mathematical induction.