DM-08

Course 8

Induction and Recursion

Learn the powerful techniques of mathematical induction for proving statements about integers, and recursion for defining functions and structures.

Learning Objectives

Understand the principle of mathematical induction
Apply weak induction to prove statements
Use strong induction for complex proofs
Create recursive definitions
Prove properties using structural induction
Understand the well-ordering principle

1. Mathematical Induction

Theorem 8.1: Principle of Mathematical Induction

To prove that $P(n)$ is true for all positive integers $n$ , it suffices to show:

Base Case: $P(1)$ is true.
Inductive Step: For all $k \geq 1$ , if $P(k)$ is true, then $P(k+1)$ is true.

The assumption that $P(k)$ is true is called the inductive hypothesis.

Example: Sum of First n Positive Integers

Claim: For all $n \geq 1$ , $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

Base Case (n = 1):

LHS: $\sum_{i=1}^{1} i = 1$ . RHS: $\frac{1 \cdot 2}{2} = 1$ . ✓

Inductive Step:

Assume $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$ for some $k \geq 1$ .

We must show: $\sum_{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2}$

$\sum_{i=1}^{k+1} i = \sum_{i=1}^{k} i + (k+1)$

$= \frac{k(k+1)}{2} + (k+1)$ (by inductive hypothesis)

$= \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$ ✓

By mathematical induction, the formula holds for all $n \geq 1$ . ∎

2. Strong Induction

Definition 8.1: Strong Induction

Strong induction allows us to assume $P(1), P(2), \ldots, P(k)$ are all true to prove $P(k+1)$ .

Base Case: Prove $P(1)$ (and possibly more base cases)
Inductive Step: Prove that if $P(1) \land P(2) \land \cdots \land P(k)$ are all true, then $P(k+1)$ is true

Example: Every Integer > 1 Has a Prime Factor

Claim: Every integer $> 1$ has a prime divisor.

Base Case (n = 2): 2 is prime, so it is its own prime divisor. ✓

Inductive Step:

Assume every integer $j$ with $2 \leq j \leq k$ has a prime divisor.

Consider $k+1$ . Either:

$k+1$ is prime: then it's its own prime divisor. ✓
$k+1$ is composite: then $k+1 = ab$ where $1 < a, b < k+1$ . By hypothesis, $a$ has a prime divisor $p$ , which also divides $k+1$ . ✓

By strong induction, every integer $> 1$ has a prime divisor. ∎

3. Recursive Definitions

Definition 8.2: Recursive Definition

A recursive definition defines an object in terms of simpler versions of itself:

Base Case(s): Specify the value(s) for the initial input(s).
Recursive Step: Define the value for larger inputs in terms of smaller inputs.

Example: Recursively Defined Functions

Factorial

Base: $0! = 1$

Recursive: $n! = n \cdot (n-1)!$ for $n \geq 1$

Power Function

Base: $a^0 = 1$

Recursive: $a^n = a \cdot a^{n-1}$ for $n \geq 1$

Fibonacci Numbers

Base: $F_1 = 1, F_2 = 1$

Recursive: $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$

4. Well-Ordering Principle

Theorem 8.2: Well-Ordering Principle

Every non-empty set of positive integers has a least (smallest) element.

Remark

The well-ordering principle, mathematical induction, and strong induction are all equivalent—each can be proved from the others.

Practice Quiz

Induction and Recursion Quiz

Questions

Correct

Accuracy

In a proof by mathematical induction, the base case typically shows that:

Easy

Not attempted

In the inductive step, we assume

P(k)

is true and prove:

Easy

Not attempted

What is

\sum_{i=1}^{n} i

according to the formula proved by induction?

Easy

Not attempted

Strong induction differs from weak induction because:

Medium

Not attempted

The Fibonacci sequence is defined by

F_1 = 1, F_2 = 1

, and

F_n = F_{n-1} + F_{n-2}

. What is

F_7

Medium

Not attempted

A recursive definition must always include:

Easy

Not attempted

To prove

n! > 2^n

for

n \geq 4

, which base case should we verify?

Medium

Not attempted

The well-ordering principle states that:

Hard

Not attempted

f(0) = 1

and

f(n) = 2 \cdot f(n-1)

for

n \geq 1

, what is

f(5)

Medium

Not attempted

Structural induction is used to prove properties about:

Hard

Not attempted

Frequently Asked Questions

When should I use weak induction vs strong induction?

Use weak induction when $P(k+1)$ depends only on $P(k)$ .

Use strong induction when $P(k+1)$ might depend on earlier values.

Why do we need a base case?

Without a base case, the inductive step has nothing to build on. The base case anchors the proof.

Can induction start at values other than 1?

Yes! If your statement is "for all $n \geq n_0$ ," start the base case at $n_0$ .

What's the connection between recursion and induction?

They are two sides of the same coin:

Recursion defines things in terms of smaller versions
Induction proves things by building up from base cases

How do I handle multiple base cases?

When your recurrence uses more than one previous value (like Fibonacci), verify the statement for enough initial values so the recurrence can take over.