Iterate a first-order recurrence

A first-order rule uses one preceding term

Here r and c are fixed and n is a nonnegative integer. First-order means only the immediately preceding term is needed. In this section r is nonzero; c and s may be positive, zero or negative. The initial condition is part of the definition

For u₀=4 and uₙ₊₁=−uₙ/2+3, find u₁

Recurrence rule

\(\displaystyle u_{n+1}=-\frac{u_n}{2}+3\)

Use the same rule and the value u₁=1 to find u₂

Which special case always gives an arithmetic sequence?

An equilibrium is a constant solution

If L=rL+c, starting at L gives L at every step. This does not mean every starting value approaches L. For uₙ₊₁=2uₙ−3, L=3, but a start of 4 gives 4,5,7,11,...

Use technology with an explicit index column

In a spreadsheet put index 0 and the initial value in the first data row. Each next row refers to the immediately preceding value. Fill the formula down once per transition and keep full precision. A plot of the generated sequence uses separate points at integer indices; a joining line is only a visual guide, not extra sequence values

Construct an iterator, ungraded

Write pseudocode that accepts an integer N≥0, a starting value s and constants r≠0,c, then returns u_N. Show the zero-step case and explain why the routine is correct. Independent program construction and justification are ungraded

Model: state, invariant and termination

Set value←s and k←0. While k<N: set value←r×value+c, then k←k+1. Return value. The invariant is value=u_k: it holds initially and one update applies the recurrence to obtain u_(k+1). When k=N the returned value is u_N. If N=0 the loop runs zero times. The integer N−k decreases by one each iteration, so termination follows