Recurrence Relations Made Easy for Discrete Mathematics Exam

Hello there, my dear students! Today we are going to learn a very important topic for your Discrete Mathematics exam — Recurrence Relations. I know many of you feel nervous when you see this topic, but I promise you, by the end of this lesson, you will feel confident. So, let us start together, step by step.

1. What is a Recurrence Relation?

Think about how you climb stairs. To reach step n, you first need to be on step n-1, right? A recurrence relation works the same way. It is an equation that tells you how to find a term in a sequence by using the previous terms.

Definition: A recurrence relation for a sequence \(\{a_n\}\) is an equation that expresses \(a_n\) in terms of one or more of the previous terms \(a_0, a_1, \ldots, a_{n-1}\), for all \(n \geq n_0\), where \(n_0\) is a non-negative integer.

Now, let me ask you a question. If I tell you that each term is double the previous term, and the first term is 3, can you write the next few terms? Yes! The sequence is: 3, 6, 12, 24, 48, …

Here, the recurrence relation is: \(a_n = 2a_{n-1}\) for \(n \geq 1\)

And the initial condition is: \(a_0 = 3\)

But wait — what if I ask you to find \(a_{100}\)? You do not want to multiply 100 times! That is why we also find a solution (also called a closed formula). For this example, the solution is \(a_n = 3(2^n)\). Now you can find any term directly!

Key Exam Note: A recurrence relation alone has many solutions. But a recurrence relation plus initial conditions gives you a unique solution. Always remember this difference!

Worked Example 1: Finding Terms Step by Step

Problem: Find \(a_6\) in the sequence defined by \(a_n = 2a_{n-1} – a_{n-2}\) with \(a_0 = 3\) and \(a_1 = 4\).

Solution: We need to find each term one by one:

\[ \begin{aligned} a_2 &= 2a_1 – a_0 = 2(4) – 3 = 5 \\ a_3 &= 2a_2 – a_1 = 2(5) – 4 = 6 \\ a_4 &= 2a_3 – a_2 = 2(6) – 5 = 7 \\ a_5 &= 2a_4 – a_3 = 2(7) – 6 = 8 \\ a_6 &= 2a_5 – a_4 = 2(8) – 7 = 9 \end{aligned} \]

So \(a_6 = 9\). Notice the pattern? Each term increases by 1. The closed formula is \(a_n = n + 3\). Can you verify this? Check: \(a_0 = 0 + 3 = 3\) ✓ and \(a_6 = 6 + 3 = 9\) ✓

Worked Example 2: Writing a Recurrence Relation from a Sequence

Problem: Find a recurrence relation for the sequence: 1, 5, 17, 53, 161, 485, …

Solution: Let me guide you. Look at how the numbers grow:

1 x 3 = 3 (but next term is 5, so 3 + 2 = 5) 5 x 3 = 15 (but next term is 17, so 15 + 2 = 17) 17 x 3 = 51 (but next term is 53, so 51 + 2 = 53)

Do you see the pattern? Each term is 3 times the previous term, plus 2. So the recurrence relation is:

\[ a_n = 3a_{n-1} + 2, \quad a_0 = 1 \]

Worked Example 3: Real-World Problem — Compound Interest

Problem: A person invests 10,000 birr at 12% interest compounded annually. Set up a recurrence relation.

Solution: Let \(A_n\) = amount at the end of year \(n\). The amount after \(n\) years equals the amount after \(n-1\) years plus the interest for year \(n\):

\[ A_n = A_{n-1} + 0.12 \, A_{n-1} = 1.12 \, A_{n-1}, \quad A_0 = 10000 \]

The closed formula is \(A_n = 10000(1.12)^n\). So after 15 years: \(A_{15} = 10000(1.12)^{15}\).

Practice Question 1: A sequence is defined by \(a_n = a_{n-1} + 5\) with \(a_0 = 2\). What is the closed formula?
Answer: Since each term increases by 5, this is an arithmetic sequence. The closed formula is \(a_n = 2 + 5n\). You can verify: \(a_0 = 2\), \(a_1 = 7\), \(a_2 = 12\), etc. Each term matches \(2 + 5n\).
Practice Question 2: Is \(a_n = 5\) (a constant sequence) a solution of \(a_n = 2a_{n-1} – a_{n-2}\)?
Answer: Yes! Substitute: \(5 = 2(5) – 5 = 10 – 5 = 5\). It is true. This shows that constant sequences can be solutions of second-order recurrence relations.

2. Linear Recurrence Relations with Constant Coefficients

Now, let me introduce you to a special and very important type of recurrence relation. Not all recurrence relations are easy to solve, but linear recurrence relations with constant coefficients have a clear step-by-step method. This is what examiners love to test!

Definition: A recurrence relation of degree \(k\) is a linear recurrence relation with constant coefficients if it has the form:

\[ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n) \]

where \(c_1, c_2, \ldots, c_k\) are constants (not depending on \(n\)), and \(f(n)\) is a function of \(n\).

Let me break this down for you with simple words:

  • Linear = no powers like \(a_{n-1}^2\), no products like \(a_{n-1} \cdot a_{n-2}\)
  • Constant coefficients = the numbers in front of each term are fixed, like 2, -3, 5 (not \(n\) or \(n^2\))
  • Degree \(k\) = the gap between \(a_n\) and the farthest previous term it uses
TypeExampleLinear?Constant Coeff.?
\(a_n = 3a_{n-1} + 2\)YesYes✓ Both
\(a_n = a_{n-1}^2 + 1\)No (has \(a_{n-1}^2\))No✗ Not linear
\(a_n = n \cdot a_{n-1}\)YesNo (coefficient is \(n\))✗ Coeff. varies
\(a_n = 2a_{n-1} – 3a_{n-2} + n^2\)YesYes✓ Both

Two Important Categories

Every linear recurrence relation with constant coefficients falls into one of two categories:

  1. Homogeneous: When \(f(n) = 0\). Example: \(a_n = 2a_{n-1} – a_{n-2}\)
  2. Non-homogeneous: When \(f(n) \neq 0\). Example: \(a_n = 2a_{n-1} + 3\) (here \(f(n) = 3\))
Exam Tip: Always check if \(f(n) = 0\) first. This tells you which method to use!
Practice Question 3 (MCQ): Which of the following is a linear recurrence relation with constant coefficients?
A) \(a_n = a_{n-1} \cdot a_{n-2}\)
B) \(a_n = n \cdot a_{n-1} + 1\)
C) \(a_n = 3a_{n-1} – 2a_{n-2}\)
D) \(a_n = a_{n-1}^2 + a_{n-2}\)
Answer: C. Option A has a product of terms (not linear). Option B has coefficient \(n\) (not constant). Option D has \(a_{n-1}^2\) (not linear). Only Option C is linear with constant coefficients (3 and -2) and is also homogeneous since \(f(n) = 0\).
Practice Question 4 (True/False): \(a_n = 2a_{n-1} + n\) is a homogeneous linear recurrence relation with constant coefficients.
Answer: False. It IS linear with constant coefficients, but it is non-homogeneous because \(f(n) = n \neq 0\). This is a common trick in exams — do not forget to check the \(f(n)\) part!

3. Solving Homogeneous Linear Recurrence Relations

Now we reach the most important part for your exam. I will teach you the method slowly and clearly. Pay close attention because this method works for all homogeneous linear recurrence relations with constant coefficients.

General Form: \(a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}\)

Step 1: Write the characteristic equation:
\[ r^k – c_1 r^{k-1} – c_2 r^{k-2} – \cdots – c_k = 0 \]
Step 2: Find the roots of this equation.
Step 3: Write the general solution based on the type of roots (see rules below).
Step 4: Use the initial conditions to find the specific constants.

Rule for Writing the General Solution

Root TypeWhat You Get in Solution
Single real root \(r\)A term: \(A \cdot r^n\)
Two distinct real roots \(r_1, r_2\)\(a_n = A \cdot r_1^n + B \cdot r_2^n\)
One repeated root \(r\) (multiplicity 2)\(a_n = (A + Bn) \cdot r^n\)
Root \(r\) repeated \(m\) times\(a_n = (A_1 + A_2 n + A_3 n^2 + \cdots + A_m n^{m-1}) \cdot r^n\)
Exam Tip: The characteristic equation is formed by replacing \(a_n\) with \(r^n\), \(a_{n-1}\) with \(r^{n-1}\), etc., then dividing by \(r^{n-k}\) (the smallest power). Or simply: move all terms to one side and replace \(a_{n-i}\) with \(r^{n-i}\), then set equal to zero.

Worked Example 4: Two Distinct Real Roots

Problem: Solve \(a_n = 5a_{n-1} – 6a_{n-2}\) with \(a_0 = 1\) and \(a_1 = 2\).

Step 1: Write the characteristic equation:

\[ r^2 – 5r + 6 = 0 \]

Step 2: Factor and find roots:

\[ (r – 2)(r – 3) = 0 \implies r_1 = 2, \; r_2 = 3 \]

Step 3: Since we have two distinct real roots, the general solution is:

\[ a_n = A \cdot 2^n + B \cdot 3^n \]

Step 4: Use initial conditions to find \(A\) and \(B\):

\[ \begin{aligned} a_0 = 1:& \quad A \cdot 2^0 + B \cdot 3^0 = A + B = 1 \quad \text{— (i)} \\ a_1 = 2:& \quad A \cdot 2^1 + B \cdot 3^1 = 2A + 3B = 2 \quad \text{— (ii)} \end{aligned} \]
See also  Elementary Probability Theory Made Easy for Discrete Mathematics Exam

From (i): \(A = 1 – B\). Substitute into (ii):

\[ 2(1 – B) + 3B = 2 \implies 2 – 2B + 3B = 2 \implies B = 0 \]

Then \(A = 1\). So the particular solution is:

\[ \boxed{a_n = 2^n} \]

Let me verify: \(a_0 = 2^0 = 1\) ✓, \(a_1 = 2^1 = 2\) ✓, \(a_2 = 5(2) – 6(1) = 4 = 2^2\) ✓. Perfect!

Worked Example 5: Repeated Root

Problem: Solve \(a_n = 4a_{n-1} – 4a_{n-2}\) with \(a_0 = 1\) and \(a_1 = 4\).

Step 1: Characteristic equation:

\[ r^2 – 4r + 4 = 0 \implies (r – 2)^2 = 0 \implies r = 2 \text{ (repeated twice)} \]

Step 2: Since the root \(r = 2\) has multiplicity 2, the general solution is:

\[ a_n = (A + Bn) \cdot 2^n \]

Step 3: Use initial conditions:

\[ \begin{aligned} a_0 = 1:& \quad (A + B \cdot 0) \cdot 2^0 = A = 1 \\ a_1 = 4:& \quad (A + B \cdot 1) \cdot 2^1 = 2(A + B) = 4 \implies A + B = 2 \implies B = 1 \end{aligned} \]

So the solution is:

\[ \boxed{a_n = (1 + n) \cdot 2^n} \]

Verify: \(a_0 = 1 \cdot 1 = 1\) ✓, \(a_1 = 2 \cdot 2 = 4\) ✓, \(a_2 = 4(4) – 4(1) = 12\) and formula gives \((1+2) \cdot 4 = 12\) ✓.

Worked Example 6: Higher Degree (Third Order)

Problem: Solve \(a_n = 6a_{n-1} – 11a_{n-2} + 6a_{n-3}\) with \(a_0 = 1\), \(a_1 = 2\), \(a_2 = 0\).

Step 1: Characteristic equation:

\[ r^3 – 6r^2 + 11r – 6 = 0 \]

Step 2: Find roots. Try \(r = 1\): \(1 – 6 + 11 – 6 = 0\) ✓. So \((r-1)\) is a factor:

\[ r^3 – 6r^2 + 11r – 6 = (r-1)(r^2 – 5r + 6) = (r-1)(r-2)(r-3) = 0 \]

Three distinct roots: \(r_1 = 1, r_2 = 2, r_3 = 3\).

Step 3: General solution:

\[ a_n = A \cdot 1^n + B \cdot 2^n + C \cdot 3^n = A + B \cdot 2^n + C \cdot 3^n \]

Step 4: Use initial conditions:

\[ \begin{aligned} a_0 = 1:& \quad A + B + C = 1 \quad \text{— (i)} \\ a_1 = 2:& \quad A + 2B + 3C = 2 \quad \text{— (ii)} \\ a_2 = 0:& \quad A + 4B + 9C = 0 \quad \text{— (iii)} \end{aligned} \]

(ii) – (i): \(B + 2C = 1\) — (iv)

(iii) – (i): \(3B + 8C = -1\) — (v)

From (iv): \(B = 1 – 2C\). Substitute into (v): \(3(1-2C) + 8C = -1 \implies 3 – 6C + 8C = -1 \implies 2C = -4 \implies C = -2\)

Then \(B = 1 – 2(-2) = 5\) and \(A = 1 – 5 – (-2) = -2\).

\[ \boxed{a_n = -2 + 5 \cdot 2^n – 2 \cdot 3^n} \]
Formula to Remember for Exam: For the characteristic equation, simply take the recurrence \(a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}\), move everything to the left side: \(a_n – c_1 a_{n-1} – c_2 a_{n-2} – \cdots – c_k a_{n-k} = 0\), then replace \(a_{n-i}\) with \(r^{n-i}\) and divide by \(r^{n-k}\).
Practice Question 5 (MCQ): The characteristic equation of \(a_n = 3a_{n-1} + 4a_{n-2}\) is:
A) \(r^2 + 3r + 4 = 0\)
B) \(r^2 – 3r – 4 = 0\)
C) \(r^2 – 3r + 4 = 0\)
D) \(r^2 + 3r – 4 = 0\)
Answer: B. Move all terms to left: \(a_n – 3a_{n-1} – 4a_{n-2} = 0\). Replace: \(r^n – 3r^{n-1} – 4r^{n-2} = 0\). Divide by \(r^{n-2}\): \(r^2 – 3r – 4 = 0\). Many students make sign errors here — be careful!
Practice Question 6 (Fill in the Blank): If the characteristic equation \((r – 5)^2 = 0\) comes from a second-order homogeneous recurrence relation, then the general solution is \(a_n =\) ______.
Answer: \(a_n = (A + Bn) \cdot 5^n\). The root \(r = 5\) is repeated twice (multiplicity 2), so we multiply by \((A + Bn)\). This is a very common exam pattern!
Practice Question 7 (Short Answer): Solve \(a_n = a_{n-1} – 6a_{n-2}\) with \(a_0 = 2\) and \(a_1 = 1\).
Answer:
Characteristic equation: \(r^2 – r + 6 = 0\)
Discriminant: \(\Delta = 1 – 24 = -23 < 0\)
This gives complex roots: \(r = \frac{1 \pm \sqrt{23}\,i}{2}\)
While complex roots can be solved using trigonometric forms, in most introductory discrete math courses, if the characteristic equation has no real roots, you simply state that the solution involves complex numbers. The general form would use \(|\alpha|\) and trigonometric functions, but for exam purposes, recognizing that no real roots means the sequence oscillates is the key insight.

4. Solving Non-Homogeneous Linear Recurrence Relations

Now, my friends, we move to the second type. This is where \(f(n) \neq 0\). Do not worry — the method builds on what you already learned!

Key Idea: The general solution of a non-homogeneous relation = General solution of homogeneous part + Particular solution of the non-homogeneous part.

\[ a_n = \underbrace{a_n^{(h)}}_{\text{homogeneous solution}} + \underbrace{a_n^{(p)}}_{\text{particular solution}} \]
TOTAL SOLUTION ======================== | | | Homogeneous part | + | Particular part | | (solve like before) | | (guess based on | | | | the form of f(n))| ========================

How to Find the Particular Solution \(a_n^{(p)}\)

You make an educated guess based on the form of \(f(n)\):

If \(f(n)\) is…Guess \(a_n^{(p)}\) as…If this guess conflicts with homogeneous, multiply by \(n\)
Constant \(d\)\(P\) (a constant)If 1 is a root, use \(Pn\); if repeated root, use \(Pn^2\)
Linear \(pn + q\)\(Pn + Q\)If 1 is a root, use \(n(Pn + Q)\)
Power \(d^n\)\(P \cdot d^n\)If \(d\) is a root of multiplicity \(m\), use \(Pn^m \cdot d^n\)
\(d^n \cdot (pn+q)\)\(d^n(Pn+Q)\)If \(d\) is a root, multiply by \(n^m\)
Exam Tip — The Conflict Rule: If your guess for \(a_n^{(p)}\) already appears in the homogeneous solution, multiply your guess by \(n\). If it still conflicts, multiply by \(n^2\), and so on. This is the most common mistake students make!

Worked Example 7: \(f(n)\) = Constant (No Conflict)

Problem: Solve \(a_n = 3a_{n-1} + 2\) with \(a_0 = 1\).

Step 1: Find the homogeneous solution. The homogeneous part is \(a_n^{(h)} = 3a_{n-1}^{(h)}\).

Characteristic equation: \(r – 3 = 0 \implies r = 3\)

So \(a_n^{(h)} = A \cdot 3^n\)

Step 2: Find a particular solution. Since \(f(n) = 2\) (a constant), guess \(a_n^{(p)} = P\).

Substitute into the original recurrence:

\[ P = 3P + 2 \implies -2P = 2 \implies P = -1 \]

So \(a_n^{(p)} = -1\). (No conflict since \(-1\) is not in the homogeneous solution form.)

Step 3: General solution: \(a_n = A \cdot 3^n – 1\)

Step 4: Use initial condition: \(a_0 = A \cdot 1 – 1 = 1 \implies A = 2\)

\[ \boxed{a_n = 2 \cdot 3^n – 1} \]

Verify: \(a_0 = 2 – 1 = 1\) ✓, \(a_1 = 2(3) – 1 = 5\) and from recurrence: \(3(1) + 2 = 5\) ✓.

Worked Example 8: \(f(n)\) = Constant WITH Conflict

Problem: Solve \(a_n = 3a_{n-1} – 2\) with \(a_0 = 1\).

Step 1: Homogeneous: \(a_n^{(h)} = 3a_{n-1}^{(h)} \implies r = 3 \implies a_n^{(h)} = A \cdot 3^n\)

Step 2: Guess \(a_n^{(p)} = P\) (constant). Substitute: \(P = 3P – 2 \implies -2P = -2 \implies P = 1\).

This works! No conflict here because the root is 3, not 1. The conflict only happens when the constant 1 is a root of the characteristic equation.

Step 3: \(a_n = A \cdot 3^n + 1\). Using \(a_0 = 1\): \(A + 1 = 1 \implies A = 0\).

\[ \boxed{a_n = 1} \]

Interesting! The solution is just the constant 1. Verify: \(a_n = 1 = 3(1) – 2 = 1\) ✓. This makes sense — the sequence is constant.

Worked Example 9: Real Conflict Case

Problem: Solve \(a_n = a_{n-1} + a_{n-2} + 2\) with \(a_0 = 0\) and \(a_1 = 0\).

Step 1: Homogeneous: \(r^2 – r – 1 = 0\). Roots: \(r = \frac{1 \pm \sqrt{5}}{2}\). (These are the golden ratio numbers.)

\(a_n^{(h)} = A \left(\frac{1+\sqrt{5}}{2}\right)^n + B \left(\frac{1-\sqrt{5}}{2}\right)^n\)

Step 2: Guess \(a_n^{(p)} = P\). Substitute: \(P = P + P + 2 \implies P = 2P + 2 \implies P = -2\).

Wait — this gives \(P = -2\). Let me check: is there a conflict? The roots are \(\frac{1\pm\sqrt{5}}{2}\), not 1. So no conflict! The particular solution \(a_n^{(p)} = -2\) is valid.

Step 3: \(a_n = A \left(\frac{1+\sqrt{5}}{2}\right)^n + B \left(\frac{1-\sqrt{5}}{2}\right)^n – 2\)

Step 4: \(a_0 = 0\): \(A + B – 2 = 0 \implies A + B = 2\)

\(a_1 = 0\): \(A\left(\frac{1+\sqrt{5}}{2}\right) + B\left(\frac{1-\sqrt{5}}{2}\right) – 2 = 0\)

This gives a system we can solve, but the key point is the method.

Worked Example 10: \(f(n) = d^n\) Type

Problem: Solve \(a_n = 5a_{n-1} – 6a_{n-2} + 2^n\) with \(a_0 = 1\) and \(a_1 = 0\).

Step 1: Homogeneous part: \(r^2 – 5r + 6 = 0 \implies (r-2)(r-3) = 0 \implies r_1 = 2, r_2 = 3\)

\(a_n^{(h)} = A \cdot 2^n + B \cdot 3^n\)

Step 2: Particular solution. Here \(f(n) = 2^n\), so normally we guess \(a_n^{(p)} = P \cdot 2^n\). BUT — \(r = 2\) is already a root of the characteristic equation! This is a conflict. So we multiply by \(n\):

Guess: \(a_n^{(p)} = Pn \cdot 2^n\)

Substitute into the original recurrence:

\[ \begin{aligned} Pn \cdot 2^n &= 5P(n-1) \cdot 2^{n-1} – 6P(n-2) \cdot 2^{n-2} + 2^n \\ \text{Divide by } 2^{n-2}:& \quad 4Pn = 10P(n-1) – 6P(n-2) + 4 \\ & \quad 4Pn = 10Pn – 10P – 6Pn + 12P + 4 \\ & \quad 4Pn = 4Pn + 2P + 4 \\ & \quad 0 = 2P + 4 \implies P = -2 \end{aligned} \]
See also  Basic Counting Principle — Complete Lesson for Discrete Mathematics and Combinatorics

So \(a_n^{(p)} = -2n \cdot 2^n\)

Step 3: General solution: \(a_n = A \cdot 2^n + B \cdot 3^n – 2n \cdot 2^n\)

Step 4: Initial conditions:

\[ \begin{aligned} a_0 = 1:& \quad A + B = 1 \quad \text{— (i)} \\ a_1 = 0:& \quad 2A + 3B – 4 = 0 \implies 2A + 3B = 4 \quad \text{— (ii)} \end{aligned} \]

From (i): \(A = 1 – B\). Substitute into (ii): \(2(1-B) + 3B = 4 \implies 2 + B = 4 \implies B = 2\), then \(A = -1\).

\[ \boxed{a_n = -2^n + 2 \cdot 3^n – 2n \cdot 2^n} \]
Common Mistake Alert: When \(f(n) = d^n\) and \(d\) is a root of the characteristic equation, you MUST multiply your guess by \(n\). If \(d\) is a repeated root (multiplicity \(m\)), multiply by \(n^m\). Students who forget this get wrong answers even when all other steps are correct!
Practice Question 8 (MCQ): For \(a_n = 2a_{n-1} + 3\), the correct guess for the particular solution is:
A) \(P \cdot 3^n\)
B) \(P\)
C) \(Pn\)
D) \(P \cdot 2^n\)
Answer: B. Since \(f(n) = 3\) is a constant, we guess \(a_n^{(p)} = P\) (a constant). The root of the homogeneous part is \(r = 2\), not 1, so there is no conflict. We do NOT need to multiply by \(n\). Option A is wrong because \(3^n\) is not the form of \(f(n)\). Option D is the homogeneous solution form, not the particular.
Practice Question 9 (Fill in the Blank): For \(a_n = 4a_{n-1} – 4a_{n-2} + 3 \cdot 2^n\), the guess for the particular solution is \(a_n^{(p)} =\) ______. (The characteristic roots are \(r = 2, 2\).)
Answer: \(a_n^{(p)} = Pn^2 \cdot 2^n\). Here \(f(n) = 3 \cdot 2^n\) so the normal guess would be \(P \cdot 2^n\). But \(r = 2\) is a root with multiplicity 2 (repeated root). So we multiply by \(n^2\) (not just \(n\)). This is a harder case that examiners love!
Practice Question 10 (Workout): Solve \(a_n = a_{n-1} + 2a_{n-2} + 2\) with \(a_0 = 0\) and \(a_1 = 1\).
Answer:
Homogeneous: \(r^2 – r – 2 = 0 \implies (r-2)(r+1) = 0 \implies r_1 = 2, r_2 = -1\)
\(a_n^{(h)} = A \cdot 2^n + B \cdot (-1)^n\)

Particular: \(f(n) = 2\) (constant). Guess \(a_n^{(p)} = P\). Neither 2 nor -1 equals 1, so no conflict.
\(P = P + 2P + 2 \implies P = 3P + 2 \implies -2P = 2 \implies P = -1\)

General: \(a_n = A \cdot 2^n + B \cdot (-1)^n – 1\)

Initial conditions:
\(a_0 = 0\): \(A + B – 1 = 0 \implies A + B = 1\) — (i)
\(a_1 = 1\): \(2A – B – 1 = 1 \implies 2A – B = 2\) — (ii)
Adding (i) and (ii): \(3A = 3 \implies A = 1\), then \(B = 0\).

\[\boxed{a_n = 2^n – 1}\]
Verify: \(a_0 = 1 – 1 = 0\) ✓, \(a_1 = 2 – 1 = 1\) ✓, \(a_2 = 1 + 0 + 2 = 3\) and \(2^2 – 1 = 3\) ✓.

5. Classic Exam Problem: Bit Strings Without Consecutive Zeros

This is one of the most frequently asked problems in discrete mathematics exams. Let me walk you through it carefully.

Worked Example 11: Bit Strings Problem

Problem: Find a recurrence relation and initial conditions for the number of bit strings of length \(n\) that do NOT have two consecutive 0s. How many such strings of length 5?

Solution: Let \(a_n\) = number of bit strings of length \(n\) with no two consecutive 0s.

Think about how a valid string of length \(n\) can start:

Case 1: String starts with 1 ============================================ 1 | _ _ _ … _ (remaining n-1 positions) Any valid string of length n-1 Count: a_{n-1}Case 2: String starts with 0 ============================================ 0 1 | _ _ _ … _ (remaining n-2 positions) (MUST have 1 after 0 to avoid “00”) Any valid string of length n-2 Count: a_{n-2}Total: a_n = a_{n-1} + a_{n-2}

So the recurrence relation is: \(a_n = a_{n-1} + a_{n-2}\) for \(n \geq 2\)

Initial conditions: \(a_0 = 1\) (the empty string) and \(a_1 = 2\) (strings: 0, 1)

Now find \(a_5\): \(a_2 = 3, a_3 = 5, a_4 = 8, a_5 = 13\)

So there are 13 bit strings of length 5 with no two consecutive 0s.

Bonus: Can you solve this recurrence? The characteristic equation is \(r^2 – r – 1 = 0\) (same as Fibonacci!). The roots are \(r = \frac{1 \pm \sqrt{5}}{2}\). Using initial conditions, you get the closed formula.

Practice Question 11 (MCQ): A recurrence relation \(a_n = a_{n-1} + a_{n-2}\) with \(a_0 = 1, a_1 = 2\) produces which sequence?
A) 1, 2, 3, 5, 8, 13, …
B) 1, 1, 2, 3, 5, 8, …
C) 0, 1, 1, 2, 3, 5, …
D) 2, 3, 5, 8, 13, 21, …
Answer: A. Starting with \(a_0 = 1, a_1 = 2\): \(a_2 = 1+2=3\), \(a_3 = 2+3=5\), \(a_4 = 3+5=8\), \(a_5 = 5+8=13\). This is the Fibonacci sequence shifted. Option B is the standard Fibonacci (starting 1,1). Option C starts with 0,1. Know the difference!
Practice Question 12 (True/False): In the bit string problem, if we also require that the string starts with 1, the recurrence relation changes completely.
Answer: False. If we require the string to start with 1, then the count is simply \(a_{n-1}\) (the remaining \(n-1\) positions can be any valid string). The recurrence relation for the original problem does not change — it counts ALL valid strings regardless of starting bit. What changes is the counting method, not the recurrence for the general problem.

6. Quick Summary of All Methods

StepHomogeneousNon-Homogeneous
1. Write characteristic eqnYesYes (ignore \(f(n)\))
2. Find rootsYesYes
3. Write homogeneous solutionYes (this IS the answer form)Yes (this is part of the answer)
4. Find particular solutionNot neededYes — guess based on \(f(n)\), check for conflict
5. CombineJust use step 3\(a_n = a_n^{(h)} + a_n^{(p)}\)
6. Use initial conditionsFind constantsFind constants
Final Exam Tips:
1. Always write the characteristic equation correctly — watch the signs!
2. For non-homogeneous, ALWAYS check if your guess conflicts with the homogeneous solution.
3. When you have repeated roots, remember to multiply by \(n, n^2, \ldots\) accordingly.
4. Verify your answer by plugging back into the original recurrence relation.
5. For bit string problems, think about cases based on how the string starts.

Challenge Conceptual Exam Questions

Test your deep understanding with these questions. They are designed to match the difficulty level of real exam questions.

Multiple Choice Questions

Q1. The sequence \(a_n = n^2\) satisfies which recurrence relation?
A) \(a_n = 2a_{n-1} – a_{n-2}\)
B) \(a_n = a_{n-1} + 2n – 1\)
C) Both A and B
D) Neither A nor B
Answer: C (Both A and B).
Check A: \(2a_{n-1} – a_{n-2} = 2(n-1)^2 – (n-2)^2 = 2(n^2 – 2n + 1) – (n^2 – 4n + 4) = 2n^2 – 4n + 2 – n^2 + 4n – 4 = n^2 – 2 = ?\) Wait — this gives \(n^2 – 2\), not \(n^2\). Let me recheck.
Actually: \(2(n-1)^2 – (n-2)^2 = 2n^2 – 4n + 2 – n^2 + 4n – 4 = n^2 – 2\). This is NOT \(n^2\). So A is wrong.
Check B: \(a_{n-1} + 2n – 1 = (n-1)^2 + 2n – 1 = n^2 – 2n + 1 + 2n – 1 = n^2\). ✓ So B is correct.
Correction: Answer is B only. This question teaches you to always verify by substitution!
Q2. The characteristic equation \(r^3 – 6r^2 + 12r – 8 = 0\) has roots \(r = 2, 2, 2\). The general solution of the corresponding homogeneous recurrence relation is:
A) \(A \cdot 2^n + B \cdot 2^n + C \cdot 2^n\)
B) \((A + Bn + Cn^2) \cdot 2^n\)
C) \(A \cdot 2^n + B \cdot n \cdot 2^n\)
D) \(A \cdot 2^{3n}\)
Answer: B. When a root \(r = 2\) has multiplicity 3 (repeated 3 times), the solution is \((A + Bn + Cn^2) \cdot 2^n\). Option A is wrong because \(A + B + C\) is just a single constant — you cannot combine them that way. Option C only accounts for multiplicity 2. Option D is completely wrong.
Q3. For the recurrence \(a_n = 4a_{n-1} – 4a_{n-2} + 3n + 5\), the correct guess for the particular solution is:
A) \(Pn + Q\)
B) \(n(Pn + Q)\)
C) \(n^2(Pn + Q)\)
D) \(P \cdot 2^n + Qn\)
Answer: B. The homogeneous part has characteristic equation \(r^2 – 4r + 4 = (r-2)^2 = 0\). The root is \(r = 2\) (repeated). Since \(f(n) = 3n + 5\) is linear, the normal guess is \(Pn + Q\). But we check: does this conflict? The conflict happens when \(r = 1\) is a root (since \(1^n = 1\) is a constant, matching the form). Here \(r = 2 \neq 1\), so actually there is NO conflict. Correction: Answer is A. The guess \(Pn + Q\) does NOT conflict because 1 is not a root. This is a tricky question — the conflict rule for \(f(n) = \text{polynomial}\) applies when 1 is a root, not when 2 is a root. Many students get this wrong!
See also  The Inclusion-Exclusion Principle – Notes, Examples & Practice Questions (Discrete Mathematics)
Q4. How many initial conditions are needed to uniquely determine a solution for \(a_n = 3a_{n-1} – 2a_{n-2} + a_{n-3}\)?
A) 1
B) 2
C) 3
D) 4
Answer: C. The recurrence relation is of degree 3 (the farthest back it goes is \(a_{n-3}\), so the gap is 3). A recurrence relation of degree \(k\) needs exactly \(k\) initial conditions. Here \(k = 3\), so we need 3 initial conditions (e.g., \(a_0, a_1, a_2\)).
Q5. Which of the following sequences is a solution of \(a_n = 4a_{n-1} – 3a_{n-2}\)?
A) \(a_n = 2^n\)
B) \(a_n = 3^n\)
C) Both A and B
D) Neither A nor B
Answer: C (Both).
Check A: \(4(2^{n-1}) – 3(2^{n-2}) = 2^{n-2}(8 – 3) = 5 \cdot 2^{n-2}\). But \(2^n = 4 \cdot 2^{n-2}\). Since \(5 \neq 4\), this does NOT work. Let me recheck carefully.
\(4 \cdot 2^{n-1} = 2^2 \cdot 2^{n-1} = 2^{n+1}\) and \(3 \cdot 2^{n-2} = 3 \cdot 2^{n-2}\). So \(2^{n+1} – 3 \cdot 2^{n-2} = 2^{n-2}(8 – 3) = 5 \cdot 2^{n-2}\). But \(a_n = 2^n = 4 \cdot 2^{n-2}\). Not equal!
Check B: \(4 \cdot 3^{n-1} – 3 \cdot 3^{n-2} = 3^{n-2}(12 – 3) = 9 \cdot 3^{n-2} = 3^n\) ✓
Correction: Answer is B only. Always verify carefully — \(2^n\) is NOT a solution here. The characteristic equation is \(r^2 – 4r + 3 = (r-1)(r-3) = 0\), so roots are 1 and 3. Solutions are \(A \cdot 1^n + B \cdot 3^n = A + B \cdot 3^n\). Only \(3^n\) works (when \(A = 0\)).

True / False Questions

Q6. A linear recurrence relation of degree \(k\) always has exactly \(k\) distinct roots in its characteristic equation.
Answer: False. The roots may be repeated (like \(r = 2, 2\)) or even complex (like \(r = 1 \pm i\)). The word “distinct” makes this statement false. A degree \(k\) equation always has \(k\) roots (counting multiplicity), but they need not be distinct.
Q7. The recurrence relation \(a_n = n \cdot a_{n-1}\) is a linear recurrence relation with constant coefficients.
Answer: False. It IS linear, but the coefficient of \(a_{n-1}\) is \(n\), which is NOT constant (it changes with \(n\)). So it is linear but NOT with constant coefficients.
Q8. If \(a_n = 3^n\) is a solution of a homogeneous linear recurrence relation, then \(r = 3\) must be a root of its characteristic equation.
Answer: True. This is a fundamental theorem. Every solution of the form \(A \cdot r^n\) corresponds to root \(r\) of the characteristic equation. If \(3^n\) is a solution, then \(r = 3\) is a root.
Q9. For a non-homogeneous recurrence, if \(f(n) = 5^n\) and \(r = 5\) is NOT a root of the characteristic equation, then the particular solution is of the form \(P \cdot 5^n\).
Answer: True. When there is no conflict (5 is not a root), the guess \(P \cdot 5^n\) is correct. If 5 WERE a root, we would need \(Pn \cdot 5^n\) or \(Pn^2 \cdot 5^n\) depending on multiplicity.

Fill in the Blank Questions

Q10. The recurrence relation for the Fibonacci sequence is \(a_n =\) ______ with initial conditions \(a_0 =\) ______ and \(a_1 =\) ______.
Answer: \(a_n = a_{n-1} + a_{n-2}\), \(a_0 = 0\), \(a_1 = 1\). (Note: Some textbooks define Fibonacci with \(a_1 = 1, a_2 = 1\). The standard definition in our reference uses \(a_0 = 0, a_1 = 1\).)
Q11. If the characteristic equation has roots \(r = -1, -1, 3\), then the general solution is \(a_n =\) ______.
Answer: \(a_n = (A + Bn)(-1)^n + C \cdot 3^n\). The root \(-1\) is repeated twice, so it contributes \((A + Bn)(-1)^n\). The root \(3\) is distinct, contributing \(C \cdot 3^n\).
Q12. For \(a_n = 2a_{n-1} + n^2\), since \(r = 1\) is not a root, the guess for the particular solution is \(a_n^{(p)} =\) ______.
Answer: \(a_n^{(p)} = Pn^2 + Qn + R\). Since \(f(n) = n^2\) is a quadratic polynomial, we guess a general quadratic. Since 1 is not a root (the only root is \(r = 2\)), there is no conflict.

Short Answer / Workout Questions

Q13. Solve completely: \(a_n = 3a_{n-1} – 2a_{n-2}\) with \(a_0 = 2\) and \(a_1 = 3\).
Answer:
Characteristic equation: \(r^2 – 3r + 2 = 0 \implies (r-1)(r-2) = 0 \implies r_1 = 1, r_2 = 2\)
General solution: \(a_n = A \cdot 1^n + B \cdot 2^n = A + B \cdot 2^n\)
Initial conditions:
\(a_0 = 2\): \(A + B = 2\) — (i)
\(a_1 = 3\): \(A + 2B = 3\) — (ii)
(ii) – (i): \(B = 1\), then \(A = 1\)
\[\boxed{a_n = 1 + 2^n}\]
Verify: \(a_0 = 1 + 1 = 2\) ✓, \(a_1 = 1 + 2 = 3\) ✓, \(a_2 = 3(3) – 2(2) = 5\) and \(1 + 4 = 5\) ✓.
Q14. Solve completely: \(a_n = 2a_{n-1} – a_{n-2} + 6n\) with \(a_0 = 1\) and \(a_1 = 2\).
Answer:
Homogeneous: \(r^2 – 2r + 1 = (r-1)^2 = 0\). Root \(r = 1\) with multiplicity 2.
\(a_n^{(h)} = (A + Bn) \cdot 1^n = A + Bn\)

Particular: \(f(n) = 6n\) (linear). Normal guess: \(Pn + Q\). But \(r = 1\) IS a root (multiplicity 2), so there is a conflict. Multiply by \(n^2\):
Guess: \(a_n^{(p)} = n^2(Pn + Q) = Pn^3 + Qn^2\)
Substitute: \(Pn^3 + Qn^2 = 2[P(n-1)^3 + Q(n-1)^2] – [P(n-2)^3 + Q(n-2)^2] + 6n\)
Expanding and comparing coefficients:
Coefficient of \(n^3\): \(P = 2P – P = P\) ✓ (identity, gives no info)
Coefficient of \(n^2\): \(Q = 2(-3P + Q) – (-6P + Q) = -6P + 2Q + 6P – Q = Q\) ✓ (identity)
Coefficient of \(n^1\): \(0 = 2(3P – 2Q) – (12P – 4Q) + 6 = 6P – 4Q – 12P + 4Q + 6 = -6P + 6\)
So \(-6P + 6 = 0 \implies P = 1\)
Coefficient of \(n^0\): \(0 = 2(-P + Q) – (-8P + 4Q) = -2P + 2Q + 8P – 4Q = 6P – 2Q\)
So \(6(1) – 2Q = 0 \implies Q = 3\)
\(a_n^{(p)} = n^3 + 3n^2\)

General: \(a_n = A + Bn + n^3 + 3n^2\)

Initial conditions:
\(a_0 = 1\): \(A = 1\)
\(a_1 = 2\): \(1 + B + 1 + 3 = 2 \implies B + 5 = 2 \implies B = -3\)
\[\boxed{a_n = 1 – 3n + 3n^2 + n^3}\]
Verify: \(a_0 = 1\) ✓, \(a_1 = 1 – 3 + 3 + 1 = 2\) ✓, \(a_2 = 1 – 6 + 12 + 8 = 15\) and from recurrence: \(2(2) – 1 + 12 = 15\) ✓.
Q15. A person deposits 5000 birr in a bank that pays 8% interest per year, compounded annually. Additionally, they deposit 1000 birr at the end of each year. Set up the recurrence relation and solve it to find the amount after \(n\) years.
Answer:
Let \(A_n\) = amount at end of year \(n\).
Each year: the previous amount grows by 8%, plus 1000 is added.
\[ A_n = 1.08 \, A_{n-1} + 1000, \quad A_0 = 5000 \]

Homogeneous: \(r – 1.08 = 0 \implies r = 1.08\)
\(A_n^{(h)} = A \cdot (1.08)^n\)

Particular: Guess \(A_n^{(p)} = P\). \(P = 1.08P + 1000 \implies -0.08P = 1000 \implies P = -12500\)
(No conflict since 1 is not the root; 1.08 is the root.)

General: \(A_n = A \cdot (1.08)^n – 12500\)

Initial condition: \(A_0 = 5000 = A – 12500 \implies A = 17500\)
\[\boxed{A_n = 17500 \cdot (1.08)^n – 12500}\]
This formula lets you find the amount after any number of years without computing year by year!
Q16. Find a recurrence relation for the number of ways to climb \(n\) stairs if you can take 1 or 2 steps at a time. Also find how many ways to climb 6 stairs.
Answer:
Let \(a_n\) = number of ways to climb \(n\) stairs.
To reach step \(n\), your last move is either:
– 1 step from step \(n-1\): \(a_{n-1}\) ways
– 2 steps from step \(n-2\): \(a_{n-2}\) ways
So: \(a_n = a_{n-1} + a_{n-2}\) for \(n \geq 2\)
Initial conditions: \(a_0 = 1\) (stay where you are), \(a_1 = 1\) (only one 1-step)

Compute: \(a_2 = 2, a_3 = 3, a_4 = 5, a_5 = 8, a_6 = 13\)
There are 13 ways to climb 6 stairs. This is the Fibonacci sequence! The closed formula is the same as the Fibonacci closed form (Binet’s formula).
Q17. Solve \(a_n = a_{n-1} + 2\) with \(a_0 = 5\). Verify that the solution satisfies both the recurrence relation and the initial condition.
Answer:
Homogeneous: \(r – 1 = 0 \implies r = 1\). So \(a_n^{(h)} = A \cdot 1^n = A\).

Particular: \(f(n) = 2\) (constant). Guess \(P\). But \(r = 1\) IS a root! So we have a conflict. Multiply by \(n\): guess \(a_n^{(p)} = Pn\).
Substitute: \(Pn = P(n-1) + 2 \implies Pn = Pn – P + 2 \implies P = 2\)
So \(a_n^{(p)} = 2n\).

General: \(a_n = A + 2n\)

Initial condition: \(a_0 = 5 = A + 0 \implies A = 5\)
\[\boxed{a_n = 5 + 2n}\]

Verification:
– Initial condition: \(a_0 = 5 + 0 = 5\) ✓
– Recurrence: \(a_n = 5 + 2n\) and \(a_{n-1} + 2 = 5 + 2(n-1) + 2 = 5 + 2n – 2 + 2 = 5 + 2n = a_n\) ✓
This confirms the solution is correct. Notice how the conflict rule was essential here — without multiplying by \(n\), we would have gotten a wrong answer.

Related Posts

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top