4.4 Iterative state updates

In Module 4.3, we used starting values and a rule to build each new value from earlier ones. We are doing the same thing here. The change is what we carry from one step to the next: instead of keeping only one number, we can keep several related values together as a state and update that whole state at once. Applying the rule again and again is called iteration.

This framing is useful when the next step needs more than one piece of information. A simulation may track several populations; an algorithm may track a position and a remaining resource. Putting the needed values together makes each update clear, repeatable, and easier to check. This is intermediate work built on the previous module. The OpenStax introduction to recursive sequences reviews the one-number version.

A basic idea: keep the needed values together

The staircase example in Module 4.3 used $w_{n+1}=w_n+w_{n-1}$: the next count needs the two latest counts. Keep those two counts as one state, $(x,y)=(w_{n-1},w_n)$. The recurrence can now be written as an update of the pair:

$$(x_{\text{new}},y_{\text{new}})=(y_{\text{old}},x_{\text{old}}+y_{\text{old}}).$$

The first entry becomes the old second entry; the second entry becomes the sum of the old two. This is the previous recurrence in a different form. The state is a snapshot of what the rule needs now, and the update produces the next snapshot. We no longer have to look back through the whole history for the two values.

For the animation, choose the starting state $(0,1)$. The updates give $(1,1)$, then $(1,2)$, then $(2,3)$, then $(3,5)$. This uses the same pair rule as the staircase count but different starting values. Both new entries must use the same old pair. If you replace $x$ first and use that new $x$ to calculate $y$, you have changed the rule.

The animation follows this pair for four updates. Use Next to see which values feed the next round.

A quick tour of update questions

A state $s_t$ contains everything the rule needs at time $t$. An update has the form $s_{t+1}=F(s_t)$; the initial state $s_0$ makes the sequence determined. This is the same shape as $a_{n+1}=F(a_n)$ from Module 4.3, but $s_t$ can hold a pair or several values. A one-number counter is also a state, with just one entry. Before calculating, ask:

For a simulation, write a short table with columns for $t$, old state, and new state. If an action requires a condition such as energy $\ge4$, test it before applying that action. A bound such as $x_t\ge0$ may be a rule that stops the process, not just a fact to check afterwards.

An invariant is a quantity that the update preserves. For example, transferring one unit from $A$ to $B$ changes $(A,B)$ to $(A-1,B+1)$ but leaves $A+B$ unchanged. Finding an invariant can make a long iteration easier to verify.

Application 1: a robot's energy

A robot starts with $9$ energy units. A move requires at least $4$ units, uses $4$, and then a charger returns $2$ units. How many moves can it complete?

1. Set the state and rule. $E_0=9$. If $E_t\ge4$, then $E_{t+1}=E_t-4+2=E_t-2$.
2. Check before each move. From $9$ it reaches $7$, then $5$, then $3$.
3. Stop. At $3$, it cannot pay the next move's upfront cost of $4$. It completes three moves.

The final energy is positive, but that alone does not permit another move.

Application 2: generating neighbouring counts

Start with $(x_0,y_0)=(0,1)$ and update simultaneously by $(x_{t+1},y_{t+1})=(y_t,x_t+y_t)$. What is the state after four updates?

1. Record each old pair. $(0,1)\to(1,1)\to(1,2)\to(2,3)\to(3,5)$.
2. Count updates, not states. The start is time $0$, so the fifth pair shown is the state at time $4$.
3. Check the last transition. From old $(2,3)$, new $x=3$ and new $y=2+3=5$.

This pair update produces neighbouring Fibonacci counts. Its purpose here is the update discipline: calculate from the old pair, then replace both entries together.