Induction and construction

This chapter introduces foundational proof techniques, including mathematical and strong induction, alongside recursive construction methods. These tools are indispensable for rigorously demonstrating properties of sequences, sets, and algorithms, representing core competencies frequently examined in CMI assessments. Mastery of these concepts is crucial for success in advanced topics in logic and discrete mathematics.

---

Chapter Contents

| Topic |

|---|-------| | 1 | Mathematical induction | | 2 | Strong induction | | 3 | Recursive construction | | 4 | Existence examples |

---

We begin with Mathematical induction.

Part 1: Mathematical induction

Mathematical Induction

Overview

Mathematical induction is one of the most fundamental proof methods in mathematics. It is used to prove statements indexed by the natural numbers. In exam problems, induction is not just a formal ritual: the real skill is identifying the exact statement to prove, choosing the right base case, and writing the induction step so that the hypothesis is used meaningfully. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Understand the logic behind induction.

Write a correct induction proof with clear base case and induction step.

Distinguish between verifying examples and proving all cases.

Use induction in identities, inequalities, divisibility, and recursive formulas.

Avoid common induction errors such as incomplete hypotheses or wrong starting index.

---

Core Idea

📖 Mathematical Induction

Suppose $P(n)$ is a statement depending on a natural number $n$ .

To prove that $P(n)$ is true for all integers $n \ge n_0$ , it is enough to show:

Base case: $P(n_0)$ is true.

Induction step: For every integer $k \ge n_0$ , if $P(k)$ is true, then $P(k+1)$ is true.

Then

P(n)

is true for all

n \ge n_0

❗ Why It Works

Induction works like a row of dominos:

the base case knocks down the first domino

the induction step shows each domino knocks down the next one

So all dominos from the starting point onward fall.

---

Standard Structure of an Induction Proof

📐 Template

To prove $P(n)$ for all $n \ge n_0$ :

Step 1: Base case

Show that $P(n_0)$ is true.

Step 2: Induction hypothesis

Assume $P(k)$ is true for some arbitrary $k \ge n_0$ .

Step 3: Induction step

Using the induction hypothesis, prove $P(k+1)$ .

Step 4: Conclusion

Therefore, by mathematical induction, $P(n)$ holds for all $n \ge n_0$ .

---

Typical Forms of Statements Proved by Induction

📐 Common Types

Sums:

\qquad 1+2+\cdots+n = \dfrac{n(n+1)}{2}

Divisibility:

\qquad 7^n-1

is divisible by

6

Inequalities:

\qquad 2^n \ge n+1

Recursive formulas:

proving explicit formulas for recursively defined sequences

Structural statements:

about tilings, constructions, or combinatorial objects

---

Minimal Worked Example

Example Prove that

\qquad 1+2+\cdots+n = \dfrac{n(n+1)}{2}

for all

n \ge 1

. Base case: For

n=1

\qquad 1 = \dfrac{1\cdot 2}{2}=1

So the statement is true for

n=1

. Induction hypothesis: Assume for some

k \ge 1

that

\qquad 1+2+\cdots+k = \dfrac{k(k+1)}{2}

Induction step: Then $\qquad 1+2+\cdots+k+(k+1) = \dfrac{k(k+1)}{2} + (k+1)$ $\qquad = \dfrac{k(k+1)+2(k+1)}{2} = \dfrac{(k+1)(k+2)}{2}$ which is exactly the required formula for

k+1

. Hence the result holds for all

n \ge 1

. ::: ---

Choosing the Right Base Case

❗ Base Case Must Match the Statement

If the claim starts from $n \ge 0$ , then check $n=0$ .
If the claim starts from $n \ge 1$ , then check $n=1$ .
If the recursion or expression only makes sense from a later value, start there.

A wrong base case can invalidate an otherwise correct-looking proof.

---

Induction in Inequalities

💡 Extra Care with Inequalities

When proving inequalities by induction:

write exactly what is assumed at stage $k$

transform the left side of the $k+1$ case

use the induction hypothesis at the correct point

justify any extra estimate used after that

Do not assume that “bigger

n

makes it obvious.” The argument must still be written.

---

Induction and Divisibility

📐 Standard Divisibility Pattern

To prove a divisibility statement like

$\qquad a_n \text{ is divisible by } d$

the induction step often looks like:

rewrite $a_{k+1}$ in terms of $a_k$

use the induction hypothesis that $d \mid a_k$

show the remaining terms are also divisible by $d$

---

Common Mistakes

⚠️ Avoid These Errors

❌ Checking only a few examples and calling it a proof

✅ Induction requires a general induction step

❌ Forgetting to state the induction hypothesis clearly

✅ Say exactly what is being assumed for

k

❌ Proving $P(k+1)$ from itself instead of from $P(k)$

✅ The direction must be from hypothesis to next case

❌ Using the wrong starting value

✅ Match the base case to the actual domain

❌ Concluding the proof without saying induction applies

✅ Write the final conclusion properly

---

CMI Strategy

💡 How to Attack Induction Problems

Identify the precise statement $P(n)$ .

Check the smallest allowed value carefully.

In the induction step, write the $k+1$ case explicitly.

Substitute the induction hypothesis only where it naturally fits.

Simplify until the target form appears.

---

Practice Questions

:::question type="MCQ" question="In a standard induction proof, after the base case one usually assumes" options=["

P(k+1)

is true","

P(k)

is true for an arbitrary

k

in the domain","

P(n)

is true for all

n

","the result is obvious"] answer="B" hint="Think about the induction hypothesis." solution="In standard induction, after verifying the base case, we assume

P(k)

is true for an arbitrary allowed integer

k

and then prove

P(k+1)

. Hence the correct option is

\boxed{B}

." ::: :::question type="NAT" question="For the statement

1+2+\cdots+n=\dfrac{n(n+1)}{2}

, what is the left-hand side when

n=4

?" answer="10" hint="Add the first four positive integers." solution="For

n=4

, the left-hand side is

\qquad 1+2+3+4 = 10

Hence the answer is

\boxed{10}

." ::: :::question type="MSQ" question="Which of the following are essential parts of a standard induction proof?" options=["Base case","Induction hypothesis","Induction step","Checking only three numerical examples"] answer="A,B,C" hint="Think of the formal structure of induction." solution="A valid induction proof requires:

a base case,

an induction hypothesis,

an induction step.

Checking only a few examples is not a proof. Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="Prove by induction that

2^n \ge n+1

for all integers

n \ge 0

." answer="Use induction on

n

." hint="Write the

(k+1)

case as

2^{k+1}=2\cdot 2^k

." solution="Let

P(n)

be the statement

\qquad 2^n \ge n+1

for all

n \ge 0

. Base case: For

n=0

\qquad 2^0=1 \ge 1

P(0)

is true. Induction hypothesis: Assume that for some

k \ge 0

\qquad 2^k \ge k+1

Induction step: Then

\qquad 2^{k+1}=2\cdot 2^k \ge 2(k+1)=2k+2

Now

\qquad 2k+2 \ge k+2

for all

k \ge 0

. So

\qquad 2^{k+1} \ge k+2

which is exactly

P(k+1)

. Hence by mathematical induction,

\qquad 2^n \ge n+1

for all integers

n \ge 0

." ::: ---

Summary

❗ Key Takeaways for CMI

Mathematical induction proves statements indexed by integers.

It consists of base case, induction hypothesis, and induction step.

The induction step must genuinely use the hypothesis.

Induction is a proof for infinitely many cases, not repeated verification.

Clear writing and correct starting index are essential.

---

💡 Next Up

Proceeding to Strong induction.

---

Part 2: Strong induction

Strong Induction

Overview

Strong induction is a variant of induction where, in the induction step, one may assume the statement for all earlier values up to $k$ , not just for

k

alone. This is extremely useful when the proof of the next case depends on several smaller cases rather than only the immediately previous one. In exam problems, strong induction appears naturally in factorisation, decomposition, recursive algorithms, and existence proofs. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

State and use strong induction correctly.

Recognise when ordinary induction is inconvenient but strong induction is natural.

Prove decomposition and factorisation statements.

Use strong induction in divisibility and recursive-structure problems.

Understand that strong induction is logically equivalent in power to standard induction.

---

Core Idea

📖 Strong Induction Principle

Let $P(n)$ be a statement for integers $n \ge n_0$ .

To prove $P(n)$ for all $n \ge n_0$ , it is enough to show:

Base case: $P(n_0)$ is true.

Strong induction step: For every $k \ge n_0$ , if

\qquad P(n_0),P(n_0+1),\dots,P(k)

are all true, then

P(k+1)

is true.

Then

P(n)

holds for all

n \ge n_0

---

Why Strong Induction is Needed

❗ When One Previous Case is Not Enough

Some proofs of $P(k+1)$ use not just $P(k)$ , but some earlier case such as $P(k-2)$ or a decomposition into smaller parts.

Typical examples:

every integer $n\ge 2$ has a prime factorisation

every amount above some threshold can be formed from given denominations

recurrence relations using multiple earlier terms

In such cases, strong induction is often the natural method. ::: ---

Standard Structure of a Strong Induction Proof

📐 Template

To prove $P(n)$ for all $n \ge n_0$ :

Step 1: Base case(s)
Verify the first required case or cases.

Step 2: Strong induction hypothesis
Assume that $P(j)$ is true for all integers $j$ with
$\qquad n_0 \le j \le k$

Step 3: Prove the next case
Using this full collection of hypotheses, prove $P(k+1)$ .

Step 4: Conclude
Therefore, by strong induction, $P(n)$ holds for all $n \ge n_0$ .

---

Strong Induction vs Ordinary Induction

❗ Key Comparison

Ordinary induction assumes only $P(k)$ .

Strong induction assumes all earlier statements up to $k$ .

In terms of logical power, they are equivalent. But strong induction is often much easier to use in problems where the next step depends on multiple earlier steps.

---

Minimal Worked Example

Example Prove that every integer

n \ge 2

can be written as a product of primes. Base case: For

n=2

, the statement is true because

2

itself is prime. Strong induction hypothesis: Assume every integer

m

with

\qquad 2 \le m \le k

can be written as a product of primes. Induction step: Consider

k+1

If $k+1$ is prime, then it is already a product of primes.

If $k+1$ is composite, then

\qquad k+1 = ab

where

2 \le a,b \le k

. By the strong induction hypothesis, both

a

and

b

are products of primes. Therefore

k+1

is also a product of primes. Hence the statement holds for all

n \ge 2

. ::: This proof uses smaller cases below

k

, not just the case

k

itself. That is why strong induction fits naturally. ---

When Multiple Base Cases Are Needed

❗ Do Not Miss This

If the recursive structure depends on more than one starting value, then several base cases may be needed.

For example, if a claim about $n$ uses smaller cases $n-1$ and $n-2$ , then one base case may not be enough.

Always check the dependency pattern before deciding how many initial cases must be verified. ---

Common Applications

📐 Typical Strong-Induction Problems

prime factorisation

coin or postage construction problems

decomposition into smaller allowed pieces

recurrence proofs depending on many earlier terms

existence of tilings or representations

---

Common Mistakes

⚠️ Avoid These Errors

❌ Stating strong induction but using only vague assumptions

✅ Clearly state that all cases from the base up to

k

are assumed

❌ Proving $P(k+1)$ using a smaller case that was never included in the hypothesis

✅ Make the hypothesis range explicit

❌ Forgetting extra base cases when needed

✅ Check the recursive dependency pattern

❌ Thinking strong induction is a different kind of truth from ordinary induction

✅ It is a different proof format, not a different notion of proof validity

---

CMI Strategy

💡 How to Recognise Strong Induction

Ask:

Does the next case depend on several earlier cases?

Is the object decomposed into smaller pieces of variable size?

Do I need a hypothesis for all smaller values, not just the immediate predecessor?

If yes, strong induction is often the correct tool.

---

Practice Questions

:::question type="MCQ" question="In strong induction, the induction hypothesis usually assumes" options=["only

P(k)

","all earlier cases up to

k

","only the base case","nothing at all"] answer="B" hint="Think about the key difference from ordinary induction." solution="In strong induction, one assumes that the statement holds for all values from the starting point up to

k

, and then proves it for

k+1

. Hence the correct option is

\boxed{B}

." ::: :::question type="NAT" question="What is the smallest integer

n

for which the statement “every integer

n \ge 2

has a prime factorisation” begins?" answer="2" hint="Read the statement carefully." solution="The statement begins at the integer

\boxed{2}

. That is the first required base case." ::: :::question type="MSQ" question="Which of the following are true?" options=["Strong induction is useful when the next case depends on multiple earlier cases","Strong induction and ordinary induction are logically equivalent in strength","Strong induction never needs more than one base case","Prime factorisation is a standard example of strong induction"] answer="A,B,D" hint="Think about when strong induction is naturally used." solution="1. True.

True.

False. Some problems require multiple base cases.

True.

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="Using strong induction, prove that every integer

n \ge 2

can be expressed as a product of primes." answer="Use the prime/composite split in the induction step." hint="If

n

is composite, factor it into smaller integers and apply the hypothesis." solution="Let

P(n)

be the statement:

\qquad n \text{ can be expressed as a product of primes}

for all integers

n \ge 2

. Base case: For

n=2

, the statement is true because

2

is itself prime. Strong induction hypothesis: Assume that for some

k \ge 2

, every integer

m

with

\qquad 2 \le m \le k

can be expressed as a product of primes. Induction step: We prove

P(k+1)

. There are two cases:

k+1

is prime, then it is already a product of primes.

k+1

is composite, then

\qquad k+1 = ab

for integers

a,b

such that

\qquad 2 \le a,b \le k

By the strong induction hypothesis, both

a

and

b

can be expressed as products of primes. Therefore their product

ab = k+1

can also be expressed as a product of primes. So in either case,

P(k+1)

holds. Hence, by strong induction, every integer

n \ge 2

can be expressed as a product of primes." ::: ---

Summary

❗ Key Takeaways for CMI

Strong induction assumes all earlier cases up to $k$ .

It is especially useful when the next case depends on several smaller cases.

It is logically equivalent to ordinary induction but often more natural.

Multiple base cases may be necessary.

Prime factorisation is one of the most important standard applications.

---

💡 Next Up

Proceeding to Recursive construction.

---

Part 3: Recursive construction

Recursive Construction

Overview

Recursive construction is the method of building mathematical objects step by step, where each stage is created from earlier stages by a fixed rule. This topic is fundamental in logic, proof, combinatorics, algorithms, and discrete mathematics. In exam problems, the goal is often to show that an object exists for all sizes, or to describe how a valid object can be built inductively. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Understand what a recursive construction is.

Build objects step by step from smaller instances.

Use recursive construction to prove existence statements.

Distinguish between recursive definition and explicit description.

Combine recursive construction with induction proofs.

---

Core Idea

📖 Recursive Construction

A recursive construction describes how to create a mathematical object of size $n+1$ from one or more objects of smaller size.

The process usually has:

a base object

a rule for building larger objects from smaller ones

Examples:

build a sequence term by term

build tilings of boards

build binary strings of length $n$

build trees, paths, or combinatorial patterns

::: ---

Recursive Construction vs Recursive Definition

❗ Important Distinction

A recursive definition tells you how later objects depend on earlier ones.

A recursive construction actively shows how to build or generate the objects.

These are closely related, but in proof problems, recursive construction is usually more constructive and existence-oriented.

---

Standard Pattern

📐 Typical Recursive Construction Scheme

To construct objects of size $n$ recursively:

Base case: construct the object for the smallest size

Recursive step: assume you already have a valid construction for size $n$

Build size $n+1$ : modify or extend the existing object while preserving the required property

---

Why Recursive Construction Matters

❗ Main Uses

Recursive construction is often used to prove:

existence of an object for every $n$

a counting recurrence

correctness of an algorithm

structural properties of combinatorial objects

The reasoning is often:

“I know how to build the first one.”

“Whenever I can build one of size $n$ , I can build one of size $n+1$ .”

“Therefore I can build them for all $n$ .”

::: ---

Typical Examples

📐 Common Recursively Constructed Objects

Strings:

Build strings of length

n+1

by appending a symbol to strings of length

n

Tilings:

Tile a larger board by adding one more tile to a smaller valid tiling

Paths:

Extend a path of length

n

by one additional step

Graphs / trees:

Add one new vertex or edge while preserving the required property

Sets:

Define a family by specifying initial members and closure rules

---

Minimal Worked Example

Example Construct binary strings of length

n

recursively. Base case: For

n=1

, the valid binary strings are

\qquad 0,\ 1

Recursive step: Given all binary strings of length

n

, construct strings of length

n+1

by appending either

0

1

to each existing string. So every string of length

n+1

is obtained from a smaller one by one recursive step. This is a recursive construction. ::: ---

Recursive Construction and Induction

❗ How They Work Together

Recursive construction tells you how to build the object.

Induction proves that the construction works for all allowed sizes.

So in many problems:

recursive construction provides the idea

induction provides the proof

---

Structural Preservation

💡 The Most Important Question

In a recursive construction problem, always ask:

$\qquad \text{What property must remain true after each step?}$

When you enlarge the object:

what is added?

why does the required condition still hold?

what new condition must be checked?

This is often the heart of the proof. ::: ---

Common Construction Patterns

📐 Frequent Recursive Moves

append one symbol

attach one new block

split into smaller parts, then combine

remove a small part, solve recursively, then restore

add one new element and update the structure

---

Common Mistakes

⚠️ Avoid These Errors

❌ Describing only the base object but not the recursive rule

✅ A recursive construction needs both

❌ Giving a rule that does not preserve the required property

✅ Check preservation carefully

❌ Assuming the larger object is valid without verifying the added part

✅ Every recursive step must be justified

❌ Confusing “can be defined recursively” with “has been constructed recursively”

✅ The actual build process must be clear

---

CMI Strategy

💡 How to Attack Recursive Construction Problems

Find the smallest object that works.

Guess how one can extend a valid object.

Identify the invariant or required property.

Show that the extension preserves the property.

Write the recursive step in a form that can be used in a proof.

---

Practice Questions

:::question type="MCQ" question="A recursive construction usually consists of" options=["only a final formula","a base object and a rule to build larger objects","a geometric diagram only","checking many examples"] answer="B" hint="Think about how recursive building starts and continues." solution="A recursive construction needs:

a base object, and

a rule to construct larger objects from smaller ones.

Hence the correct option is

\boxed{B}

." ::: :::question type="NAT" question="If a binary string of length

n+1

is built from one of length

n

by appending one symbol, how many choices are there for the appended symbol?" answer="2" hint="Binary means two possible symbols." solution="A binary string uses the symbols

0

and

1

. So at each step, there are exactly

\boxed{2}

choices for the appended symbol." ::: :::question type="MSQ" question="Which of the following are typical features of recursive construction?" options=["A base case","A recursive extension rule","Preservation of a desired property","An explicit closed formula is always necessary"] answer="A,B,C" hint="Think about what makes a recursive build valid." solution="1. True.

True.

False. A recursive construction does not require an explicit closed formula.

Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="Explain how recursive construction can be used to show that binary strings of every positive length exist." answer="Start with length

1

and append a symbol at each step." hint="Use a base case and a recursive extension rule." solution="We prove existence of binary strings of every positive length by recursive construction. Base case: For length

1

, strings such as

0

and

1

already exist. Recursive step: Assume that a binary string of length

n

has been constructed. Append either

0

1

to the end of that string. The result is a binary string of length

n+1

. Thus, from a valid string of length

n

, we can construct one of length

n+1

. Therefore, starting from length

1

and repeating the recursive step, binary strings of every positive length exist." ::: ---

Summary

❗ Key Takeaways for CMI

Recursive construction builds larger objects from smaller ones.

It always needs a base case and a recursive rule.

The crucial issue is preserving the required property at each step.

Recursive construction is often paired with induction.

It is especially useful in existence and combinatorial proof problems.

---

💡 Next Up

Proceeding to Existence examples.

---

Part 4: Existence examples

Existence Examples

Overview

To prove that something exists, it is often enough to produce one correct example. This makes existence proofs very different from universal proofs. In some problems, one explicit example is enough; in others, we must show how to build an example for every

n

or for infinitely many cases. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Distinguish existence statements from universal statements.

Prove existence by giving an explicit example.

Prove infinitely many examples by construction.

Understand when induction helps create a family of examples.

Avoid confusing “one example” with “all examples”.

---

Core Idea

📖 Existence Statement

An existence statement has the form

$\qquad \exists x \text{ such that } P(x)$

To prove it, it is enough to find one valid object $x$ satisfying $P(x)$ .

❗ Two Common Types

Single existence

\qquad \exists x \text{ such that } P(x)

Parameterized existence

\qquad \forall n,\ \exists x \text{ such that } P(n,x)

The second type often needs a construction depending on

n

---

Standard Methods

📐 Method 1: Explicit Example

If the statement is
$\qquad \exists x \text{ such that } P(x)$ ,
try to find one concrete $x$ and verify it.

📐 Method 2: Construction

If the statement is
$\qquad \forall n,\ \exists x \text{ such that } P(n,x)$ ,
give a formula or rule producing such an $x$ from $n$ .

📐 Method 3: Inductive Construction

Sometimes a family of examples is built step by step:

construct a base example,

show how to enlarge one valid example into another.

This is where induction and construction meet.

---

Minimal Worked Examples

Example 1 Prove that there exists a composite number of the form

\qquad n^2+n+41

Take

\qquad n=41

. Then

\qquad n^2+n+41 = 41^2+41+41 = 41(41+2)=41\cdot 43

which is composite. So the required existence statement is proved. --- Example 2 Prove that for every positive integer

n

, there exists an even integer greater than

n

. Take

\qquad x=2n+2

Then

x

is even and

\qquad x=2n+2>n

So this constructs the required example for each

n

. ---

Why Examples Matter

❗ Existence Needs Validity, Not Exhaustion

To prove there exists an object, you do not need to classify all such objects. You only need one correct witness.

But that witness must satisfy every required condition.

---

Construction vs Guessing

⚠️ A Random Example Is Not Enough

An example is useful only if:

it is actually valid,

you explain why it works,

in the parameterized case, it works for every allowed input.

So “here is one pattern” is not a proof unless the pattern is justified.

---

Induction-Flavored Existence

💡 When Induction Helps

Suppose we want to prove:

for every $n$ , a structure of size $n$ exists,

or an example with property $P_n$ exists.

Then a common strategy is:

construct the case $n=1$ ,

show how to extend a valid example of size $n$ to one of size $n+1$ .

This is not always the best method, but it is very useful in constructive combinatorics. ---

Common Mistakes

⚠️ Avoid These Errors

❌ Giving an example but not checking it

❌ Proving only one case when the statement says “for every $n$ ”

❌ Confusing existence with uniqueness

❌ Giving a construction that does not satisfy the original condition

---

CMI Strategy

💡 How to Attack Existence Problems

Read carefully whether the statement asks for one example or infinitely many.

If one example is enough, search for a smart witness.

If every $n$ is involved, try to build a formula in terms of $n$ .

Verify the example explicitly.

Prefer constructions that are simple and checkable.

---

Practice Questions

:::question type="MCQ" question="To prove that there exists an even prime number, it is enough to show that" options=["

2

is even and prime","all prime numbers are even","all even numbers are prime","there are infinitely many even primes"] answer="A" hint="An existence proof needs one valid example." solution="The number

2

is both even and prime. That single valid example proves the existence statement. Therefore the correct option is

\boxed{A}

." ::: :::question type="NAT" question="Give one positive integer

n

for which

n^2+n

is even." answer="1" hint="Try a very small value first." solution="Take

\qquad n=1

. Then

\qquad n^2+n=1^2+1=2

, which is even. Hence one valid answer is

\boxed{1}

." ::: :::question type="MSQ" question="Which of the following can be valid ways to prove an existence statement?" options=["Exhibiting one correct example","Giving a construction that works for every allowed

n

","Checking one invalid example","Using contradiction to show that assuming nonexistence fails"] answer="A,B,D" hint="Think about standard proof methods for existence." solution="1. True. 2. True. 3. False. An invalid example proves nothing. 4. True. Contradiction can also prove existence. Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="Prove that for every positive integer

n

, there exists an odd integer greater than

n

." answer="Take

2n+1

n

is even, or

2n+3

; more simply,

2n+1>n

and is odd for all positive

n

." hint="Construct an explicit odd number from

n

." solution="Let

\qquad x=2n+1

. Then

x

is odd because it is of the form

\qquad 2k+1

with

k=n

. Also

\qquad x=2n+1>n

for every positive integer

n

. Therefore, for every positive integer

n

, there exists an odd integer greater than

n

, namely

\boxed{2n+1}

." ::: ---

Summary

❗ Key Takeaways for CMI

Existence proofs need a valid witness.

“There exists” and “for every” require different proof styles.

Construction is often the cleanest method.

Parameterized existence usually needs a formula in terms of the parameter.

Always verify the example completely.

---

Chapter Summary

❗ Induction and construction — Key Points

Mathematical Induction (MI) is a fundamental proof technique for statements about natural numbers, requiring a base case and an inductive step.
Strong Induction (SI) is a variant where the inductive hypothesis assumes the statement holds for all values up to $k$ , not just $k$ , often simplifying proofs for recursive definitions or when the $k+1$ case depends on earlier non-adjacent cases.
Recursive Definitions precisely define sequences, functions, or sets by specifying initial values (base cases) and a rule for constructing subsequent elements from preceding ones (recursive step).
The validity of both MI and SI rests on the Well-Ordering Principle, which states every non-empty set of natural numbers has a least element.
Induction is crucial for proving properties of recursively defined structures and algorithms, ensuring their correctness and existence under specified conditions.
Distinguishing between MI and SI involves analyzing the dependency of $P(k+1)$ : if it depends only on $P(k)$ , MI suffices; if it depends on $P(j)$ for $j \le k$ , SI is generally more appropriate.

---

Chapter Review Questions

:::question type="MCQ" question="Which of the following statements is typically best proven using strong induction rather than standard mathematical induction?" options=["The sum of the first $n$ natural numbers is $n(n+1)/2$ .", "For any integer $n \ge 1$ , $2^{2n}-1$ is divisible by 3.", "Every integer $n \ge 2$ can be expressed as a product of prime numbers.", "A sequence defined by $a_n = 2a_{n-1}$ for $n \ge 1$ with $a_0=1$ has the property $a_n = 2^n$ ."] answer="Every integer $n \ge 2$ can be expressed as a product of prime numbers." hint="Consider cases where $P(k+1)$ depends on $P(j)$ for $j < k+1$ rather than just $P(k)$ ." solution="The Fundamental Theorem of Arithmetic, stating that every integer $n \ge 2$ can be expressed as a product of prime numbers, is a classic application of strong induction. The proof for $n$ relies on the fact that if $n$ is composite, it can be written as $ab$ where $a, b < n$ , and the inductive hypothesis applies to $a$ and $b$ (which are not necessarily $n-1$ ). The other options are typically proven using standard mathematical induction."
:::

:::question type="NAT" question="A sequence is defined by $a_0 = 3$ , $a_1 = 2$ , and $a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 2$ . What is the value of $a_4$ ?" answer="28" hint="Calculate the terms iteratively starting from $a_2$ ." solution="Using the recursive definition:
$a_0 = 3$
$a_1 = 2$
$a_2 = a_1 + 2a_0 = 2 + 2(3) = 8$
$a_3 = a_2 + 2a_1 = 8 + 2(2) = 12$
$a_4 = a_3 + 2a_2 = 12 + 2(8) = 28$ "
:::

:::question type="MCQ" question="Which of the following statements about the principle of mathematical induction is FALSE?" options=["The base case must be proven true for the smallest value of $n$ for which the statement is claimed to hold.", "The inductive hypothesis assumes $P(k)$ is true for an arbitrary integer $k \ge \text{base case}$ .", "The inductive step proves $P(k+1)$ is true, assuming $P(k)$ is true.", "If the base case is false but the inductive step holds, the statement $P(n)$ is still guaranteed to be true for all $n \ge \text{base case}$ ."] answer="If the base case is false but the inductive step holds, the statement $P(n)$ is still guaranteed to be true for all $n \ge \text{base case}$ ." hint="Both the base case and the inductive step are necessary components for a valid inductive proof." solution="For a statement $P(n)$ to be proven true by mathematical induction, both the base case $P(n_0)$ and the inductive step $P(k) \implies P(k+1)$ must be valid. If the base case is false, the induction cannot establish the truth of $P(n)$ for any $n$ , even if the inductive step holds."
:::

:::question type="NAT" question="Let $S$ be the set recursively defined by:

3 \in S

x \in S

, then

x+4 \in S

What is the smallest element in

S

that is greater than 10?" answer="11" hint="List the elements of the set

S

in increasing order." solution="The elements of

S

are generated as follows:
Starting with

3 \in S

.
Applying rule 2:

3+4 = 7 \in S

.
Applying rule 2:

7+4 = 11 \in S

.
Applying rule 2:

11+4 = 15 \in S

.
And so on.
The elements of

S

are

\{3, 7, 11, 15, 19, \dots\}

. The smallest element in

S

greater than 10 is 11."
:::

---

What's Next?

💡 Continue Your CMI Journey

This chapter established mathematical induction and recursive construction as powerful tools for proving properties of natural numbers and defining complex structures. These techniques build directly upon the logical foundations of proof introduced previously and are indispensable for rigorous mathematical thinking. Expect to apply these principles extensively when analyzing algorithms, constructing data structures, and proving theorems in subsequent chapters on topics such as graph theory, discrete structures, and computability.

Induction and construction

Induction and construction

Chapter Contents

| Topic |

Part 1: Mathematical induction

Mathematical Induction

Overview

Learning Objectives

Core Idea

Standard Structure of an Induction Proof

Typical Forms of Statements Proved by Induction

Minimal Worked Example

Choosing the Right Base Case

Induction in Inequalities

Induction and Divisibility

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 2: Strong induction

Strong Induction

Overview

Learning Objectives

Core Idea

Why Strong Induction is Needed

Standard Structure of a Strong Induction Proof

Strong Induction vs Ordinary Induction

Minimal Worked Example

When Multiple Base Cases Are Needed

Common Applications

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 3: Recursive construction

Recursive Construction

Overview

Learning Objectives

Core Idea

Recursive Construction vs Recursive Definition

Standard Pattern

Why Recursive Construction Matters

Typical Examples

Minimal Worked Example

Recursive Construction and Induction

Structural Preservation

Common Construction Patterns

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 4: Existence examples

Existence Examples

Overview

Learning Objectives

Core Idea

Standard Methods

Minimal Worked Examples

Why Examples Matter

Construction vs Guessing

Induction-Flavored Existence

Common Mistakes

CMI Strategy

Practice Questions

Summary

Chapter Summary

Chapter Review Questions

What's Next?

🎯 Key Points to Remember

Related Topics in Logic, Proof and Mathematical Thinking

Logic language

Case analysis

Standard proof methods

Mixed-topic aptitude

More Resources

Study Notes

Short Notes

Test Series

Mock Tests

Previous Year Papers