Recurrences path · R04

Before this lesson: First-order linear recurrences, Equations and quadratic tools

Your goal: Find a substitution suggested by the recurrence rather than guessing at random.

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.

Nonlinear recurrences and substitutions: the key idea

A nonlinear recurrence may become linear after a change of variable. Reciprocal substitutions help with rational rules such as aₙ₊₁=aₙ/(1+aₙ): if all terms are nonzero, bₙ=1/aₙ gives bₙ₊₁=bₙ+1. First prove the denominators and substitution remain valid. Other useful ideas include factoring aₙ₊₁−aₙ, bounding the terms, or finding an invariant. A transformation that loses a zero solution must treat that solution separately.

A worked example

Solve a₀=1 and aₙ₊₁=aₙ/(1+aₙ).

Positivity is preserved, so no denominator or aₙ is zero. Let bₙ=1/aₙ. Then bₙ₊₁=1+1/aₙ=bₙ+1 with b₀=1. Therefore bₙ=n+1 and aₙ=1/(n+1).

Your turn: change one thing

What happens with the same recurrence when a₀=0?

Try this on paper before opening the explanation.

Compare your reasoning

Every term is zero. The reciprocal substitution is invalid, but the original recurrence gives this solution directly.

Pause and check

A trap to avoid: Dividing by a term that could be zero or using an inadmissible radical branch.

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

For a₀>0 prove the terms of this recurrence are positive and strictly decreasing.

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

If aₙ>0 then 1+aₙ>1. Hence 0<aₙ/(1+aₙ)<aₙ. Starting from a₀>0, induction establishes positivity and the strict decrease at every step.

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. For aₙ₊₁=aₙ/(1+aₙ), which substitution is useful when aₙ≠0?

Foundation

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

Take reciprocals of the entire rule.

Answer and reasoning

bₙ=1/aₙ. 1/aₙ₊₁=1/aₙ+1.

2. What must be checked before taking reciprocals?

Foundation

  1. The sequence is finite
  2. The terms are even
  3. The terms are nonzero
  4. The terms are integers
Hint

Division by zero is undefined.

Answer and reasoning

The terms are nonzero. A valid substitution needs nonzero values at every used index.

3. For a₀=1 under this rule, a₂ equals what?

Core

  1. 1/2
  2. 1/4
  3. 2/3
  4. 1/3
Hint

The explicit formula is 1/(n+1).

Answer and reasoning

1/3. a₁=1/2, then a₂=(1/2)/(3/2)=1/3.

4. For a₀=0 under this rule, what is a₅?

Core

  1. 0
  2. 1/6
  3. 1
  4. Undefined
Hint

Use the original recurrence.

Answer and reasoning

0. Zero maps to zero at every step.

5. For positive aₙ, why is the next term smaller?

Stretch

  1. Reciprocals preserve order
  2. It is divided by 1+aₙ>1
  3. The numerator is negative
  4. Every nonlinear sequence decreases
Hint

Compare the denominator to 1.

Answer and reasoning

It is divided by 1+aₙ>1. Dividing a positive number by a number greater than 1 decreases it.

6. Why handle a₀=0 separately?

Stretch

  1. It is a prime case
  2. The reciprocal change of variable excludes it
  3. It is not a real number
  4. It makes 1+a₀ zero
Hint

The transformed system has a narrower domain.

Answer and reasoning

The reciprocal change of variable excludes it. The original recurrence permits zero, while 1/a₀ does not.

7. A substitution is valid only if what is checked?

Foundation

  1. The font of the formula
  2. That every term is prime
  3. That n is even
  4. Its domain along the sequence
Hint

Every introduced reciprocal or root has conditions.

Answer and reasoning

Its domain along the sequence. An invalid change of variable can lose solutions or use undefined expressions.

8. If a₀=2 and aₙ₊₁=aₙ/(1+aₙ), find a₁.

Core

  1. 1/3
  2. 3/2
  3. 1
  4. 2/3
Hint

Apply the fraction rule.

Answer and reasoning

2/3. 2/(1+2)=2/3.

9. For positive a₀ under that rule, what is the general form?

Stretch

  1. aₙ=1/(n+1/a₀)
  2. aₙ=a₀+n
  3. an=a02na_{n}=a_{0}^{2n}
  4. aₙ=1/(n+a₀) always
Hint

The reciprocal increases by 1 per step.

Answer and reasoning

aₙ=1/(n+1/a₀). 1/aₙ=n+1/a₀, and positivity makes inversion valid.

Choose your next step

Continue to Second-order linear recurrences. 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.