Proving That a Linear Combination of Solutions Is Also a Solution

Last Updated on June 20, 2026 by Rajeev Bagra

Introduction

When solving recurrence relations, one of the most powerful ideas is the Principle of Superposition.

This principle tells us that if we already know two solutions of a linear recurrence relation, then we can combine them to create new solutions.

This fact is the foundation for obtaining the general solution of many recurrence relations, including those that arise in probability problems such as the Gambler’s Ruin problem.

---

The Original Recurrence Relation

Suppose we want to solve

where p and q are constants.

This is a linear second-order recurrence relation because:

• The unknown sequence appears only to the first power.
• Terms are added together.
• The recurrence involves both Pᵢ₊₁ and Pᵢ₋₁.

---

Assume We Already Know Two Solutions

Suppose we have discovered two sequences:

Aᵢ

and

Bᵢ

that satisfy the recurrence.

For Aᵢ:

For Bᵢ:

Since these sequences satisfy the recurrence relation, they are called solutions.

---

Multiply Each Solution by a Constant

Choose any constants C₁ and C₂.

Multiplying the first equation by C₁ gives

Multiplying the second equation by C₂ gives

Notice that multiplying by a constant does not destroy the equality.

---

Add the Two Equations

Now add the left-hand sides and right-hand sides:

This equation is extremely important because it has the same structure as the original recurrence relation.

---

Define a New Sequence

Let

This means Pᵢ is formed by combining the two known solutions.

Now shift the index by one:

and

---

Substitute into the Previous Equation

Earlier we obtained

Using our definitions:

• Replace C₁Aᵢ + C₂Bᵢ with Pᵢ.
• Replace C₁Aᵢ₊₁ + C₂Bᵢ₊₁ with Pᵢ₊₁.
• Replace C₁Aᵢ₋₁ + C₂Bᵢ₋₁ with Pᵢ₋₁.

The equation becomes

---

What Did We Just Prove?

The equation we obtained is exactly the same as the original recurrence relation.

Therefore Pᵢ satisfies the recurrence.

Since Pᵢ satisfies the recurrence, Pᵢ is also a solution.

This proves that

is a solution whenever Aᵢ and Bᵢ are solutions.

---

Why Is This Called Superposition?

The word “superposition” means combining things together.

In a linear recurrence relation:

• A solution can be multiplied by a constant.
• Two solutions can be added together.
• The result is still a solution.

Therefore any linear combination

remains a valid solution.

This property is called the Principle of Superposition.

---

A Concrete Example

Suppose the recurrence relation has two known solutions:

and

Choose constants A and B.

By superposition, another solution is

This is called the general solution because every solution can be written in this form.

---

Key Takeaway

To prove that a linear combination of solutions is itself a solution:

1. Start with two known solutions.
2. Multiply them by arbitrary constants.
3. Add the resulting equations.
4. Define a new sequence using the linear combination.
5. Substitute the new sequence into the recurrence.
6. Observe that the original recurrence relation is recovered.

This simple idea is one of the most important concepts in recurrence relations, differential equations, linear algebra, probability theory, and mathematical physics.