Algebra & Functions · Recurrence relation

Recurrence relation

A recurrence relation gives each term of a sequence from the terms before it, so a rule and a first term fix the whole sequence. For aₙ₊₁ = p·aₙ + q the difference aₙ − α from the fixed point α = q/(1 − p) is multiplied by p at every step.

Recurrence relations in this visualization

A recurrence relation gives each term of a sequence from the terms before it. Together with a first term a0a_0, the rule an+1=p an+qa_{n+1} = p\,a_n + q fixes the whole sequence: a1=p a0+qa_1 = p\,a_0 + q, then a2=p a1+qa_2 = p\,a_1 + q, and so on. With p=1p = 1 it adds q at every step, an arithmetic sequence; with q=0q = 0 it multiplies by p, a geometric one. The left view plots a0a_0 to a20a_{20} against n; the right one draws the rule itself, as the line y=px+qy = px + q.

Why the difference from the fixed point is geometric

When p≠1p \ne 1, one value stays where it is under the rule: the fixed point α=q1−p\alpha = \frac{q}{1 - p}, the solution of α=pα+q\alpha = p\alpha + q. Subtract that equation from an+1=p an+qa_{n+1} = p\,a_n + q and q drops out: an+1−α=p (an−α)a_{n+1} - \alpha = p\,(a_n - \alpha). Each step multiplies the difference an−αa_n - \alpha by p, so the differences form a geometric sequence, and an=α+pn(a0−α)a_n = \alpha + p^n (a_0 - \alpha). The yellow bars are these differences. From 0 with p=0.5p = 0.5 and q=3q = 3 they are −6, −3, −1.5, …, so an=6−6⋅0.5na_n = 6 - 6 \cdot 0.5^n: the terms come as close to 6 as you like but never reach it, and a20≈5.999994a_{20} \approx 5.999994. With p=1p = 1 and q≠0q \ne 0 there is no fixed point, and an=a0+nqa_n = a_0 + nq.

Where the sequence goes

Where the sequence goes depends on p. If ∣p∣<1|p| < 1, the distance shrinks and the sequence tends to α, from one side when p is positive, and from above and below in turn when it is negative. If ∣p∣>1|p| > 1, the distance grows, and every start except α itself is pushed away. With p=−1p = -1 the distance keeps its size, and the terms alternate between a0a_0 and q−a0q - a_0. The cobweb shows why. Go up from ana_n to the line to get an+1a_{n+1}, then across to the diagonal y=xy = x to use it as the next input. Its axes are ana_n and an+1a_{n+1}, not n: the path is the calculation, not a graph of the sequence. α is where the line crosses the diagonal. A line less steep than the diagonal pulls the path in toward α; a steeper one pushes it out.

A loan works this way. A balance charged 1% a month, with 100 paid each month, follows bn+1=1.01 bn−100b_{n+1} = 1.01\,b_n - 100, whose fixed point is 10000: the interest on 10000 is exactly the payment. A balance of 9000 falls to about 8873.17 after a year; one of 11000 grows to about 11126.83, though the same 100 is paid every month.

Things to notice

  • The rule alone does not fix a sequence: every first term gives a different one.
  • Each Fibonacci number uses the two before it, so that sequence needs two starting terms.
  • When the rule is not linear, there can be several fixed points, some that pull the terms in and some that push them away, as in the logistic map.

Controls

  • Drag the first term: the blue point at n = 0 up or down, or the hollow blue start along the cobweb's axis. It catches the fixed point. The wheel and the field set it too.
  • The knobs turn p and q; their fields, like the first term's, take exact values such as 1/3.
  • With the keyboard, Tab to either blue point and use the arrow keys; hold Shift to move by whole numbers.

Related