Recurrences path · R07

Before this lesson: Second-order linear recurrences, First-order linear recurrences

Your goal: Choose a valid particular form and adjust it when it overlaps the homogeneous part.

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.

Names you may know: inhomogeneous recurrence relations; particular solutions.

Non-homogeneous recurrences: the key idea

A linear non-homogeneous recurrence is solved by adding one particular solution to the general homogeneous solution. Guess a form suited to the forcing term: a polynomial for polynomial forcing, or CrnCr^{n} for exponential forcing. If this form is already homogeneous, multiply by enough powers of n to obtain a new trial; this is resonance. Determine the trial coefficients by substitution, then fit the initial values to the complete solution. A guess is a discovery device, while substitution is the verification.

A worked example

Solve a₀=0 and aₙ₊₁−2aₙ=1.

The homogeneous solution is C2nC2^{n}. A constant particular solution K satisfies K−2K=1, so K=−1. Hence an=C2n−1a_{n}=C2^{n}-1. The initial value gives C=1, so an=2n−1a_{n}=2^{n}-1.

Your turn: change one thing

Solve b₀=0 and bn+1−2bn=2nb_{n+1}-2b_{n}=2^{n}.

Try this on paper before opening the explanation.

Compare your reasoning

A trial C2nC2^{n} is homogeneous and cannot produce the forcing. Try Kn2nKn2^{n}: substitution gives K2n+1=2nK2^{n+1}=2^{n}, so K=1/2. The initial value removes the homogeneous constant. Thus bn=n2n−1b_{n}=n2^{n-1}, including b₀=0.

Pause and check

A trap to avoid: Forgetting the homogeneous contribution or the resonance adjustment.

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 the difference of two particular solutions satisfies the homogeneous recurrence.

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

Let L be the linear recurrence operator and suppose L(u)=f and L(v)=f. Linearity gives L(u−v)=L(u)−L(v)=0. Thus all solutions differ from a fixed particular solution by a homogeneous solution.

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 complete solution is assembled as what?

Foundation

  1. Only the forcing term
  2. Only initial values
  3. Particular plus homogeneous
  4. Particular times homogeneous
Hint

Use linearity of the recurrence operator.

Answer and reasoning

Particular plus homogeneous. Adding a homogeneous solution does not change the forcing.

2. A trial that already solves the homogeneous equation is a sign of what?

Foundation

  1. Nonlinearity
  2. A missing domain
  3. Resonance
  4. A unique answer
Hint

It produces zero instead of the forcing.

Answer and reasoning

Resonance. The trial needs an extra factor of n, or a higher power for repeated roots.

3. For aₙ₊₁−2aₙ=1, a constant particular solution is what?

Core

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

Substitute K.

Answer and reasoning

−1. K−2K=−K=1, so K=−1.

4. With a₀=0, aₙ₊₁=2aₙ+1, a₃ is what?

Core

  1. 3
  2. 7
  3. 6
  4. 8
Hint

The formula is 2n−12^{n}-1.

Answer and reasoning

7. At n=3 this is 8−1=7.

5. For forcing 2n2^{n} when 2 is a simple characteristic root, a suitable trial is what?

Stretch

  1. K2nK2^{n}
  2. K only
  3. Kn² only
  4. Kn2nKn2^{n}
Hint

Add one factor of n for resonance.

Answer and reasoning

Kn2nKn2^{n}. The exponential alone is homogeneous; n times it can produce the forcing.

6. Why is the difference of two particular solutions homogeneous?

Stretch

  1. Their initial values always match
  2. They are geometric
  3. Their equal forcing terms cancel
  4. Both must be zero
Hint

Apply linearity.

Answer and reasoning

Their equal forcing terms cancel. L(u−v)=L(u)−L(v)=f−f=0.

7. A particular solution needs to satisfy what?

Foundation

  1. Only the zero-forcing equation
  2. Every possible initial value
  3. Only the first term
  4. The non-homogeneous recurrence
Hint

It must produce the specified forcing.

Answer and reasoning

The non-homogeneous recurrence. The homogeneous part is later added to fit initial values.

8. Solve a₀=1, aₙ₊₁−aₙ=2.

Core

  1. aₙ=n²+1
  2. aₙ=2n
  3. aₙ=1+2n
  4. an=2na_{n}=2^{n}
Hint

Sum the constant differences.

Answer and reasoning

aₙ=1+2n. The arithmetic sequence starts at 1 and adds 2 each step.

9. Why can a homogeneous solution be added to a particular one?

Stretch

  1. It changes the forcing arbitrarily
  2. It removes the initial data
  3. Its contribution to the forcing is zero
  4. It is always a constant
Hint

Use linearity of the recurrence operator.

Answer and reasoning

Its contribution to the forcing is zero. L(p+h)=L(p)+L(h)=f+0=f.

Choose your next step

Try a written problem in the challenge room. 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.