Recurrences path · R03

Before this lesson: Classifying recurrence relations, Sequences and sums, Mathematical induction: the first principle

Your goal: Transform a first-order recurrence and verify its explicit formula.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Names you may know: first-order difference equations.

First-order linear recurrences: the key idea

For aₙ₊₁=raₙ+c, first look for a fixed point L=rL+c. When r≠1, L=c/(1−r), and bₙ=aₙ−L satisfies bₙ₊₁=rbₙ. Thus an=L+(a0−L)rna_{n}=L+(a_{0}-L)r^{n}. When r=1 the recurrence is arithmetic: aₙ=a₀+nc. For variable forcing f(n), iteration gives an=rna0+∑j=0n−1rn−1−jf(j)a_{n}=r^{n}a_{0}+\sum_{j=0}^{n-1}r^{n-1-j}f(j). One may also divide by a geometric factor when r≠0 to obtain a telescoping difference.

A worked example

Solve a₀=1, aₙ₊₁=2aₙ+3.

The fixed point is L=−3. Set bₙ=aₙ+3; then bₙ₊₁=2bₙ and b₀=4. Hence an=4⋅2n−3a_{n}=4\cdot 2^{n}-3. It gives 1 at n=0 and satisfies the recurrence.

Your turn: change one thing

Solve b₀=2, bₙ₊₁=bₙ+2n+1.

Try this on paper before opening the explanation.

Compare your reasoning

Summing the differences from 0 to n−1 gives bₙ−2=1+3+⋯+(2n−1)=n². Thus bₙ=n²+2.

Pause and check

A trap to avoid: Off-by-one indices or an explicit formula that misses the initial value.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Derive the solution for aₙ₊₁=raₙ+c when r≠1.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

Let L=c/(1−r), so rL+c=L. Subtraction yields aₙ₊₁−L=r(aₙ−L). Induction gives an−L=rn(a0−L)a_{n}-L=r^{n}(a_{0}-L). Rearranging proves the formula and also verifies the initial value.

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. A fixed point L of aₙ₊₁=raₙ+c satisfies what?

Foundation

  1. L=0 always
  2. L=rL−c
  3. L=rL+c
  4. L=r+c always
Hint

A constant sequence must obey the same rule.

Answer and reasoning

L=rL+c. Substitute L for both successive terms.

2. When r=1 and forcing is constant c, the sequence is what?

Foundation

  1. Periodic of length two
  2. Arithmetic
  3. Always geometric
  4. Undefined
Hint

Each step adds c.

Answer and reasoning

Arithmetic. aₙ=a₀+nc.

3. For aₙ₊₁=2aₙ+3, the fixed point is what?

Core

  1. 3
  2. −1
  3. 2
  4. −3
Hint

Solve L=2L+3.

Answer and reasoning

−3. Subtract 2L to obtain −L=3, hence L=−3.

4. With a₀=1 and aₙ₊₁=2aₙ+3, a₂ is what?

Core

  1. 13
  2. 7
  3. 11
  4. 16
Hint

Compute a₁ first.

Answer and reasoning

13. a₁=5 and a₂=2·5+3=13.

5. Which shift makes aₙ₊₁=2aₙ+3 geometric?

Stretch

  1. bₙ=aₙ+3
  2. bₙ=aₙ−3
  3. bₙ=aₙ²
  4. bₙ=3aₙ
Hint

Subtract the fixed point −3.

Answer and reasoning

bₙ=aₙ+3. bₙ₊₁=aₙ₊₁+3=2(aₙ+3)=2bₙ.

6. If b₀=2 and bₙ₊₁−bₙ=2n+1, bₙ equals what?

Stretch

  1. n²+2
  2. 2n+2
  3. n²
  4. n(n+1)+2
Hint

Sum the first n odd numbers.

Answer and reasoning

n²+2. The accumulated increment is n².

7. An arithmetic recurrence adds what at every step?

Foundation

  1. The square of the term
  2. A random value
  3. A fixed difference
  4. A fixed factor only
Hint

Compare successive terms.

Answer and reasoning

A fixed difference. aₙ₊₁−aₙ is constant.

8. a₀=2 and aₙ₊₁=3aₙ+2. What is a₁?

Core

  1. 7
  2. 10
  3. 8
  4. 6
Hint

Apply the rule once.

Answer and reasoning

8. 3·2+2=8.

9. For aₙ₊₁=raₙ+c, why treat r=1 separately?

Stretch

  1. The fixed-point formula divides by 1−r
  2. The sequence has no terms
  3. All terms must vanish
  4. The recurrence becomes nonlinear
Hint

At r=1 that denominator is zero.

Answer and reasoning

The fixed-point formula divides by 1−r. The separate arithmetic formula aₙ=a₀+nc applies.

Choose your next step

Continue to Nonlinear recurrences and substitutions. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.