Recurrences path · R06

Before this lesson: Second-order linear recurrences, Polynomial roots and multiplicity

Your goal: Explain how the order and root multiplicities control the general form.

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.

Higher-order linear recurrences: the key idea

For an order-k linear homogeneous recurrence with constant coefficients, the characteristic polynomial has degree k. A nonzero root r of multiplicity m contributes rnr^{n},nrnnr^{n},…,nm−1rnn^{m-1}r^{n} to the solution space. Add contributions from all roots and use k initial values to determine the constants. In the standard forward recurrence, the coefficient of the newest term is nonzero, so the next term is uniquely determined. Degenerate zero-root cases need care with the starting indices and may be handled directly.

A worked example

Solve aₙ₊₃=6aₙ₊₂−11aₙ₊₁+6aₙ with a₀=3,a₁=6,a₂=14.

The characteristic polynomial is (r−1)(r−2)(r−3). The candidate an=1+2n+3na_{n}=1+2^{n}+3^{n} has the three initial values 3,6,14. Each exponential satisfies the recurrence, so their sum does too. Uniqueness proves the formula.

Your turn: change one thing

What contributions come from a characteristic factor (r−2)³?

Try this on paper before opening the explanation.

Compare your reasoning

The three independent contributions are 2n2^{n},n2nn2^{n},n22nn^{2}2^{n}, so the combined part is (A+Bn+Cn2)2n(A+Bn+Cn^{2})2^{n}.

Pause and check

A trap to avoid: Using too few initial conditions; complex cases require F09.

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 uniqueness for a forward order-k recurrence with k specified initial values.

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 on the first k indices. The recurrence then gives the same next value because its k required predecessors agree. Repeating this argument, or applying induction to agreement through index n, proves equality at every later index.

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. An order-three recurrence normally needs how many initial values?

Foundation

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

Count the required predecessors.

Answer and reasoning

3. Three initial terms start the forward recurrence.

2. A root of multiplicity 3 contributes how many independent terms?

Foundation

  1. 6
  2. 3
  3. 1
  4. 2
Hint

Use powers of n from 0 to 2.

Answer and reasoning

3. The contributions are rnr^{n},nrnnr^{n},n2rnn^{2}r^{n}.

3. For an=1+2n+3na_{n}=1+2^{n}+3^{n}, what is a₃?

Core

  1. 14
  2. 36
  3. 35
  4. 27
Hint

Substitute n=3.

Answer and reasoning

36. 1+8+27=36.

4. Which polynomial has roots 1,2,3?

Core

  1. r²−3r+2
  2. r³−6r²+11r−6
  3. r³+6r²+11r+6
  4. r³−3r+2
Hint

Expand (r−1)(r−2)(r−3).

Answer and reasoning

r³−6r²+11r−6. The elementary symmetric sums are 6,11 and 6.

5. If 2 is a triple characteristic root, which form is appropriate?

Stretch

  1. (A+Bn+Cn2)2n(A+Bn+Cn^{2})2^{n}
  2. A2nA2^{n} only
  3. A+Bn+Cn² only
  4. 2n32^{n3}
Hint

Combine polynomial factors with the exponential.

Answer and reasoning

(A+Bn+Cn2)2n(A+Bn+Cn^{2})2^{n}. Multiplicity three produces a polynomial of degree at most two times 2n2^{n}.

6. Why do sums of homogeneous solutions remain solutions?

Stretch

  1. The recurrence operator is linear
  2. All roots are positive
  3. Every sequence is constant
  4. Initial values vanish always
Hint

Distribute each linear term over the sum.

Answer and reasoning

The recurrence operator is linear. Linearity makes the recurrence of a sum the sum of the recurrences.

7. A standard order-k characteristic polynomial has degree what?

Foundation

  1. 2k
  2. Always two
  3. k
  4. k−1
Hint

The newest term is k indices ahead.

Answer and reasoning

k. Substituting rnr^{n} leaves a highest power rkr^{k}.

8. A double root 3 contributes which expression?

Core

  1. A+3Bn
  2. (A+Bn)3n(A+Bn)3^{n}
  3. A3n+B3nA3^{n}+B3^{n} only
  4. (A+B)n(A+B)^{n}
Hint

Use a polynomial factor of degree one.

Answer and reasoning

(A+Bn)3n(A+Bn)3^{n}. The independent terms are 3n3^{n} and n3nn3^{n}.

9. How can one verify a higher-order formula without solving for roots again?

Stretch

  1. Check one late term only
  2. Count its symbols
  3. Assume uniqueness without checking data
  4. Check all required initial terms and substitute in the recurrence
Hint

Uniqueness then identifies the sequence.

Answer and reasoning

Check all required initial terms and substitute in the recurrence. A candidate satisfying the recurrence and all initial values is the required sequence.

Choose your next step

Continue to Non-homogeneous 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.