Recurrences path · R01

Before this lesson: Sequences and sums

Your goal: Compute terms and explain why initial conditions matter.

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.

Recursive sequences: the key idea

A recurrence defines a term from earlier terms, together with starting values. The recurrence alone often describes many sequences. State the first index and enough initial terms before computing. An explicit formula gives aₙ directly from n; verify it against both the recurrence and initial conditions. Compute a few terms to discover a candidate, then prove it rather than extrapolating the pattern.

A worked example

Let a₀=2 and aₙ₊₁=3aₙ. Find a formula.

The first terms are 2,6,18,54. The candidate is an=2⋅3na_{n}=2\cdot 3^{n}. It gives a₀=2 and 2⋅3n+1=3(2⋅3n)2\cdot 3^{n+1}=3(2\cdot 3^{n}), so it meets the rule for every n≥0.

Your turn: change one thing

Let b₁=4 and bₙ₊₁=bₙ+5. Find bₙ.

Try this on paper before opening the explanation.

Compare your reasoning

There are n−1 increments after b₁, so bₙ=4+5(n−1)=5n−1. Check n=1 and the difference of successive terms.

Pause and check

A trap to avoid: Treating a few matching terms as proof of an explicit formula.

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

Prove that a first-order deterministic recurrence and one initial value determine at most one sequence.

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

Two candidate sequences agree initially. If their kth terms agree, applying the same recurrence rule gives equal next terms. Induction shows agreement at every subsequent index, provided the rule is defined along the sequence.

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. What is missing from aₙ₊₁=2aₙ if a unique sequence is required?

Foundation

  1. An initial value
  2. A graph
  3. A prime index
  4. A sum formula
Hint

Different first values give different sequences.

Answer and reasoning

An initial value. The rule determines the next term only after a starting value is chosen.

2. An explicit formula expresses aₙ using what?

Foundation

  1. n directly
  2. Only aₙ itself
  3. Only an unknown limit
  4. A random term
Hint

It avoids computing every preceding term.

Answer and reasoning

n directly. A direct formula gives the term from the index.

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

Core

  1. 6
  2. 24
  3. 12
  4. 48
Hint

Apply three doublings.

Answer and reasoning

24. a₁=6,a₂=12,a₃=24.

4. b₁=4,bₙ₊₁=bₙ+5. What is b₄?

Core

  1. 20
  2. 24
  3. 14
  4. 19
Hint

There are three increments.

Answer and reasoning

19. 4+3·5=19.

5. How should a proposed closed formula be verified?

Stretch

  1. Check its appearance
  2. Ignore the first index
  3. Check initial data and recurrence
  4. Check one large term
Hint

Both parts of the definition matter.

Answer and reasoning

Check initial data and recurrence. A formula satisfying the recurrence can still have incorrect constants or indexing.

6. Why does recurrence uniqueness follow by induction?

Stretch

  1. Initial values are unnecessary
  2. Equal preceding data give equal next terms
  3. Every sequence converges
  4. All recurrences are linear
Hint

The recurrence is deterministic.

Answer and reasoning

Equal preceding data give equal next terms. Agreement propagates from the initial data to every subsequent term.

7. Can different initial values share one recurrence rule?

Foundation

  1. No
  2. Only for nonlinear rules
  3. Only for finite sequences
  4. Yes
Hint

The rule and starting data are separate.

Answer and reasoning

Yes. For example aₙ₊₁=2aₙ allows many choices of a₀.

8. a₁=7 and aₙ₊₁=aₙ−2. What is a₄?

Core

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

Apply three decreases of 2.

Answer and reasoning

1. 7−3·2=1.

9. Why is matching several computed terms not enough to verify a formula?

Stretch

  1. The initial terms are irrelevant
  2. Every matching formula is identical
  3. Later terms may fail the recurrence
  4. All sequences are finite
Hint

Verify the defining rule for general n.

Answer and reasoning

Later terms may fail the recurrence. A proof needs the recurrence identity and the initial data, not a finite pattern alone.

Choose your next step

Continue to Classifying recurrence relations. 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.