Recurrences path · R02

Before this lesson: Recursive sequences, Algebraic identities and factorisation

Your goal: Classify a recurrence to select an appropriate method.

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.

Recurrence Relations: Order and Types: the key idea

The order is the number of preceding steps needed in a recurrence: aₙ₊₂=3aₙ₊₁−2aₙ has order two. A recurrence is linear when each sequence term appears to the first power and terms are not multiplied together. In a linear homogeneous recurrence, the equation has no independent forcing term after all sequence terms are moved to one side. Coefficients may depend on n; constant-coefficient methods do not automatically apply then. Classification guides a method but does not solve the problem by itself.

A worked example

Classify an+2=4an+1−4an+2na_{n+2}=4a_{n+1}-4a_{n}+2^{n}.

It is order two, linear, non-homogeneous, with constant coefficients on the sequence terms. The forcing term is 2n2^{n}.

Your turn: change one thing

Classify bₙ₊₁=bₙ²+1.

Try this on paper before opening the explanation.

Compare your reasoning

It has order one and is nonlinear because bₙ is squared. Linear characteristic-root methods do not apply directly.

Pause and check

A trap to avoid: Confusing order with polynomial degree or ignoring variable coefficients.

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

Explain why aₙ₊₁=(n+1)aₙ is linear despite the factor n+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

Linearity concerns the unknown sequence terms, not the index. Here aₙ₊₁ and aₙ each have exponent one and are not multiplied together. The coefficient n+1 varies with n, so the recurrence is linear homogeneous with variable coefficients.

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 the order of aₙ₊₂=aₙ₊₁+aₙ?

Foundation

  1. 3
  2. 0
  3. 2
  4. 1
Hint

Count the furthest previous step.

Answer and reasoning

2. The next term requires the two immediately preceding terms.

2. Which recurrence is nonlinear?

Foundation

  1. aₙ₊₂=aₙ₊₁+aₙ
  2. aₙ₊₁=aₙ+1
  3. aₙ₊₁=aₙ²+1
  4. aₙ₊₁=2aₙ
Hint

Look for a power of an unknown term.

Answer and reasoning

aₙ₊₁=aₙ²+1. The square of aₙ makes the recurrence nonlinear.

3. aₙ₊₁=3aₙ+7 is what type?

Core

  1. Nonlinear
  2. Order two
  3. Linear non-homogeneous
  4. Linear homogeneous
Hint

The independent term is 7.

Answer and reasoning

Linear non-homogeneous. It is order one and linear, with a nonzero forcing term.

4. aₙ₊₁=(n+1)aₙ has what kind of coefficient?

Core

  1. Variable
  2. Constant
  3. Undefined
  4. Quadratic in aₙ
Hint

The coefficient depends on n.

Answer and reasoning

Variable. n+1 changes with the index.

5. Why is aₙ₊₁=aₙaₙ₋₁ nonlinear?

Stretch

  1. Every order-two recurrence is nonlinear
  2. Unknown terms are multiplied
  3. The indices differ
  4. It has no constant
Hint

Linearity forbids products of sequence terms.

Answer and reasoning

Unknown terms are multiplied. The product aₙaₙ₋₁ is nonlinear in the unknown sequence.

6. What should be checked before using a characteristic polynomial?

Stretch

  1. Whether a graph is straight
  2. Linearity, homogeneity and constant coefficients for the standard method
  3. Only whether terms are positive
  4. Only whether n is even
Hint

Match the method to its assumptions.

Answer and reasoning

Linearity, homogeneity and constant coefficients for the standard method. The standard homogeneous characteristic-root formula needs these recurrence properties.

7. A homogeneous linear recurrence has which independent forcing term?

Foundation

  1. Always 2n2^{n}
  2. Zero
  3. Always one
  4. Always n
Hint

Move sequence terms to one side.

Answer and reasoning

Zero. No nonzero term independent of the sequence remains.

8. Classify aₙ₊₃=aₙ₊₁+2aₙ.

Core

  1. Order three, linear homogeneous
  2. Order one, nonlinear
  3. Order two, non-homogeneous
  4. Order zero
Hint

The gap from n to n+3 determines the order.

Answer and reasoning

Order three, linear homogeneous. The sequence terms are linear with constant coefficients and no forcing.

9. Is aₙ₊₁=n²aₙ linear in the sequence terms?

Stretch

  1. Only when n=1
  2. Only if aₙ=0
  3. Yes
  4. No, because n is squared
Hint

The coefficient is not an unknown sequence term.

Answer and reasoning

Yes. The recurrence is linear with variable coefficient n².

Choose your next step

Continue to First-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.