Finite states, cycles and recurrence invariants
Concept in depth
A recurrence is a state machine: once exactly the same required state reappears, determinism guarantees that the entire future repeats. For a second-order rule, the ordered pair—not one value—is the state that must repeat.
Method cue
Compute only until a full state repeats, record the cycle's first index and length, then find where the distant term falls within that repeating cycle.
Worked synthesis
Let and . Find .
. The value repeats from , so the deterministic first-order rule now cycles through . Since is even, .
Contrast example · different route
Let and . For which indices is even?
Track the odd/even pairs: (odd, odd), (odd, even), (even, odd), then (odd, odd) again. The full pair repeats, so is even exactly when is divisible by .
Why it changes: This rule is second-order, so repeating one value is not enough; the ordered pair is the state.
Five-option check on a new question
Let , and . How many of the first terms are even?
- A
- B
- C
- D
- E
The odd/even pattern repeats every three terms. The even terms have indices . There are .
Next · matched practice
Now recognise the same state decision in a linked recurrence question without being told the route.
A free Forge account includes 41 lessons and four advanced methods. Premium unlocks all 104 lessons, all 18 methods, your weekly plan, the full question bank and unlimited mocks.