Understand · explore · practise

Recurrence relations

Generate sequences from recurrence relations, recover initial values and constants, handle nonlinear rules, and verify explicit formulas including two-step recurrences.

Before you startSubstitution, algebraic equations and sequence notation

01 / A rule using earlier terms

An initial value starts the process.

A recurrence relation defines a term using one or more earlier terms. For uₙ₊₁ = 2uₙ + 1, read it as “double the current term, then add 1 to get the next term”. An initial value is needed to select a particular sequence.

u₁ = 3 and uₙ₊₁ = 2uₙ + 1Worked example

u₂ = 2(3) + 1 = 7

Use the first term to calculate the second.

u₃ = 2(7) + 1 = 15

Now use the second term, not the initial value again.

u₄ = 2(15) + 1 = 31

Continue one step at a time.

Substituting n = 100 into a recurrence does not by itself give a numerical u₁₀₀. It relates that term to another term that may still be unknown.

Keep the previous terms in viewExplore

u₁ = 3; uₙ₊₁ = 2uₙ + 1.

u₁ = 3
u₂ = 7
u₃ = 15
u₄ = 31

Use u₃ = 15: 2 × 15 + 1 = 31.

Recurrence Terms shown 4

Watch each output become the next input

Pause, replay or seek freely. The notes explain the same idea and stay in view.

02 / Check where the indexing starts

u₀ and u₁ describe different starting conventions.

u₀ = 4 and uₙ₊₁ = 2uₙ + 3Worked example

u₁ = 2(4) + 3 = 11

One application moves from index 0 to index 1.

u₂ = 2(11) + 3 = 25

There have now been two applications.

u₃ = 2(25) + 3 = 53

Do not relabel the given u₀ as u₁.

With a starting term u₁, reaching uₙ takes n − 1 applications of a one-step rule. With starting term u₀, it takes n applications. Include the indices in your working.

03 / Arithmetic and geometric recurrences

A constant addition differs from a constant multiplier.

Arithmetic: u₁ = a, uₙ₊₁ = uₙ + d
Geometric: u₁ = a, uₙ₊₁ = ruₙ

An arithmetic rule adds the same number; a geometric rule multiplies by the same number. The rule 2uₙ + 1 usually gives neither an arithmetic nor a geometric sequence.

Connect a recurrence to a direct formulaWorked example

u₁ = 3, uₙ₊₁ = 2uₙ + 1

The terms begin 3, 7, 15, 31.

uₙ₊₁ + 1 = 2(uₙ + 1)

Adding 1 to each term creates a geometric sequence.

uₙ + 1 = 4 × 2^(n − 1) ⇒ uₙ = 2^(n + 1) − 1

The transformed first term is 4, and its ratio is 2.

A transformed sequence can be simple even when the original one is not. Always check the starting value as well as the recurrence.

04 / Find unknown constants

Use consecutive pairs to form equations.

uₙ₊₁ = puₙ + q, with u₁ = 2, u₂ = 7, u₃ = 22Worked example

2p + q = 7 and 7p + q = 22

Each known transition gives one equation.

5p = 15 ⇒ p = 3

Subtract to eliminate q.

q = 1

Substituting back gives the rule uₙ₊₁ = 3uₙ + 1.

If the two input terms are equal, these two equations may not be independent. Do not assume a pair of parameters is uniquely determined without checking.

A symbolic initial valueWorked example

u₁ = t and uₙ₊₁ = 3uₙ − 2

Keep the parameter until the condition is applied.

u₂ = 3t − 2; u₃ = 3(3t − 2) − 2 = 9t − 8

Substitute the whole previous expression in brackets.

If u₃ = 37, then 9t − 8 = 37 ⇒ t = 5

Check 5, 13, 37 satisfies the rule.

05 / Recover an earlier term

Reverse the actual operation; uniqueness is not automatic.

uₙ₊₁ = 2uₙ − 1 and u₃ = 19Worked example

u₂ = (19 + 1)/2 = 10

Undo subtracting 1, then undo doubling.

u₁ = (10 + 1)/2 = 11/2

The starting term need not be an integer.

2(11/2) − 1 = 10; 2(10) − 1 = 19

Check forwards to verify the recovery.

For uₙ₊₁ = uₙ² − 2, knowing u₂ = 7 gives u₁² = 9, so u₁ = 3 or −3. A nonlinear rule can lose information, leaving more than one earlier value.

06 / Nonlinear rules and valid domains

Check that every requested step is defined.

u₁ = 2 and uₙ₊₁ = uₙ² − 1Worked example

u₂ = 2² − 1 = 3

Square the entire current term.

u₃ = 3² − 1 = 8

Use the new result as the input.

u₄ = 8² − 1 = 63

The growth is not multiplication by a constant.

A rule that stops being definedWorked example

u₁ = 2, uₙ₊₁ = 1/(uₙ − 1)

The denominator must not be zero.

u₂ = 1/(2 − 1) = 1

The first transition is defined.

u₃ would require 1/(1 − 1)

This is undefined. The proposed rule does not generate a real sequence at every later index from this start.

Similarly, square roots need nonnegative inputs and logarithms need positive inputs. A few valid terms do not prove that all later terms are defined.

07 / Verify an explicit formula

Check the initial term and the rule for a general index.

Verify uₙ = 4 × 3^(n − 1) − 2 for u₁ = 2, uₙ₊₁ = 3uₙ + 4Worked example

At n = 1: 4 × 3⁰ − 2 = 2

The proposed formula has the required initial value.

3uₙ + 4 = 3[4 × 3^(n − 1) − 2] + 4

Substitute the proposed expression into the recurrence.

= 4 × 3ⁿ − 2 = uₙ₊₁

This is the same formula with n replaced by n + 1.

The starting value and the deterministic recurrence uniquely determine each next term. Matching both verifies the formula for every index reached by the rule. Checking just the first few numerical values is not a general verification.

08 / Two-step recurrence extension

A rule using two earlier terms normally needs two initial values.

u₁ = 5, u₂ = 13, uₙ₊₂ = 5uₙ₊₁ − 6uₙWorked example

u₃ = 5(13) − 6(5) = 35

Use both preceding terms in the stated order.

u₄ = 5(35) − 6(13) = 97

Keep a running list so the two inputs are clear.

Claim: uₙ = 2ⁿ + 3ⁿ

At n = 1 and n = 2 it gives 5 and 13.

5(2^(n + 1) + 3^(n + 1)) − 6(2ⁿ + 3ⁿ)

Substitute the formula into the right side.

= (10 − 6)2ⁿ + (15 − 6)3ⁿ = 2^(n + 2) + 3^(n + 2)

The recurrence holds for general n, so the two starting checks verify the formula.

09 / Count digits

Compare with consecutive powers of 10.

For a positive integer N, the number of decimal digits is the unique integer d such that 10^(d − 1) ≤ N < 10ᵈ. Equivalently it is floor(log₁₀ N) + 1, taking care near a power of 10.

For example, u₂₀ = 2²⁰ + 3²⁰ = 3,487,832,977. Since 10⁹ ≤ u₂₀ < 10¹⁰, it has 10 digits. Use the verified explicit formula to reach distant terms without listing every earlier one.

How many digits does u₅₀₀ = 2⁵⁰⁰ + 3⁵⁰⁰ have?Worked example

3⁵⁰⁰ < u₅₀₀ < 2 × 3⁵⁰⁰

Both terms are positive and 2⁵⁰⁰ < 3⁵⁰⁰.

500log₁₀ 3 < log₁₀ u₅₀₀ < log₁₀ 2 + 500log₁₀ 3

Logarithms preserve the inequalities.

238.5606… < log₁₀ u₅₀₀ < 238.8616…

Both bounds lie strictly between 238 and 239.

Using the verified rule uₙ = 2ⁿ + 3ⁿ, how many decimal digits does u₁₅ have?

Hint

Find the value, then place it between consecutive powers of 10.

Worked solution

u₁₅ = 32,768 + 14,348,907 = 14,381,675. Since 10⁷ ≤ u₁₅ < 10⁸, it has 8 digits.

11 / Recap

A recurrence is a process with a starting condition.

Use the latest term as the next input.
Check the initial index and the number of applications.
Consecutive data can determine unknown recurrence constants.
Backward steps can be ambiguous for nonlinear rules.
Check domains before each requested substitution.
Verify an explicit formula using both initial conditions and the general recurrence.
A two-step rule normally needs two initial terms.

Back to sequences and series →

Section 1 of 11 · A rule using earlier terms