1.04e–1.04g - Sequences, recurrence and sigma notation

You already know

A function takes an input and produces an output. Substituting a value into $2x-1$ means doubling that value and then subtracting $1$.

Sequence, explicit rule and recurrence

A sequence is an ordered list with a term at each permitted integer position. An explicit rule gives a term directly from its position, such as $u_n=n^2+1$. A recurrence gives a term from earlier terms, such as $u_{n+1}=2u_n-1$, and needs enough initial values to start it. Always specify whether the first index is $0$ or $1$.

Worked example 1: feed the previous output back in

Question. For $u_1=3$ and $u_{n+1}=2u_n-1$, find $u_2,u_3,u_4$.

Plan. Apply the recurrence successively, using the previous term rather than its index.

Why not put $n=3$ into $2u_n-1$ as $2(3)-1$? The input is the value $u_3=9$, not the position $3$.

Answer. $u_2=5,\ u_3=9,\ u_4=17$.

Check. Substituting $u_3=9$ gives the stated fourth term $17$.

Worked example 2: a fixed starting value

Question. For $u_1=1$ and $u_{n+1}=2u_n-1$, find $u_2,u_3,u_4$, and describe all later terms.

Plan. Generate terms, then check whether the starting value is returned unchanged by the rule.

Why does this establish every later term? Whenever the input is $1$, the output is exactly $1$, so it remains available as the next input.

Answer. Every term equals $1$; the sequence is constant.

Check. The fixed-value equation $L=2L-1$ gives $L=1$.

Watch out

Wrong: generate a recurrence by inserting $n=1,2,3$ as its inputs. Right: insert the preceding term. A recurrence without an initial value generally describes many possible sequences.

Finite, increasing and periodic

A finite sequence has a last position; an infinite sequence has endlessly many positions. Here increasing means $u_{n+1}>u_n$ at every consecutive pair, and decreasing means $u_{n+1}<u_n$. A periodic sequence repeats after a fixed positive integer number of positions: $u_{n+p}=u_n$. Its period is the smallest such $p$.

Worked example 3: a two-term cycle

Question. For $a_1=2$ and $a_{n+1}=5-a_n$, describe the sequence and its period.

Plan. Generate a block, then show that two applications of the rule return any input.

Why check two general steps? It establishes repetition for all positions, rather than just observing a short list.

Answer. $2,3,2,3,\ldots$ is infinite, neither increasing nor decreasing, and periodic with period $2$.

Check. The two terms differ, so the smallest period cannot be $1$.

Worked example 4: the constant boundary case

Question. For $a_1=5/2$ and $a_{n+1}=5-a_n$, describe the sequence and its period.

Plan. Test whether one step already returns the initial value.

Why is the period not $2$? Returning after two steps is true, but the definition asks for the smallest positive return length.

Answer. It is an infinite constant sequence with period $1$, neither strictly increasing nor strictly decreasing.

Check. Consecutive terms are equal, so neither strict inequality holds.

Watch out

Wrong: “infinite means the terms become arbitrarily large”. Right: it means there is no last position. A constant or a repeating sequence can have infinitely many terms.