Recursive Foundations Slides Unit 1: Foundations
RECURSIVE ROOTS
Lesson 1: The Power of Dependence
Definition
Iteration
Sequence
The Essential Question
"How can we describe and predict the state of a system based solely on its history?"
Implicit
Defined by what came before.
Recursive
The current step is a function of previous steps.
Explicit
Defined by position in the sequence.
The Tower of Hanoi
A classic recursive puzzle
The Goal
Move all disks from the source peg to the destination peg.
The Rules
Move only one disk at a time.
A disk can only be moved to an empty peg or on top of a larger disk.
Minimum moves for \( n \) disks?
Building the Recurrence
Let \( H_n \) be the minimum moves to transfer \( n \) disks.
To move \( n \) disks:
Move top \( n-1 \) disks: \( H_{n-1} \) moves
Move largest disk: 1 move
Move \( n-1 \) disks onto largest: \( H_{n-1} \) moves
The Formula
\( H_n = 2H_{n-1} + 1 \)
Base Case: \( H_1 = 1 \)
Disks (\( n \)) Moves (\( H_n \)) 1 1 2 3 3 7 4 15
Anatomy of a Recurrence
\( a_n \)
Term in Question
=
\( f(a_{n-1}, a_{n-2}, ...) \)
Recursive Definition
1. Initial Conditions
You must define where the sequence starts (e.g., \( a_0 \)). Without this, the formula is incomplete.
2. Order
Determined by the oldest term the current term depends on. If \( a_n \) depends on \( a_{n-2} \), it is second-order.
Hanoi Trials Worksheet HANOI TRIALS
Lesson 1: Introduction to Recursive Definitions
Student Name:
Date:
Part 1: Iterative Investigation
Recall the recursive formula for the Tower of Hanoi: \( H_n = 2H_{n-1} + 1 \) where \( H_1 = 1 \). Manually iterate this formula to find the minimum moves for the following values of \( n \).
\( n = 1 \)
1
\( n = 2 \)
\( n = 3 \)
\( n = 4 \)
\( n = 5 \)
Pattern Recognition:
Looking at the sequence above (\( 1, 3, 7, 15, ... \)), can you propose an explicit formula \( H_n = f(n) \) that does not require the previous term?
Part 2: Linear Recurrence Types
Determine the recursive formula for each sequence and identify its order .
5, 10, 20, 40, 80...
Recursive Formula
Order
2, 5, 8, 11, 14...
Recursive Formula
Order
1, 1, 2, 3, 5, 8...
Recursive Formula
Order
Part 3: Word Problems to Recurrence
Problem A: Binary Strings
Let \( a_n \) be the number of binary strings of length \( n \) that do not contain consecutive zeros. Write out the strings for \( n=1, 2, 3 \) and find a recurrence relation for \( a_n \).
Investigation Space:
Resulting Recurrence:
Problem B: Computer Backup
A server stores 100GB of data. Every hour, it generates 5GB of new data and deletes 10% of the total data stored at the start of that hour. Write a recurrence relation for \( D_n \), the amount of data after \( n \) hours.
Model Construction:
First Order Slides Unit 2: Linear Systems
ALGORITHM ARSENAL
Lesson 2: Solving First-Order Recurrences
Analysis
Summation
Efficiency
First-Order Linear Recurrence
\( a_n = c \cdot a_{n-1} + g(n) \)
Homogeneous Part If \( g(n) = 0 \), the relation is homogeneous.
Non-Homogeneous Part If \( g(n) \neq 0 \), the relation is non-homogeneous.
Our goal is to find a closed-form solution: a formula for \( a_n \) that depends only on \( n \).
Method of Iteration
Let's unroll the definition of \( a_n = c \cdot a_{n-1} + f \)
\( a_n = c \cdot a_{n-1} + f \)
\( a_n = c (c \cdot a_{n-2} + f) + f \)
\( a_n = c^2 \cdot a_{n-2} + cf + f \)
\( a_n = c^3 \cdot a_{n-3} + c^2f + cf + f \)
The General Pattern
\( a_n = c^n a_0 + f \sum_{i=0}^{n-1} c^i \)
By applying the geometric series sum formula, we can collapse the summation into a single fraction.
Search Efficiency
Binary Search
Each step halves the search space and does one comparison.
\( T(n) = T(n/2) + 1 \)
Master Theorem Preview
Linear Search
Each step checks one item and proceeds to the remaining list.
\( L(n) = L(n-1) + 1 \)
Wait, that looks familiar...
Observation:
Algorithm runtime is rarely a single number; it's a sequence of costs that scales with input size. Recurrences are the natural language of Big-O.
Algorithm Audit Worksheet ALGORITHM AUDIT
Lesson 2: First-Order Recurrence Relations
Student:
System ID:
Part 1: The Iterative Method
Use the method of iteration to find a closed-form solution for the following recurrence. Show each "unrolling" step clearly.
\( a_n = 3a_{n-1} + 2 \), where \( a_0 = 1 \)
Step 1:
Step 2:
Step 3:
Generalize:
Final Closed-Form Solution:
Part 2: Sorting Performance
An engineer is comparing two algorithms. Let \( C(n) \) be the number of comparisons needed for a list of size \( n \).
Algorithm Alpha
Divide and Conquer (Simplified)
C(n) = C(n-1) + (n-1)
1. Solve for \( C(n) \) using the sum of arithmetic integers.
Algorithm Beta
Geometric Scaling
C(n) = 2C(n-1) + 1
2. Solve for \( C(n) \) using the Tower of Hanoi result.
Efficiency Analysis
As \( n \to \infty \), which algorithm has a lower computational complexity? Use Big-O notation to justify your answer.
Second Order Slides Unit 3: Higher Order Systems
CHARACTERISTIC ROOTS
Lesson 3: Homogeneous Second-Order Relations
Growth
Linearity
Roots
The Second-Order Jump
Fibonacci's Model (1202)
A pair of rabbits takes one month to mature. Once mature, they produce a new pair every month.
Key Insight:
"The population today depends not just on last month, but on the month before when the new breeders were born."
The Relation
\( F_n = F_{n-1} + F_{n-2} \)
Requires TWO initial conditions: \( F_0, F_1 \).
Solving \( a_n = c_1 a_{n-1} + c_2 a_{n-2} \)
We guess a solution of the form \( a_n = r^n \).
Substituting this into the recurrence gives:
\( r^n = c_1 r^{n-1} + c_2 r^{n-2} \)
Divide by \( r^{n-2} \) to get the quadratic:
\( r^2 - c_1 r - c_2 = 0 \)
Distinct Roots (\( r_1 \neq r_2 \))
\( a_n = \alpha_1 r_1^n + \alpha_2 r_2^n \)
Repeated Roots (\( r_1 = r_2 = r \))
\( a_n = \alpha_1 r^n + \alpha_2 n r^n \)
Applying Initial Conditions
Initial State
\( a_0 = X \)
\( a_1 = Y \)
Plug \( n=0 \) and \( n=1 \) into the general solution to create a system of linear equations.
\( a_0 = \alpha_1 + \alpha_2 = X \)
Solve for \( \alpha_1 \) and \( \alpha_2 \) to find the unique solution.
Rabbit Breeding Worksheet RABBIT BREEDING LOG
Lesson 3: Second-Order Homogeneous Recurrences
Student Name:
Date:
Part 1: Solving the Equation
For each of the following second-order homogeneous linear recurrences, find the characteristic roots and write the general solution .
\( a_n = 5a_{n-1} - 6a_{n-2} \)
Distinct Roots
Characteristic Equation & Roots:
General Solution:
\( a_n = 4a_{n-1} - 4a_{n-2} \)
Repeated Roots
Characteristic Equation & Roots:
General Solution:
Part 2: Initial Conditions
Solve the following initial value problem to find the unique solution for \( a_n \).
\( a_n = a_{n-1} + 2a_{n-2} \)
Initial Conditions: \( a_0 = 2, a_1 = 7 \)
1. Form the System of Equations
2. Solve for \( \alpha_1, \alpha_2 \)
3. Final Formula
The Challenge: Luca's Numbers
Lucas numbers (\( L_n \)) follow the same recurrence as Fibonacci (\( L_n = L_{n-1} + L_{n-2} \)) but start with \( L_0 = 2 \) and \( L_1 = 1 \). Based on what you know about the characteristic roots of this recurrence (\( \phi \) and \( \psi \)), write the closed-form for \( L_n \).
Phi Finder Slides Unit 4: Universal Constants
GOLDEN ROOTS
Lesson 4: Binet's Formula & The Ratio of Life
Botany
Limits
Derivation
Re-solving Fibonacci
Let's solve \( F_n = F_{n-1} + F_{n-2} \) with \( F_0 = 0, F_1 = 1 \).
Step 1: The Characteristic Equation
\( r^2 - r - 1 = 0 \)
Step 2: Using the Quadratic Formula
\( r = \frac{1 \pm \sqrt{5}}{2} \)
The Roots
\( \phi \)
\( \approx 1.618 \)
The Golden Ratio
\( \psi \)
\( \approx -0.618 \)
\( -1/\phi \)
Binet's Formula
Closed-Form Solution
\( F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right] \)
Produces integers from irrational numbers.
Allows direct calculation of \( F_{1000} \).
Shows the growth rate is exactly \( \phi \).
Emergence in Nature
Sunflowers
Seed packing follows Fibonacci spirals to maximize space efficiency.
Phyllotaxis
Leaf arrangement on stems often follows Fibonacci numbers for light exposure.
Limit Ratio
As \( n \to \infty \):
Binet Derivation Worksheet BINET'S DERIVATION LAB
Lesson 4: The Golden Ratio & Binet's Formula
Researcher:
System Time:
Part 1: The Converging Ratio
Fill in the table below to observe the behavior of the ratio of consecutive Fibonacci terms \( \frac{F_{n+1}}{F_n} \).
\( n \) \( F_n \) \( F_{n+1} \) Ratio (\( \approx 4 \) decimals) 3 2 3 1.5000 4 3 5 1.6667 5 5 8 6 8 13 7 13 21 8 21 34
Conjecture:
As \( n \to \infty \), what specific irrational value does this ratio approach?
Part 2: The Derivation Challenge
Recall that the general solution for the Fibonacci recurrence \( F_n = F_{n-1} + F_{n-2} \) is:
Step A: Setup the System
Use \( F_0 = 0 \) and \( F_1 = 1 \) to write two equations for \( \alpha_1 \) and \( \alpha_2 \).
Step B: Solve for Constants
Solve the system to find that \( \alpha_1 = 1/\sqrt{5} \) and \( \alpha_2 = -1/\sqrt{5} \).
Conclusion
The Result: Binet's Formula
Write the final closed-form expression for the \( n^{th} \) Fibonacci number.
Coexistence Slides Unit 5: Coupled Systems
COEXISTENCE
Lesson 5: Predator-Prey Recurrence Systems
Coupled
Matrices
Stability
Interdependent Systems
In the real world, variables rarely evolve in isolation. The population of Prey (\( R_n \)) affects the survival of Predators (\( F_n \)), and vice versa.
The Loop:
More prey \(\to\) Predator growth
More predators \(\to\) Prey decline
Less prey \(\to\) Predator decline
The Matrix Representation
We can represent the system of recurrences as a single vector equation:
\( V_{n+1} = M \cdot V_n \)
Where \( V_n = [R_n, F_n]^T \)
Example Transition Matrix
\( \begin{bmatrix} R_{n+1} \\ F_{n+1} \end{bmatrix} = \begin{bmatrix} 1.1 & -0.4 \\ 0.1 & 0.8 \end{bmatrix} \begin{bmatrix} R_n \\ F_n \end{bmatrix} \)
1.1: Prey growth rate without predators.
-0.4: Impact of predators on prey.
0.8: Predator survival rate.
Predicting Stability
Explosive Growth
If eigenvalues are greater than 1, the system grows without bound.
\( \lambda > 1 \)
Extinction
If eigenvalues are less than 1, the populations eventually vanish.
\( \lambda < 1 \)
Equilibrium
If eigenvalues equal 1, the system reaches a stable steady state.
\( \lambda = 1 \)
General Solution: \( V_n = c_1 \lambda_1^n X_1 + c_2 \lambda_2^n X_2 \)
Population Pivot Worksheet POPULATION PIVOT
Lesson 5: Systems of Recurrence Relations
Lead Analyst:
Sector ID:
Part 1: The Transition Matrix
Convert the following coupled system into its matrix-vector form: \( V_{n+1} = M V_n \).
\( R_{n+1} = 1.2 R_n - 0.5 F_n \)
\( F_{n+1} = 0.2 R_n + 0.9 F_n \)
\( \begin{bmatrix} R_{n+1} \\ F_{n+1} \end{bmatrix} = \)
Matrix M
\( \begin{bmatrix} R_n \\ F_n \end{bmatrix} \)
Iteration Check:
If the initial population is \( V_0 = [100, 50]^T \), calculate the population at \( n=1 \).
Part 2: Long-Term Behavior
To predict if a population thrives or goes extinct, we examine the eigenvalues (\( \lambda \)) of the transition matrix.
Case Study: The Fox-Rabbit Equilibrium
Consider a system where the transition matrix is \( M = \begin{bmatrix} 0.8 & 0.4 \\ 0.2 & 0.6 \end{bmatrix} \).
1. Find the Eigenvalues
Solve \( \det(M - \lambda I) = 0 \).
2. Dominant Root
Identify the eigenvalue with the largest magnitude.
3. Stability Prediction
Describe the population's fate as \( n \to \infty \).
The Extinction Threshold
If the dominant eigenvalue is \( \lambda = 0.95 \), and the starting population is 1,000,000, approximately how many steps (\( n \)) will it take for the population to fall below 500,000?
Recursive Roots Solution Key INSTRUCTOR SOLUTIONS
Sequence: Recursive Roots (Discrete Mathematics)
Teacher Reference
Lesson 1: Hanoi Trials
Part 1: Hanoi Iteration
\( H_1=1, H_2=3, H_3=7, H_4=15, H_5=31 \). Explicit formula: \( H_n = 2^n - 1 \).
Part 2: Sequences
5, 10, 20...: \( a_n = 2a_{n-1} \); Order: 1
2, 5, 8...: \( a_n = a_{n-1} + 3 \); Order: 1
1, 1, 2, 3...: \( a_n = a_{n-1} + a_{n-2} \); Order: 2
Lesson 2: Algorithm Audit
Part 1: Method of Iteration
\( a_n = 3a_{n-1} + 2 \to a_n = 2 \cdot 3^n - 1 \)
Part 2: Sorting Efficiency
Alpha: \( C(n) = n(n-1)/2 \to O(n^2) \)Alpha is more efficient.
Lesson 3: Rabbit Breeding
Part 2: Initial Value Problem
\( a_n = 3 \cdot 2^n - (-1)^n \).
Lesson 5: Population Pivot
Part 2: Long-Term Behavior
Eigenvalues: \( \lambda = 1, 0.4 \).stable .
