The Central Idea
A discrete system evolves through a sequence of states:
\[ s_0,\ s_1,\ s_2,\ s_3,\ldots \]An update rule tells us how to move from one state to the next:
\[ \boxed{s_{n+1}=T(s_n)}. \]The function \(T\) is the state-transition rule.
Iteration means repeatedly applying \(T\):
\[ s_0 \longrightarrow s_1 \longrightarrow s_2 \longrightarrow s_3 \longrightarrow\cdots. \]What Is a State?
A state is the information needed to determine what happens next.
In a first-order recurrence such as
\[ a_{n+1}=2a_n+1, \]the current value \(a_n\) is enough to determine \(a_{n+1}\).
Therefore, the state can be represented by the single number
\[ \boxed{a_n}. \]What Is a Transition?
A transition is one application of the update rule.
Suppose
\[ T(x)=2x+1. \]Starting from
\[ x=3, \]one transition gives
\[ T(3)=7. \]Thus,
\[ \boxed{3\longrightarrow7}. \]Iteration
To iterate a rule means to apply it repeatedly.
Let
\[ x_{n+1}=2x_n+1 \]with
\[ x_0=1. \]Then
\[ x_1=2(1)+1=3, \] \[ x_2=2(3)+1=7, \] \[ x_3=2(7)+1=15. \]The trajectory begins
\[ \boxed{1,\ 3,\ 7,\ 15,\ldots}. \]The Orbit or Trajectory
The sequence of states produced from an initial state is often called an orbit or trajectory.
If
\[ x_0=4 \]and
\[ x_{n+1}=x_n-1, \]then the trajectory is
\[ \boxed{4,\ 3,\ 2,\ 1,\ 0,\ -1,\ldots}. \]Iteration and Recurrence Relations
A first-order recurrence
\[ a_{n+1}=F(a_n) \]is already an iterative state-transition rule.
We can write
\[ T(x)=F(x), \]so that
\[ \boxed{a_{n+1}=T(a_n)}. \]The recurrence and the state-transition description emphasize the same process from slightly different perspectives.
Iteration and Difference Equations
Suppose
\[ \Delta a_n=G(a_n). \]Since
\[ \Delta a_n=a_{n+1}-a_n, \]we have
\[ a_{n+1}=a_n+G(a_n). \]Therefore, the transition rule is
\[ \boxed{T(x)=x+G(x)}. \]Example: From Difference Equation to Transition Rule
Let
\[ \Delta x_n=5-0.2x_n. \]Then
\[ x_{n+1} = x_n+5-0.2x_n. \]Therefore,
\[ \boxed{x_{n+1}=0.8x_n+5}. \]The state-transition function is
\[ \boxed{T(x)=0.8x+5}. \]Initial State
An iterative system requires an initial state.
The rule
\[ x_{n+1}=3x_n \]allows many trajectories.
If
\[ x_0=1, \]then
\[ 1,\ 3,\ 9,\ 27,\ldots \]results.
If
\[ x_0=2, \]then
\[ 2,\ 6,\ 18,\ 54,\ldots \]results.
Deterministic State Transitions
A transition rule is deterministic if the current state determines exactly one next state.
For example,
\[ T(x)=x^2+1 \]is deterministic because every input \(x\) produces exactly one output.
Therefore, a known initial state determines one unique trajectory.
Finite State Spaces
A system has a finite state space if only finitely many states are possible.
For example, suppose the possible states are
\[ \{A,B,C,D\}. \]A transition rule might specify
\[ A\to B,\qquad B\to C,\qquad C\to B,\qquad D\to A. \]Every trajectory remains inside this finite set.
Infinite State Spaces
Many recurrence systems have infinitely many possible states.
For example,
\[ x_{n+1}=x_n+1 \]may evolve through integer states
\[ 0,\ 1,\ 2,\ 3,\ldots \]without repeating.
The state-transition idea applies to both finite and infinite state spaces.
Transition Diagrams
A finite state-transition system can be represented by a directed diagram.
Each state is a vertex, and an arrow points from a state to its next state.
For
\[ A\to B,\qquad B\to C,\qquad C\to B, \]the system eventually moves back and forth between \(B\) and \(C\).
Transition diagrams make cycles and fixed states visually apparent.
Fixed States
A state \(s\) is a fixed state or fixed point if applying the transition rule leaves it unchanged.
\[ \boxed{T(s)=s}. \]In recurrence form,
\[ s_{n+1}=s_n=s. \]Example: Find a Fixed Point
Let
\[ T(x)=0.5x+6. \]A fixed point satisfies
\[ x=0.5x+6. \]Therefore,
\[ 0.5x=6, \] \[ \boxed{x=12}. \]Starting exactly at \(12\) gives the constant trajectory
\[ 12,\ 12,\ 12,\ldots \]Fixed Points and Equilibria
Fixed points in transition form correspond to equilibria in difference form.
If
\[ x_{n+1}=T(x_n), \]then a fixed point satisfies
\[ T(x)=x. \]Equivalently,
\[ x_{n+1}-x_n=0. \]Thus,
\[ \boxed{\Delta x_n=0}. \]Cycles
A cycle occurs when the system returns to a previous state and then repeats the same pattern.
For example,
\[ A\to B\to C\to A \]forms a cycle of length \(3\).
The trajectory repeats
\[ A,\ B,\ C,\ A,\ B,\ C,\ldots \]A Two-Cycle
Consider
\[ T(x)=1-x. \]Starting at \(0\),
\[ 0\to1\to0\to1\to\cdots. \]Thus, \(0\) and \(1\) form a cycle of length \(2\).
Period of a Cycle
The period of a cycle is the number of transitions required to return to the same state.
A fixed point has period \(1\).
A two-cycle has period \(2\).
More generally, a cycle
\[ s_0\to s_1\to\cdots\to s_{k-1}\to s_0 \]has period \(k\) if no earlier return occurs.
Repeated States in Deterministic Finite Systems
In a deterministic system, once a state repeats, the future must repeat as well.
Suppose
\[ s_i=s_j \]
for some \(i
Since the same state always has the same next state,
and the subsequent states repeat in the same way.
Thus, repetition produces eventual periodicity.
Finite Deterministic Systems Eventually Repeat
Suppose a deterministic system has only finitely many states.
If we iterate forever, eventually some state must occur twice.
Once that happens, the trajectory enters a cycle.
Therefore,
\[ \boxed{\text{every infinite trajectory in a finite deterministic system is eventually periodic}}. \]This is an application of pigeonhole reasoning.
Transient States
States visited before a trajectory enters its repeating cycle are often called transient states.
For example,
\[ A\to D\to B\to C\to B\to C\to\cdots \]has transient states
\[ A,\ D \]followed by the cycle
\[ B\leftrightarrow C. \]State Transition under Modular Arithmetic
Modular arithmetic naturally creates finite state spaces.
Consider
\[ x_{n+1}\equiv x_n+2\pmod 5. \]Starting from \(0\),
\[ 0\to2\to4\to1\to3\to0. \]The system cycles through all five residue classes.
Example: Modular Doubling
Let
\[ x_{n+1}\equiv2x_n\pmod7 \]with
\[ x_0=1. \]Then
\[ 1\to2\to4\to1. \]Therefore, the trajectory has period \(3\).
Higher-Order Recurrences Need Larger States
A second-order recurrence such as
\[ a_{n+1}=a_n+a_{n-1} \]cannot determine the next term from \(a_n\) alone.
A complete state must include two consecutive terms:
\[ \boxed{(a_{n-1},a_n)}. \]State Transition for a Second-Order Recurrence
For
\[ a_{n+1}=a_n+a_{n-1}, \]the state transition is
\[ \boxed{ (a_{n-1},a_n) \longrightarrow (a_n,a_{n-1}+a_n) }. \]This converts a second-order scalar recurrence into a first-order transition rule on ordered pairs.
Example: Fibonacci State Transition
Begin with
\[ (1,1). \]Then
\[ (1,1)\to(1,2), \] \[ (1,2)\to(2,3), \] \[ (2,3)\to(3,5), \] \[ (3,5)\to(5,8). \]The pair representation contains exactly the information needed to continue.
Third-Order Recurrences as State Transitions
Suppose
\[ a_{n+1}=a_n+a_{n-2}. \]The update reaches back three positions, so a useful state is
\[ \boxed{(a_{n-2},a_{n-1},a_n)}. \]The transition becomes
\[ (x,y,z)\longrightarrow(y,z,z+x). \]State Vectors
When several quantities are needed to describe a state, they can be grouped into a vector.
For example,
\[ \mathbf{s}_n= \begin{bmatrix} x_n\\ y_n \end{bmatrix}. \]A transition rule then updates the entire vector:
\[ \boxed{\mathbf{s}_{n+1}=T(\mathbf{s}_n)}. \]Example: Two-Variable State
Suppose
\[ x_{n+1}=x_n+y_n, \] \[ y_{n+1}=x_n. \]Then
\[ \mathbf{s}_n= \begin{bmatrix} x_n\\ y_n \end{bmatrix} \]contains all information needed for the next step.
Starting from
\[ (x_0,y_0)=(1,1), \]we get
\[ (1,1)\to(2,1)\to(3,2)\to(5,3)\to\cdots. \]Linear State Transitions
Some multi-variable transitions are linear.
For example,
\[ x_{n+1}=2x_n+y_n, \] \[ y_{n+1}=x_n+3y_n. \]The next state is a linear combination of the current state variables.
Matrix notation provides a compact way to represent such systems, though detailed matrix iteration is beyond the main scope of this lesson.
Iteration as Repeated Function Composition
Applying \(T\) twice gives
\[ T(T(x)). \]Applying it three times gives
\[ T(T(T(x))). \]A compact notation is
\[ T^2(x),\qquad T^3(x), \]where the exponent indicates repeated composition, not ordinary multiplication.
Iterates
The \(k\)th iterate of a transition rule is
\[ \boxed{T^k}. \]If
\[ s_{n+1}=T(s_n), \]then
\[ s_n=T^n(s_0). \]This notation expresses the entire trajectory through repeated composition.
Example: Repeated Translation
Let
\[ T(x)=x+3. \]Then
\[ T^2(x)=x+6, \] \[ T^3(x)=x+9. \]More generally,
\[ \boxed{T^n(x)=x+3n}. \]This recovers the explicit form of an arithmetic recurrence.
Example: Repeated Scaling
Let
\[ T(x)=2x. \]Then
\[ T^2(x)=4x, \] \[ T^3(x)=8x. \]In general,
\[ \boxed{T^n(x)=2^nx}. \]This recovers the explicit form of a geometric recurrence.
Stable-Looking Fixed Points
Consider
\[ x_{n+1}=0.5x_n+6. \]The fixed point is \(12\).
Starting at \(x_0=20\),
\[ x_1=16, \] \[ x_2=14, \] \[ x_3=13, \] \[ x_4=12.5. \]The trajectory moves toward \(12\).
Unstable-Looking Fixed Points
Consider
\[ x_{n+1}=2x_n. \]The fixed point is
\[ x=0. \]But starting at a nearby nonzero value such as
\[ x_0=0.1 \]gives
\[ 0.1,\ 0.2,\ 0.4,\ 0.8,\ldots \]which moves away from \(0\).
Local Stability Idea
A fixed point is informally called stable or attracting when nearby states tend to move toward it under iteration.
It is informally called unstable or repelling when nearby states tend to move away.
Precise stability tests belong to later analysis, but the trajectory viewpoint already makes the distinction visible.
Example: Affine Transition toward Equilibrium
Let
\[ x_{n+1}=0.8x_n+10. \]The fixed point satisfies
\[ x=0.8x+10, \]so
\[ x=50. \]Starting at \(x_0=0\),
\[ 0,\ 10,\ 18,\ 24.4,\ 29.52,\ldots \]moves toward \(50\).
Iteration in Algorithms
Many algorithms repeatedly update a state until a stopping condition is met.
A simple iterative algorithm may have the form:
- begin with state \(s_0\);
- compute \(s_{n+1}=T(s_n)\);
- check whether a stopping condition holds;
- if not, repeat.
Recurrence relations provide a mathematical description of such repeated updates.
Stopping States
Some processes terminate when they enter a designated state.
For example, consider
\[ x_{n+1}=x_n-1 \]while \(x_n>0\).
Starting from \(4\),
\[ 4\to3\to2\to1\to0. \]If the rule stops at \(0\), then \(0\) is a terminal state rather than a state from which another update is required.
Absorbing States
An absorbing state is a state that, once entered, cannot be left.
In a deterministic system, this usually means
\[ T(s)=s. \]Thus, an absorbing state is a fixed state under the transition rule.
Iteration in Population Models
A population model may update once per year:
\[ P_{n+1}=1.04P_n. \]The state is the current population.
The transition rule multiplies it by \(1.04\).
The trajectory records the population over successive years.
Iteration in Financial Models
Suppose a balance earns \(3\%\) per period and receives a deposit of \(\$100\):
\[ B_{n+1}=1.03B_n+100. \]The current balance is the state.
Each transition applies growth and then adds the new deposit.
Iteration in Inventory Models
Suppose inventory changes according to
\[ I_{n+1}=I_n+R_n-S_n, \]where \(R_n\) is incoming stock and \(S_n\) is outgoing stock.
The state transition records the balance between arrivals and departures during each period.
Iteration and Finite Automata
A finite automaton moves among finitely many states according to transition rules.
The current state summarizes relevant past information, and each new input determines the next state.
This is a broader version of the same state-transition principle used in recurrence relations.
State Must Contain Enough Information
A poorly chosen state may omit information needed to determine the next step.
For the recurrence
\[ a_{n+1}=a_n+a_{n-1}, \]the single value \(a_n\) is not enough.
The pair
\[ (a_{n-1},a_n) \]is sufficient.
A good state representation contains all information required by the update rule and no unnecessary history.
Minimal State Idea
The minimal state is the smallest collection of information sufficient to determine the future evolution.
For
\[ a_{n+1}=2a_n+1, \]the current value \(a_n\) is sufficient.
For
\[ a_{n+1}=a_n+a_{n-1}, \]two consecutive values are needed.
Common Error: Confusing State with Time
The index \(n\) identifies the step.
The state \(s_n\) records the system's condition at that step.
These are different quantities.
In
\[ s_{n+1}=2s_n, \]\(n\) is the step number, while \(s_n\) is the state value.
Common Error: Applying the Rule to the Wrong State
To find \(s_{n+1}\), apply the transition rule to \(s_n\).
For
\[ s_{n+1}=3s_n+1, \]computing \(s_5\) requires \(s_4\), not \(s_3\).
Common Error: Treating \(T^2(x)\) as \([T(x)]^2\)
In iteration notation,
\[ T^2(x) \]usually means
\[ \boxed{T(T(x))}, \]not the square of the number \(T(x)\).
Context distinguishes composition from ordinary exponentiation.
Common Error: Calling Any Repeated Value a Fixed Point
A fixed point must satisfy
\[ T(s)=s. \]In a two-cycle,
\[ A\to B\to A, \]neither \(A\) nor \(B\) is fixed unless one maps to itself.
The pair is periodic, but the individual states are not fixed.
Common Error: Ignoring Transient Behavior
A trajectory can wander through several nonrepeating states before entering a cycle.
Therefore, eventual periodicity does not mean the sequence repeats from the beginning.
Transient states may precede the repeating part.
Common Error: Using an Incomplete State for a Higher-Order Recurrence
For
\[ a_{n+1}=a_n+a_{n-1}, \]the state \(a_n\) alone is incomplete.
A valid state must include
\[ \boxed{(a_{n-1},a_n)}. \]Common Error: Assuming Finite State Means Immediate Repetition
A finite deterministic system must eventually repeat, but it may first pass through many different states.
The guarantee is eventual periodicity, not immediate periodicity.
A Reliable Procedure for Iterating a Rule
- Identify the state variable or state vector.
- Write the transition rule clearly.
- Identify the initial state.
- Apply the rule once to obtain the next state.
- Use the new state as the input for the next step.
- Continue in order.
- Watch for fixed states, cycles, or stopping conditions.
A Reliable Procedure for Finding Fixed Points
- Write the transition rule \(s_{n+1}=T(s_n)\).
- Set the next state equal to the current state.
- Solve \(T(s)=s\).
- Substitute the solution back into the rule.
- Interpret the fixed state in context.
A Reliable Procedure for Finite-State Analysis
- List the possible states.
- Record the transition from each state.
- Choose the initial state.
- Follow the transitions in order.
- Mark the first repeated state.
- Separate transient states from the eventual cycle.
- Determine the cycle length.
A Reliable Procedure for Higher-Order Recurrences
- Identify how many previous terms determine the next term.
- Package those terms into an ordered state.
- Shift the components forward after each update.
- Compute the new final component using the recurrence.
- Repeat the resulting first-order state transition.
Practice 1: Iterate a Rule
Let
\[ x_{n+1}=2x_n+1 \]with
\[ x_0=2. \]Find \(x_1,x_2,x_3,x_4\).
Practice 2: Find a Fixed Point
Find the fixed point of
\[ T(x)=0.75x+5. \]Practice 3: Identify a Two-Cycle
Let
\[ T(x)=2-x. \]Starting from \(x_0=0\), generate four transitions and identify the cycle.
Practice 4: Modular State Transition
Let
\[ x_{n+1}\equiv x_n+3\pmod7 \]with
\[ x_0=0. \]List states until the first return to \(0\).
Practice 5: Fibonacci State Pair
For
\[ a_{n+1}=a_n+a_{n-1}, \]begin with state
\[ (a_1,a_2)=(2,3). \]List the next four state pairs.
Practice 6: Convert a Difference Equation
Convert
\[ \Delta x_n=4-0.25x_n \]into transition form.
Practice 7: Determine Eventual Behavior
A finite deterministic system has transitions
\[ A\to B,\qquad B\to D,\qquad C\to A,\qquad D\to B. \]Starting from \(C\), identify the transient states and eventual cycle.
Practice 8: Repeated Function Composition
Let
\[ T(x)=x+4. \]Find \(T^2(x)\), \(T^3(x)\), and \(T^n(x)\).
Practice 9: State Dimension
What state information is sufficient for the recurrence
\[ a_{n+1}=2a_n-a_{n-2}? \]Practice 10: Financial State Transition
An account earns \(2\%\) per period and receives a \(\$75\) deposit after the growth is applied.
Write the state-transition rule for the balance \(B_n\).
Practice Answers
Practice 1
\[ x_1=2(2)+1=5, \] \[ x_2=2(5)+1=11, \] \[ x_3=2(11)+1=23, \] \[ x_4=2(23)+1=47. \]Therefore,
\[ \boxed{x_1=5,\quad x_2=11,\quad x_3=23,\quad x_4=47}. \]Practice 2
A fixed point satisfies
\[ x=0.75x+5. \]Therefore,
\[ 0.25x=5, \] \[ \boxed{x=20}. \]Practice 3
Starting at \(0\),
\[ 0\to2\to0\to2\to0. \]Therefore, the cycle is
\[ \boxed{0\leftrightarrow2} \]with period \(2\).
Practice 4
\[ 0\to3\to6\to2\to5\to1\to4\to0. \]Therefore, the trajectory cycles through all seven residue classes.
Practice 5
The transition is
\[ (x,y)\to(y,x+y). \]Starting from \((2,3)\),
\[ (2,3)\to(3,5)\to(5,8)\to(8,13)\to(13,21). \]The next four state pairs are
\[ \boxed{(3,5),\ (5,8),\ (8,13),\ (13,21)}. \]Practice 6
\[ x_{n+1}-x_n=4-0.25x_n. \]Therefore,
\[ x_{n+1} = 0.75x_n+4. \]Thus,
\[ \boxed{x_{n+1}=0.75x_n+4}. \]Practice 7
Starting from \(C\),
\[ C\to A\to B\to D\to B\to D\to\cdots. \]The transient states are
\[ \boxed{C,\ A}. \]The eventual cycle is
\[ \boxed{B\leftrightarrow D}. \]Practice 8
\[ T^2(x)=x+8, \] \[ T^3(x)=x+12. \]In general,
\[ \boxed{T^n(x)=x+4n}. \]Practice 9
The recurrence uses
\[ a_n \]and
\[ a_{n-2}. \]To update consistently while shifting indices, a convenient complete state is
\[ \boxed{(a_{n-2},a_{n-1},a_n)}. \]Practice 10
A \(2\%\) increase multiplies the balance by
\[ 1.02. \]Then the deposit adds \(75\):
\[ \boxed{B_{n+1}=1.02B_n+75}. \]What to Remember
Iteration repeatedly applies a state-transition rule:
\[ \boxed{s_{n+1}=T(s_n)}. \]- A state contains the information needed to determine what happens next.
- A transition is one application of the update rule.
- The resulting sequence of states is a trajectory or orbit.
- Recurrence relations and difference equations can be interpreted as state-transition systems.
- A fixed point satisfies \(T(s)=s\).
- A cycle repeats after a finite number of transitions.
- Finite deterministic systems are eventually periodic.
- Higher-order recurrences can be converted into first-order transitions on larger state spaces.
- State vectors organize systems with several evolving quantities.
- Iteration appears throughout algorithms, modeling, automata, and discrete dynamical systems.
Where We Go Next
Iteration describes how a rule generates a trajectory step by step. In many cases, however, we also want a direct formula that gives the state at a distant index without generating every intermediate step.
The next lesson, Closed Forms, develops the idea of replacing recursive descriptions with explicit formulas, explains what makes a formula a closed form, and compares direct evaluation with recursive computation.