Chapter 8: Induction and Recursion

Content locked

The catalog is public. Reading this content requires approved access.

8.1 Sequences

Survey

Animation content:

Animation captions:

Increasing and decreasing sequences

2) 4,3.5,2,-1

3) 2, 2, 2, 2

Geometric sequences

Animation content:

Animation captions:

Example 8.1.1: Interest rates and geometric sequences.

PARTICIPATION ACTIVITY

Arithmetic sequences

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

Example 8.1.2: Accumulated resources and arithmetic sequences.

PARTICIPATION ACTIVITY

Check

Show answer

Check

Show answer

CHALLENGE ACTIVITY

Start

Additional exercises

EXERCISE

8.2 Recurrence relations

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

CHALLENGE ACTIVITY

PARTICIPATION ACTIVITY

Example 8.2.3: Outstanding balance on a car loan.

Additional exercises

EXERCISE

8.3 Summations

Animation content:

Animation captions:

Pulling out a final term from a summation

PARTICIPATION ACTIVITY

Change of variables in summations

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Check

Show answer

Check

Show answer

Check

Show answer

Check

Show answer

Closed forms for sums

PARTICIPATION ACTIVITY

CHALLENGE ACTIVITY

Additional exercises

EXERCISE

8.4 Mathematical induction

Figure 8.4.1: The two components of an inductive proof.

Figure 8.4.2: Principle of mathematical induction.

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Additional exercises

EXERCISE

8.5 More inductive proofs

Divisibility proof by induction

PARTICIPATION ACTIVITY

Using induction to prove an assertion about a recurrence relation

Proof.

PARTICIPATION ACTIVITY

Proof.

Inductive proofs showing the closed forms for sums of arithmetic and geometric sequences.

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

An inductive proof for set operations

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Additional exercises

EXERCISE

8.6 Strong induction and well-ordering

PARTICIPATION ACTIVITY

Inductive step:

Figure 8.6.2: Principle of strong mathematical induction.

Figure 8.6.3: Expanded expression of the inductive step with an arbitrary range for the base case.

PARTICIPATION ACTIVITY

Strong induction example: buying cans of juice in 3-packs or 4-packs.

Base case:

Animation content:

Animation captions:

How many base cases?

Proof.

PARTICIPATION ACTIVITY

Figure 8.6.4: The well-ordering principle.

Figure 8.6.5: The principle of mathematical induction.

Proof 8.6.3: Well-ordering implies the principle of mathematical induction.

Proof.

Theorem 8.6.2: The Division Algorithm.

Proof 8.6.4: Proof of the Division Algorithm using the well-ordering principle.

Proof.

PARTICIPATION ACTIVITY

Additional exercises

EXERCISE

8.7 Loop invariants

Program correctness

PARTICIPATION ACTIVITY

Loop invariants for while loops

Figure 8.7.2: Steps in using a loop invariant.

PARTICIPATION ACTIVITY

8.7.4: The four steps of using a loop invariant.

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Proof.

PARTICIPATION ACTIVITY

EXERCISE

8.8 Recursive definitions

Check Show answer

PARTICIPATION ACTIVITY

Recursively defined sets

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Creating: 101

PARTICIPATION ACTIVITY

Check

Show answer

Check

Show answer

Recursive definition for the length of a binary string

PARTICIPATION ACTIVITY

Check

Show answer

Check

Show answer

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

Start

EXERCISE

8.9 Structural induction

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

Proof.

Structural induction and perfect binary trees

PARTICIPATION ACTIVITY

Proof.

Additional exercises

EXERCISE

8.10 Recursive algorithms

Factorial(n)

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PowerSet(A)

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

ReverseString(s)

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Exponent(r, n)

RecursiveFibonacci(n)

Animation content:

Animation captions:

Additional exercises

EXERCISE

8.11 Induction and recursive algorithms

Animation content:

Animation captions:

Proof 8.11.1: Proof of correctness for ReverseString.

Proof.

PowerSet(A)

PARTICIPATION ACTIVITY

Proof 8.11.2: Proof of correctness for PowerSet.

Proof.

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

Proof 8.11.3: Proof of correctness for FastExpRec.

Proof.

PARTICIPATION ACTIVITY

Exponent(r, n)

Additional exercises

EXERCISE

8.12 Analyzing the time complexity of recursive algorithms ©zyBooks 04/08/25

Deriving the recurrence relation

Factorial(n)

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

PowerRecursive(r, n)

Overview of analyzing recursive algorithms: A two step process

PARTICIPATION ACTIVITY

Simplifying recurrence relations for asymptotic analysis

Rule

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Deriving a simplified recurrence relation for asymptotic analysis

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

Additional exercises

EXERCISE

8.13 Divide-and-conquer algorithms: Introduction and mergesort

Divide-and-conquer algorithms

FindMin(L)

FindMin

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

MergeSort

PARTICIPATION ACTIVITY

8.13.3: Recursion tree for MergeSort.

Animation content:

Animation captions:

The queue data structure

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

The Merge operation

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Pseudocode for MergeSort

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Additional exercises

EXERCISE

8.14 Divide-and-conquer algorithms: Binary search

Binary search

Animation content:

Animation captions:

Recursive binary search

Pseudocode

Animation content:

Animation captions:

Check

Show answer

Check

Show answer

Check

Show answer

Check

Show answer

Check

Show answer

Analyzing recursive binary search

Animation content:

Animation captions:

EXERCISE

8.15 Solving linear homogeneous recurrence relations

A simple example

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

Linear Homogeneous Recurrence Relations

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Reset

Proof 8.15.1: Solutions to linear homogeneous recurrence relations.

Proof.

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Characteristic equations with multiple roots

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Additional exercises

EXERCISE

8.16 Solving linear nonhomogeneous recurrence relations

The associated homogeneous recurrence relation

Particular and homogeneous solutions

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Using the initial conditions to derive the final solution

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

Summary of all the steps

PARTICIPATION ACTIVITY

Determining the form of the particular solution

Animation content:

Animation captions:

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Additional exercises

EXERCISE

8.17 Divide-and-conquer recurrence relations

Deriving solutions to divide-and-conquer recurrence relations

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

Expressing the formula as a geometric sum

PARTICIPATION ACTIVITY

Animation content:

Animation captions:

PARTICIPATION ACTIVITY

The Master Theorem

Animation content:

Animation captions:

Additional exercises

EXERCISE

Source