Recurrences path · R05

Before this lesson: Classifying recurrence relations, Solving polynomial equations, Mathematical induction: the first principle

Your goal: Solve a second-order recurrence and justify the resulting expression.

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.

Second-order linear recurrences: the key idea

For aₙ₊₂=paₙ₊₁+qaₙ, test an=rna_{n}=r^{n} to obtain the characteristic equation r²−pr−q=0. Distinct roots r,s give an=Arn+Bsna_{n}=Ar^{n}+Bs^{n}; a repeated root r gives an=(A+Bn)rna_{n}=(A+Bn)r^{n} in the usual nonzero-root case. Determine A,B from two initial values, then verify. These formulas work over complex numbers too, with conjugate combinations producing real sequences. The all-zero characteristic-root degeneration should be read directly from the recurrence rather than using ambiguous 0⁰ formulas.

A worked example

Solve a₀=2,a₁=5,aₙ₊₂=3aₙ₊₁−2aₙ.

The roots of r²−3r+2=0 are 1 and 2. Write an=A+B2na_{n}=A+B2^{n}. The initial equations A+B=2,A+2B=5 give B=3,A=−1. Thus an=3⋅2n−1a_{n}=3\cdot 2^{n}-1.

Your turn: change one thing

Solve b₀=1,b₁=4,bₙ₊₂=4bₙ₊₁−4bₙ.

Try this on paper before opening the explanation.

Compare your reasoning

The repeated root is 2, so bn=(A+Bn)2nb_{n}=(A+Bn)2^{n}. The initial data give A=1 and 2(1+B)=4, hence B=1. Thus bn=(n+1)2nb_{n}=(n+1)2^{n}.

Pause and check

A trap to avoid: Missing the n multiplier for a repeated root.

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 verifying a formula and two initial terms proves it is the required order-two 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

The recurrence determines each next term from its two predecessors. The candidate and the required sequence agree at indices 0 and 1. If they agree at two successive indices, the recurrence forces agreement at the next. Induction gives agreement at every 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. The characteristic equation of aₙ₊₂=3aₙ₊₁−2aₙ is what?

Foundation

  1. r²+3r−2=0
  2. r−3=0
  3. r²−2r+3=0
  4. r²−3r+2=0
Hint

Substitute rnr^{n} and cancel the common power formally.

Answer and reasoning

r²−3r+2=0. r²=3r−2 gives the displayed polynomial.

2. How many initial values does a standard order-two recurrence need?

Foundation

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

Two predecessors determine the next term.

Answer and reasoning

2. Two starting values determine the forward sequence.

3. Roots of r²−3r+2 are what?

Core

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

Factor the quadratic.

Answer and reasoning

1 and 2. r²−3r+2=(r−1)(r−2).

4. If an=3⋅2n−1a_{n}=3\cdot 2^{n}-1, what is a₃?

Core

  1. 11
  2. 23
  3. 24
  4. 17
Hint

Substitute n=3.

Answer and reasoning

23. 3·8−1=23.

5. For a repeated nonzero root r, the general form is what?

Stretch

  1. Arn+BrnAr^{n}+Br^{n} only
  2. A+B always
  3. rn2r^{n2}
  4. (A+Bn)rn(A+Bn)r^{n}
Hint

A second independent solution is needed.

Answer and reasoning

(A+Bn)rn(A+Bn)r^{n}. The factor n supplies a second linearly independent solution.

6. Finding characteristic roots without initial values gives what?

Stretch

  1. Only the zero sequence
  2. No useful information
  3. A family of candidate sequences
  4. One fully determined sequence
Hint

The constants remain to be fixed.

Answer and reasoning

A family of candidate sequences. Initial values determine the coefficients of the root solutions.

7. A trial rnr^{n} turns a constant-coefficient recurrence into what?

Foundation

  1. A polynomial equation for r
  2. An inequality for n
  3. A factorial formula
  4. A random initial value
Hint

All terms share a geometric factor.

Answer and reasoning

A polynomial equation for r. The remaining relation between powers of r is the characteristic equation.

8. For aₙ₊₂=5aₙ₊₁−6aₙ, the characteristic roots are what?

Core

  1. −2 and −3
  2. 0 and 5
  3. 2 and 3
  4. 1 and 6
Hint

Factor r²−5r+6.

Answer and reasoning

2 and 3. (r−2)(r−3)=0.

9. Why does a repeated root need a term such as nrnnr^{n}?

Stretch

  1. Two copies of rnr^{n} are not independent
  2. Because n must be a root
  3. Because all roots are zero
  4. Because the sequence is nonlinear
Hint

Arn+BrnAr^{n}+Br^{n} collapses to one constant times rnr^{n}.

Answer and reasoning

Two copies of rnr^{n} are not independent. The additional factor n provides the missing independent solution.

Choose your next step

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