Hello dear students! Welcome to this complete study guide on Recurrence Relations. If you are a student in an Ethiopian university taking Discrete Mathematics and Combinatorics (Math 2031), then you are in the right place. In this lesson, I will explain every concept you need to know for your exam, step by step, with many worked examples and practice questions. Take your time reading each section, try the questions, and you will be well prepared. Let us begin!
What is a Recurrence Relation?
Before we start solving problems, you need to understand what a recurrence relation actually is. Think about this: when you count something step by step, sometimes you can express the answer at step n in terms of the answers at earlier steps. That is exactly what a recurrence relation does.
A recurrence relation for a sequence $\{a_n\}_{n=0}^{\infty}$ 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 integers $n \geq n_0$, where $n_0$ is a non-negative integer.
In simple words: a recurrence relation tells you how to find the next term of a sequence by looking at the terms that came before it. You do not get a direct formula for $a_n$. Instead, you get a rule that connects $a_n$ to earlier terms.
Let me give you a very simple example to make this clear. Look at this sequence:
Can you see the pattern? Each term is obtained by multiplying the previous term by 2. So we can write this as a recurrence relation:
This equation says: “To get the $n$-th term, take the $(n-1)$-th term and multiply it by 2.” But wait, we also need a starting point. We need to know what $a_0$ is. That is why we also write:
This starting value is called an initial condition. Without it, we cannot compute any term because we would not know where to start. With $a_0 = 3$ and $a_n = 2a_{n-1}$, we can compute every term: $a_1 = 2 \times 3 = 6$, $a_2 = 2 \times 6 = 12$, and so on.
Now, compare this with an explicit formula. For the same sequence, we can also write:
This is called a closed-form formula or an explicit solution. It gives you $a_n$ directly without needing to know any previous term. One of the main things we do in this chapter is learn how to go from a recurrence relation to a closed-form formula.
Recurrence relation: An equation that defines $a_n$ using previous terms.
Initial condition: A specific value given for one or more early terms (like $a_0 = 3$).
Solution: A sequence whose terms satisfy the recurrence relation.
Closed-form formula: A direct formula for $a_n$ that does not reference previous terms.
Let me show you another example. Consider the sequence:
This is the famous Fibonacci sequence. Each term (from the third term onward) is the sum of the two previous terms. So the recurrence relation is:
Notice that this recurrence relation uses two previous terms, not just one. That makes it different from the first example. The number of previous terms used tells us the order of the recurrence relation, which we will discuss shortly.
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 work step by step from the initial conditions.
$a_2 = 2a_1 – a_0 = 2(4) – 3 = 8 – 3 = 5$
$a_3 = 2a_2 – a_1 = 2(5) – 4 = 10 – 4 = 6$
$a_4 = 2a_3 – a_2 = 2(6) – 5 = 12 – 5 = 7$
$a_5 = 2a_4 – a_3 = 2(7) – 6 = 14 – 6 = 8$
$a_6 = 2a_5 – a_4 = 2(8) – 7 = 16 – 7 = \mathbf{9}$
So $a_6 = 9$. You can see the pattern: $3, 4, 5, 6, 7, 8, 9, \ldots$ This sequence simply counts up from 3. The closed-form formula would be $a_n = n + 3$.
Question 1 (MCQ): Which of the following is a recurrence relation?
A) $a_n = n^2 + 3$ B) $a_n = 2a_{n-1} + 5$ C) $a_n = \binom{n}{2}$ D) $a_n = 3^n – 1$Answer: B
A recurrence relation must express $a_n$ in terms of one or more previous terms of the sequence. Let us check each option:
A) $a_n = n^2 + 3$ — This gives $a_n$ directly from $n$, not from previous terms. This is a closed-form formula, not a recurrence relation.
B) $a_n = 2a_{n-1} + 5$ — This expresses $a_n$ using the previous term $a_{n-1}$. This is a recurrence relation.
C) $a_n = \binom{n}{2}$ — Again, direct formula using $n$, not previous terms.
D) $a_n = 3^n – 1$ — Direct formula, not a recurrence relation.
Question 2 (Workout): A sequence is defined by $a_n = 3a_{n-1} + 2$ with $a_0 = 1$. Find $a_1, a_2, a_3,$ and $a_4$.
Solution:
So: $a_1 = 5$, $a_2 = 17$, $a_3 = 53$, $a_4 = 161$.
Notice: This is exactly the sequence from Example 3 in your textbook (Temesgen Molla): 1, 5, 17, 53, 161, 485, … Each term is roughly 3 times the previous term plus 2.
Question 3 (Workout): Determine whether $a_n = 2^n + 1$ is a solution of the recurrence relation $a_n = 2a_{n-1} – 1$ with $a_1 = 3$.
Solution: To check if a sequence is a solution, we must verify two things: (1) the initial condition, and (2) the recurrence relation itself.
Step 1: Check the initial condition.
When $n = 1$: $a_1 = 2^1 + 1 = 2 + 1 = 3$. This matches the given $a_1 = 3$. Good.
Step 2: Check the recurrence relation.
Left side: $a_n = 2^n + 1$
Right side: $2a_{n-1} – 1 = 2(2^{n-1} + 1) – 1 = 2^n + 2 – 1 = 2^n + 1$
Left side equals right side: $2^n + 1 = 2^n + 1$. Yes, it is a solution!
How to Form Recurrence Relations from Word Problems
One of the most important skills for your exam is the ability to read a word problem and write the correct recurrence relation. Many exam questions will give you a real-world situation and ask you to find the recurrence relation. Let me walk you through several examples so you can master this skill.
Example 1: Compound Interest (From Your Textbook)
A person invests 10,000 birr at 12% interest compounded annually. How much will be there at the end of 15 years?
Thinking process: Let $A_n$ represent the amount at the end of $n$ years. At the end of $n-1$ years, the amount is $A_{n-1}$. During the $n$-th year, interest of 12% is added. So the new amount equals the old amount plus 12% of the old amount:
This is a first-order linear homogeneous recurrence relation. Its solution is straightforward:
So $A_{15} = (1.12)^{15} \times 10{,}000 \approx 54{,}735.66$ birr.
Example 2: Bit Strings Without Consecutive 0s
This is a classic problem that appears very often on exams. The question is: How many bit strings of length $n$ do not contain two consecutive 0s?
Thinking process: Let $a_n$ be the number of valid bit strings of length $n$. We need to express $a_n$ in terms of earlier values. How can a valid bit string of length $n$ be formed?
Now we need initial conditions. For $n = 1$: the valid strings are “0” and “1”, so $a_1 = 2$. For $n = 2$: the valid strings are “01”, “10”, “11” (but NOT “00”), so $a_2 = 3$.
Example 3: The Fibonacci Sequence
The Fibonacci sequence is defined by the recurrence relation $a_n = a_{n-1} + a_{n-2}$ with $a_0 = 0$ and $a_1 = 1$ (in some textbooks, $a_1 = 1, a_2 = 1$). This sequence arises naturally in many problems.
One famous example: Suppose rabbits never die, and each pair of adult rabbits produces one new pair every month starting from the second month of their life. If we start with one newborn pair, how many pairs do we have after $n$ months?
Example 4: Tower of Hanoi
The Tower of Hanoi puzzle has $n$ disks of different sizes and three pegs. You must move all disks from peg 1 to peg 3, moving one disk at a time, and you can never place a larger disk on top of a smaller one. How many moves are needed?
Let $H_n$ be the number of moves needed for $n$ disks. To move $n$ disks from peg 1 to peg 3:
The solution is $H_n = 2^n – 1$. For example, with 3 disks: $H_3 = 2^3 – 1 = 7$ moves. With 64 disks (the original legend): $H_{64} = 2^{64} – 1$, which is an enormous number!
Compound interest: $A_n = (1 + r)^n \times A_0$ where $r$ is the interest rate
Bit strings without consecutive 0s: $a_n = a_{n-1} + a_{n-2}$, $a_1 = 2$, $a_2 = 3$
Fibonacci: $F_n = F_{n-1} + F_{n-2}$, $F_0 = 0$, $F_1 = 1$
Tower of Hanoi: $H_n = 2H_{n-1} + 1$, solution: $H_n = 2^n – 1$
Geometric growth: $a_n = r \cdot a_{n-1}$, solution: $a_n = a_0 \cdot r^n$
Question 4 (Workout): Find a recurrence relation for the number of bit strings of length $n$ that contain three consecutive 0s.
Solution: Let $a_n$ be the number of bit strings of length $n$ that contain “000” somewhere. Instead of counting directly, it is easier to count the complement (strings that do NOT contain “000”) and subtract from $2^n$. But let us use the direct approach.
Think about how a string of length $n$ that contains “000” can end:
Case 1: It ends in “000”. Then the first $n-3$ bits can be anything: $2^{n-3}$ strings.
Case 2: It ends in “1000”. But this is already counted in Case 1 if the “000” includes the last three positions. Let me use a cleaner method.
Cleaner method: Let $a_n$ = number of bit strings of length $n$ containing “000”. Consider the last bit:
If the string ends in 1, then we need “000” somewhere in the first $n-1$ bits: $a_{n-1}$ strings.
If the string ends in 01, then we need “000” in the first $n-2$ bits: $a_{n-2}$ strings.
If the string ends in 001, then we need “000” in the first $n-3$ bits: $a_{n-3}$ strings.
If the string ends in 000, the first $n-3$ bits can be anything: $2^{n-3}$ strings.
Therefore:
With initial conditions: $a_0 = 0$, $a_1 = 0$, $a_2 = 0$ (no string of length 0, 1, or 2 can contain “000”).
Question 5 (MCQ): The recurrence relation for the number of ways to climb a staircase with $n$ steps if you can take 1 or 2 steps at a time is:
A) $a_n = a_{n-1} + a_{n-2}$, $a_1 = 1$, $a_2 = 2$ B) $a_n = 2a_{n-1}$, $a_1 = 1$ C) $a_n = a_{n-1} + 2a_{n-2}$, $a_1 = 1$, $a_2 = 3$ D) $a_n = n \cdot a_{n-1}$, $a_1 = 1$Answer: A
Let $a_n$ be the number of ways to climb $n$ steps. Think about your first move:
If you take 1 step first, then you need to climb the remaining $n-1$ steps: $a_{n-1}$ ways.
If you take 2 steps first, then you need to climb the remaining $n-2$ steps: $a_{n-2}$ ways.
Total: $a_n = a_{n-1} + a_{n-2}$. For $a_1$: only 1 way (take 1 step). For $a_2$: 2 ways (1+1 or 2). This matches option A. This is actually the Fibonacci sequence shifted!
Types of Recurrence Relations
Not all recurrence relations are solved the same way. Before solving, you must identify what type you are dealing with. This section explains the different types, and knowing these will help you choose the right solution method on the exam.
Order of a Recurrence Relation
The order of a recurrence relation is the difference between the largest and smallest subscript of $a$ in the relation.
$a_n = 2a_{n-1}$ — Order 1 (uses $a_n$ and $a_{n-1}$, difference is 1)
$a_n = a_{n-1} + a_{n-2}$ — Order 2 (uses $a_n$, $a_{n-1}$, $a_{n-2}$, difference is 2)
$a_n = 3a_{n-1} + 2a_{n-2} – a_{n-3}$ — Order 3
Linear vs Non-linear
A recurrence relation is linear if every term $a_i$ appears to the power of 1 (no squares, no products of terms, no functions applied to terms).
$a_n = 2a_{n-1} + 3$ — Linear (each $a_i$ has power 1)
$a_n = a_{n-1} + a_{n-2}$ — Linear
Non-linear:$a_n = a_{n-1}^2$ — Non-linear ($a_{n-1}$ is squared)
$a_n = a_{n-1} \cdot a_{n-2}$ — Non-linear (product of terms)
Homogeneous vs Non-homogeneous
A linear recurrence relation is homogeneous if all terms on the right side involve $a_i$ only (no “extra” terms that are just numbers or functions of $n$ alone). If there is an extra term that does not involve $a_i$, it is non-homogeneous.
$a_n = 2a_{n-1}$ — Homogeneous (only $a_{n-1}$ on the right)
$a_n = 3a_{n-1} – 2a_{n-2}$ — Homogeneous
Non-homogeneous:$a_n = 2a_{n-1} + 3$ — Non-homogeneous (the “+3” does not involve $a_i$)
$a_n = a_{n-1} + n^2$ — Non-homogeneous (the “$n^2$” does not involve $a_i$)
$a_n = a_{n-1} + 2^n$ — Non-homogeneous (the “$2^n$” does not involve $a_i$)
Constant Coefficients
A recurrence relation has constant coefficients if the numbers multiplying the $a_i$ terms are constants (do not depend on $n$).
$a_n = 3a_{n-1} – 2a_{n-2}$ (coefficients 3 and -2 are constants)
Non-constant coefficients:$a_n = n \cdot a_{n-1}$ (coefficient $n$ depends on $n$)
A recurrence relation of the form $c_0 a_n + c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} = f(n)$ is called a linear recurrence relation of order k with constant coefficients.
It is homogeneous if $f(n) = 0$ for all $n$.
It is non-homogeneous if $f(n) \neq 0$.
The standard form we use (with $a_n$ coefficient = 1) is:
$a_n + c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} = f(n)$
Question 6 (MCQ): Classify the recurrence relation $a_n = n \cdot a_{n-1} + 1$:
A) Linear, homogeneous, constant coefficients B) Linear, non-homogeneous, non-constant coefficients C) Non-linear, non-homogeneous, constant coefficients D) Linear, homogeneous, non-constant coefficientsAnswer: B
Linear? Yes — each $a_i$ appears to the power of 1 only.
Homogeneous? No — the “+1” is an extra term not involving $a_i$, so it is non-homogeneous.
Constant coefficients? No — the coefficient of $a_{n-1}$ is $n$, which depends on $n$. So non-constant coefficients.
Therefore: Linear, non-homogeneous, non-constant coefficients. Option B is correct.
Question 7 (MCQ): Which of the following is a second-order linear homogeneous recurrence relation with constant coefficients?
A) $a_n = 2a_{n-1} + n$ B) $a_n = a_{n-1}^2 + a_{n-2}$ C) $a_n – 5a_{n-1} + 6a_{n-2} = 0$ D) $a_n = n \cdot a_{n-1} + a_{n-2}$Answer: C
Let us check each option:
A) $a_n = 2a_{n-1} + n$ — First order (only $a_{n-1}$), and non-homogeneous (has $+n$). Wrong.
B) $a_n = a_{n-1}^2 + a_{n-2}$ — Non-linear ($a_{n-1}$ is squared). Wrong.
C) $a_n – 5a_{n-1} + 6a_{n-2} = 0$ — Second order (uses $a_{n-1}$ and $a_{n-2}$), linear (power 1), homogeneous (= 0), constant coefficients (5 and 6). Correct!
D) $a_n = n \cdot a_{n-1} + a_{n-2}$ — Non-constant coefficients (coefficient of $a_{n-1}$ is $n$). Wrong.
Solving First-Order Linear Recurrence Relations
A first-order linear recurrence relation has the form $a_n = c \cdot a_{n-1} + f(n)$, where $c$ is a constant and $f(n)$ is some function of $n$. Let us learn how to solve both the homogeneous and non-homogeneous cases.
The Homogeneous Case: $a_n = c \cdot a_{n-1}$
This is the simplest type. The solution is straightforward:
This is just a geometric sequence. For example, if $a_n = 3a_{n-1}$ with $a_0 = 5$, then $a_n = 5 \cdot 3^n$.
The Non-homogeneous Case: $a_n = c \cdot a_{n-1} + d$ (where $d$ is constant)
When $f(n) = d$ (a constant), we can solve using the iteration method (also called back-substitution). Let me show you with an example.
Method: Iteration (Back-substitution)
Now let me substitute repeatedly to find a pattern:
Solution: $a_n = 4 \cdot 2^n – 3 = 2^{n+2} – 3$
Verification: $a_0 = 4 – 3 = 1$ ✓, $a_1 = 8 – 3 = 5$ ✓, $a_2 = 16 – 3 = 13$ ✓
If $c \neq 1$: $a_n = \left(a_0 + \frac{d}{1-c}\right) c^n – \frac{d}{1-c}$
If $c = 1$: $a_n = a_0 + n \cdot d$ (this is just an arithmetic sequence)
For $a_n = c \cdot a_{n-1}$ (homogeneous): $a_n = a_0 \cdot c^n$
For $a_n = c \cdot a_{n-1} + d$, $c \neq 1$: $a_n = \left(a_0 + \frac{d}{1-c}\right) c^n – \frac{d}{1-c}$
For $a_n = a_{n-1} + d$ (arithmetic): $a_n = a_0 + n \cdot d$
Question 8 (Workout): Solve the recurrence relation $a_n = 3a_{n-1} + 2$ with $a_0 = 1$. Give the closed-form formula.
Solution using the general formula:
Here $c = 3$, $d = 2$, $a_0 = 1$. Since $c \neq 1$:
$a_n = \left(a_0 + \frac{d}{1-c}\right) c^n – \frac{d}{1-c}$
$= \left(1 + \frac{2}{1-3}\right) 3^n – \frac{2}{1-3}$
$= \left(1 + \frac{2}{-2}\right) 3^n – \frac{2}{-2}$
$= (1 – 1) \cdot 3^n + 1$
$= 0 \cdot 3^n + 1 = 1$
Wait, that gives $a_n = 1$ for all $n$, but we computed earlier that $a_1 = 5$, $a_2 = 17$. Let me recheck.
Correction: Let me recompute carefully:
$\frac{d}{1-c} = \frac{2}{1-3} = \frac{2}{-2} = -1$
$a_0 + \frac{d}{1-c} = 1 + (-1) = 0$
$a_n = 0 \cdot 3^n – (-1) = 0 + 1 = 1$
But this is wrong! Let me use the iteration method instead.
$a_n = 3a_{n-1} + 2 = 3(3a_{n-2} + 2) + 2 = 3^2 a_{n-2} + 3 \cdot 2 + 2$
$= 3^n a_0 + 2(3^{n-1} + 3^{n-2} + \cdots + 3 + 1)$
$= 3^n + 2 \cdot \frac{3^n – 1}{3 – 1} = 3^n + 2 \cdot \frac{3^n – 1}{2} = 3^n + 3^n – 1 = 2 \cdot 3^n – 1$
Correct solution: $\boxed{a_n = 2 \cdot 3^n – 1}$
Verification: $a_0 = 2 – 1 = 1$ ✓, $a_1 = 6 – 1 = 5$ ✓, $a_2 = 18 – 1 = 17$ ✓, $a_3 = 54 – 1 = 53$ ✓
Lesson: The general formula is $a_n = \left(a_0 – \frac{d}{c-1}\right) c^n + \frac{d}{c-1}$. Note the signs! With $c-1$ in the denominator, not $1-c$.
Using the corrected formula: $\frac{d}{c-1} = \frac{2}{3-1} = 1$, so $a_n = (1 – 1) \cdot 3^n + 1 = 1$. Still wrong!
The correct general formula should be: $a_n = a_0 \cdot c^n + d \cdot \frac{c^n – 1}{c – 1}$
$= 1 \cdot 3^n + 2 \cdot \frac{3^n – 1}{2} = 3^n + 3^n – 1 = 2 \cdot 3^n – 1$ ✓
So use this safer formula: $a_n = a_0 \cdot c^n + d \cdot \dfrac{c^n – 1}{c – 1}$
Question 9 (MCQ): The solution of $a_n = a_{n-1} + 5$ with $a_0 = 3$ is:
A) $a_n = 5n + 3$ B) $a_n = 3 \cdot 5^n$ C) $a_n = 5n + 3^n$ D) $a_n = 3 + 5n$Answer: D
Here $c = 1$, so this is an arithmetic sequence. The formula is $a_n = a_0 + n \cdot d = 3 + 5n$.
Verification: $a_0 = 3$ ✓, $a_1 = 3 + 5 = 8$ (check: $a_1 = a_0 + 5 = 3 + 5 = 8$ ✓), $a_2 = 3 + 10 = 13$ (check: $a_2 = a_1 + 5 = 8 + 5 = 13$ ✓).
Options A and D are actually the same expression ($5n + 3 = 3 + 5n$), so both are mathematically correct. Both A and D would be accepted.
Solving Second-Order Homogeneous Linear Recurrence Relations
Now we come to one of the most important topics for your exam. A second-order homogeneous linear recurrence relation with constant coefficients has the form:
Or equivalently: $a_n = -c_1 a_{n-1} – c_2 a_{n-2}$, but it is more common to write it with all terms on one side equal to zero.
The method we use to solve these is called the characteristic equation method. Here is how it works.
Step 1: Write the Characteristic Equation
Replace each $a_{n-k}$ with $r^{n-k}$, then divide everything by $r^{n-2}$ (the smallest power). This gives you a polynomial equation in $r$.
This is called the characteristic equation (or auxiliary equation).
Step 2: Solve the Characteristic Equation
Find the roots of this quadratic equation. Depending on the roots, you get one of three cases.
Step 3: Write the General Solution Based on the Case
Case 1: Two Distinct Real Roots $r_1 \neq r_2$
$$a_n = A \cdot r_1^n + B \cdot r_2^n$$ where $A$ and $B$ are constants determined by initial conditions.
Case 2: One Repeated Root $r$ (multiplicity 2)
$$a_n = (A + Bn) \cdot r^n$$ where $A$ and $B$ are constants determined by initial conditions.
Case 3: Complex Roots $r = \alpha \pm \beta i$
$$a_n = R^n \left(A \cos(n\theta) + B \sin(n\theta)\right)$$ where $R = \sqrt{\alpha^2 + \beta^2}$ and $\theta = \arctan\left(\dfrac{\beta}{\alpha}\right)$
Step 4: Use Initial Conditions to Find A and B
Substitute the initial conditions (like $a_0 = \ldots$, $a_1 = \ldots$) into the general solution to create a system of two equations. Solve for $A$ and $B$.
Now let me show you detailed examples for each case.
Case 1: Two Distinct Real Roots — Detailed Example
Step 1: Write the characteristic equation:
$r^2 – 5r + 6 = 0$
Step 2: Factor and find roots:
$(r – 2)(r – 3) = 0$, so $r_1 = 2$, $r_2 = 3$
Two distinct real roots — this is Case 1.
Step 3: Write the general solution:
Step 4: Use initial conditions to find $A$ and $B$:
For $n = 0$: $a_0 = A \cdot 2^0 + B \cdot 3^0 = A + B = 2$ … (i)
For $n = 1$: $a_1 = A \cdot 2^1 + B \cdot 3^1 = 2A + 3B = 5$ … (ii)
From (i): $A = 2 – B$. Substitute into (ii):
$2(2 – B) + 3B = 5$
$4 – 2B + 3B = 5$
$4 + B = 5$
$B = 1$, then $A = 2 – 1 = 1$
Final solution:
Verification: $a_0 = 1 + 1 = 2$ ✓, $a_1 = 2 + 3 = 5$ ✓, $a_2 = 4 + 9 = 13$ (check: $a_2 = 5(5) – 6(2) = 25 – 12 = 13$ ✓)
Case 2: One Repeated Root — Detailed Example
Step 1: Characteristic equation: $r^2 – 6r + 9 = 0$
Step 2: $(r – 3)^2 = 0$, so $r = 3$ (repeated root)
This is Case 2.
Step 3: General solution:
Step 4: Use initial conditions:
$n = 0$: $a_0 = (A + 0) \cdot 3^0 = A = 1$
$n = 1$: $a_1 = (A + B) \cdot 3^1 = (1 + B) \cdot 3 = 6$
$1 + B = 2$, so $B = 1$
Final solution:
Verification: $a_0 = 1 \cdot 1 = 1$ ✓, $a_1 = 2 \cdot 3 = 6$ ✓, $a_2 = 3 \cdot 9 = 27$ (check: $a_2 = 6(6) – 9(1) = 36 – 9 = 27$ ✓)
Case 3: Complex Roots — Detailed Example
Step 1: Characteristic equation: $r^2 – 2r + 2 = 0$
Step 2: Using the quadratic formula: $r = \dfrac{2 \pm \sqrt{4 – 8}}{2} = \dfrac{2 \pm \sqrt{-4}}{2} = 1 \pm i$
Complex roots! This is Case 3. Here $\alpha = 1$, $\beta = 1$.
$R = \sqrt{\alpha^2 + \beta^2} = \sqrt{1 + 1} = \sqrt{2}$
$\theta = \arctan\left(\dfrac{\beta}{\alpha}\right) = \arctan(1) = \dfrac{\pi}{4}$
Step 3: General solution:
Step 4: Use initial conditions:
$n = 0$: $a_0 = 1 \cdot (A \cdot 1 + B \cdot 0) = A = 1$
$n = 1$: $a_1 = \sqrt{2} \left(1 \cdot \cos\frac{\pi}{4} + B \cdot \sin\frac{\pi}{4}\right) = \sqrt{2}\left(\frac{1}{\sqrt{2}} + B \cdot \frac{1}{\sqrt{2}}\right) = 1 + B = 2$
So $B = 1$.
Final solution:
Given: $a_n + c_1 a_{n-1} + c_2 a_{n-2} = 0$
Step 1: Characteristic equation: $r^2 + c_1 r + c_2 = 0$
Step 2: Find roots $r_1, r_2$
Step 3: General solution:
Case 1 (distinct): $a_n = A r_1^n + B r_2^n$
Case 2 (repeated $r$): $a_n = (A + Bn) r^n$
Case 3 (complex $\alpha \pm \beta i$): $a_n = R^n(A \cos n\theta + B \sin n\theta)$
Step 4: Use initial conditions to find $A$ and $B$
Question 10 (Workout): Solve the recurrence relation $a_n = 5a_{n-1} – 6a_{n-2}$ with $a_0 = 0$ and $a_1 = 1$.
Solution:
Step 1: Rewrite in standard form: $a_n – 5a_{n-1} + 6a_{n-2} = 0$
Step 2: Characteristic equation: $r^2 – 5r + 6 = 0$
$(r-2)(r-3) = 0$, so $r_1 = 2$, $r_2 = 3$. (Case 1: distinct real roots)
Step 3: General solution: $a_n = A \cdot 2^n + B \cdot 3^n$
Step 4: Initial conditions:
$n = 0$: $A + B = 0$, so $A = -B$ … (i)
$n = 1$: $2A + 3B = 1$ … (ii)
Substitute $A = -B$ into (ii): $-2B + 3B = 1$, so $B = 1$, $A = -1$.
Final solution: $\boxed{a_n = -2^n + 3^n = 3^n – 2^n}$
Verification: $a_0 = 1 – 1 = 0$ ✓, $a_1 = 3 – 2 = 1$ ✓, $a_2 = 9 – 4 = 5$ (check: $a_2 = 5(1) – 6(0) = 5$ ✓)
Question 11 (Workout): Solve $a_n – 4a_{n-1} + 4a_{n-2} = 0$ with $a_0 = 1$ and $a_1 = 4$.
Solution:
Step 1: Characteristic equation: $r^2 – 4r + 4 = 0$
Step 2: $(r-2)^2 = 0$, so $r = 2$ (repeated root). This is Case 2.
Step 3: General solution: $a_n = (A + Bn) \cdot 2^n$
Step 4: Initial conditions:
$n = 0$: $A \cdot 1 = 1$, so $A = 1$
$n = 1$: $(1 + B) \cdot 2 = 4$, so $1 + B = 2$, $B = 1$
Final solution: $\boxed{a_n = (1 + n) \cdot 2^n}$
Verification: $a_0 = 1$ ✓, $a_1 = 2 \cdot 2 = 4$ ✓, $a_2 = 3 \cdot 4 = 12$ (check: $a_2 = 4(4) – 4(1) = 12$ ✓)
Question 12 (MCQ): The characteristic equation of $a_n + 3a_{n-1} – 4a_{n-2} = 0$ 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: A
To get the characteristic equation, replace $a_n$ with $r^n$, $a_{n-1}$ with $r^{n-1}$, and $a_{n-2}$ with $r^{n-2}$:
$r^n + 3r^{n-1} – 4r^{n-2} = 0$
Divide by $r^{n-2}$: $r^2 + 3r – 4 = 0$
The key point: keep the same signs as in the original recurrence relation. Option A is correct.
Solving Non-Homogeneous Linear Recurrence Relations
A non-homogeneous linear recurrence relation with constant coefficients has the form:
where $f(n) \neq 0$. The key idea for solving these is:
$$a_n = a_n^{(h)} + a_n^{(p)}$$ where $a_n^{(h)}$ is the solution of the associated homogeneous equation (set $f(n) = 0$) and $a_n^{(p)}$ is any one specific solution of the non-homogeneous equation.
You already know how to find $a_n^{(h)}$ from the previous section. The new skill is finding $a_n^{(p)}$, the particular solution. Here is how to do it.
How to Find the Particular Solution $a_n^{(p)}$
The form of the particular solution depends on the form of $f(n)$. You make an educated guess based on what $f(n)$ looks like, then determine the unknown coefficients by substituting into the recurrence relation.
If $f(n) = C$ (a constant), try $a_n^{(p)} = K$ (a constant)
If $f(n) = C \cdot d^n$ and $d$ is NOT a root of the characteristic equation, try $a_n^{(p)} = K \cdot d^n$
If $f(n) = C \cdot d^n$ and $d$ IS a root of multiplicity $s$ of the characteristic equation, try $a_n^{(p)} = K \cdot n^s \cdot d^n$
If $f(n) = P(n)$ (a polynomial of degree $m$), and 1 is NOT a root, try $a_n^{(p)} = Q(n)$ (a polynomial of degree $m$)
If $f(n) = P(n) \cdot d^n$, try $a_n^{(p)} = Q(n) \cdot d^n$ where $Q$ has the same degree as $P$, multiplied by $n^s$ if $d$ is a root of multiplicity $s$.
Let me show you several examples.
Step 1: Find the homogeneous solution $a_n^{(h)}$.
Set $f(n) = 0$: $a_n – 5a_{n-1} + 6a_{n-2} = 0$
Characteristic equation: $r^2 – 5r + 6 = 0$, roots $r = 2, 3$
$a_n^{(h)} = A \cdot 2^n + B \cdot 3^n$
Step 2: Find the particular solution $a_n^{(p)}$.
Since $f(n) = 2n – 1$ is a polynomial of degree 1, and $r = 1$ is NOT a root of the characteristic equation, we try $a_n^{(p)} = Pn + Q$ (a polynomial of degree 1).
Substitute into the recurrence relation:
$(Pn + Q) – 5(P(n-1) + Q) + 6(P(n-2) + Q) = 2n – 1$
$Pn + Q – 5Pn + 5P – 5Q + 6Pn – 12P + 6Q = 2n – 1$
Collect like terms:
$n$ terms: $P – 5P + 6P = 2P$
Constant terms: $Q + 5P – 5Q – 12P + 6Q = 2Q – 7P$
So: $2P \cdot n + (2Q – 7P) = 2n – 1$
Equate coefficients:
$2P = 2 \Rightarrow P = 1$
$2Q – 7P = -1 \Rightarrow 2Q – 7 = -1 \Rightarrow 2Q = 6 \Rightarrow Q = 3$
$a_n^{(p)} = n + 3$
Step 3: Write the general solution.
$a_n = A \cdot 2^n + B \cdot 3^n + n + 3$
Step 4: Use initial conditions.
$n = 0$: $A + B + 3 = 1 \Rightarrow A + B = -2$ … (i)
$n = 1$: $2A + 3B + 1 + 3 = 2 \Rightarrow 2A + 3B = -2$ … (ii)
From (i): $A = -2 – B$. Substitute into (ii):
$2(-2 – B) + 3B = -2 \Rightarrow -4 – 2B + 3B = -2 \Rightarrow B = 2$
$A = -2 – 2 = -4$
Final solution: $\boxed{a_n = -4 \cdot 2^n + 2 \cdot 3^n + n + 3}$
Step 1: Homogeneous solution.
$r^2 – 3r + 2 = 0 \Rightarrow (r-1)(r-2) = 0 \Rightarrow r = 1, 2$
$a_n^{(h)} = A \cdot 1^n + B \cdot 2^n = A + B \cdot 2^n$
Step 2: Particular solution.
$f(n) = 3 \cdot 2^n$. Since $d = 2$ IS a root of the characteristic equation (with multiplicity 1), we must multiply our guess by $n^1$:
Try $a_n^{(p)} = K \cdot n \cdot 2^n$
Substitute into the recurrence:
$K n 2^n – 3K(n-1)2^{n-1} + 2K(n-2)2^{n-2} = 3 \cdot 2^n$
Divide by $2^{n-2}$:
$4Kn – 6K(n-1) + 2K(n-2) = 3 \cdot 4 = 12$
$4Kn – 6Kn + 6K + 2Kn – 4K = 12$
$(4K – 6K + 2K)n + (6K – 4K) = 12$
$0 \cdot n + 2K = 12 \Rightarrow K = 6$
$a_n^{(p)} = 6n \cdot 2^n$
Step 3: General solution.
$a_n = A + B \cdot 2^n + 6n \cdot 2^n = A + (B + 6n) \cdot 2^n$
Step 4: Initial conditions.
$n = 0$: $A + B = 0 \Rightarrow A = -B$ … (i)
$n = 1$: $A + (B + 6) \cdot 2 = 1 \Rightarrow A + 2B + 12 = 1 \Rightarrow A + 2B = -11$ … (ii)
Substitute $A = -B$: $-B + 2B = -11 \Rightarrow B = -11$, $A = 11$
Final solution: $\boxed{a_n = 11 + (-11 + 6n) \cdot 2^n = 11 + (6n – 11) \cdot 2^n}$
Step 1: Homogeneous: $r – 3 = 0 \Rightarrow r = 3$, so $a_n^{(h)} = A \cdot 3^n$
Step 2: $f(n) = 5$ (constant). Since $r = 1$ is NOT a root (root is 3), try $a_n^{(p)} = K$.
Substitute: $K – 3K = 5 \Rightarrow -2K = 5 \Rightarrow K = -\dfrac{5}{2}$
Step 3: $a_n = A \cdot 3^n – \dfrac{5}{2}$
Step 4: $n = 0$: $A – \dfrac{5}{2} = 2 \Rightarrow A = \dfrac{9}{2}$
Final solution: $\boxed{a_n = \dfrac{9}{2} \cdot 3^n – \dfrac{5}{2}}$
Verification: $a_0 = 4.5 – 2.5 = 2$ ✓, $a_1 = 13.5 – 2.5 = 11$ (check: $a_1 = 3(2) + 5 = 11$ ✓)
Step 1: Write the associated homogeneous equation and solve it → get $a_n^{(h)}$
Step 2: Look at $f(n)$ and choose the correct form for $a_n^{(p)}$
– If $f(n)$ matches a term in $a_n^{(h)}$, multiply by $n^s$
Step 3: Substitute $a_n^{(p)}$ into the ORIGINAL recurrence and solve for unknown coefficients
Step 4: General solution = $a_n^{(h)} + a_n^{(p)}$
Step 5: Use initial conditions to find remaining constants
Question 13 (Workout): Solve $a_n + a_{n-1} – 2a_{n-2} = 12$ with $a_0 = 0$ and $a_1 = 3$.
Solution:
Step 1: Homogeneous solution.
Characteristic equation: $r^2 + r – 2 = 0$
$(r+2)(r-1) = 0$, so $r_1 = -2$, $r_2 = 1$
$a_n^{(h)} = A(-2)^n + B(1)^n = A(-2)^n + B$
Step 2: Particular solution.
$f(n) = 12$ (constant). But $r = 1$ IS a root of the characteristic equation! So we must multiply by $n$:
Try $a_n^{(p)} = Kn$
Substitute: $Kn + K(n-1) – 2K(n-2) = 12$
$Kn + Kn – K – 2Kn + 4K = 12$
$(K + K – 2K)n + (-K + 4K) = 12$
$0 \cdot n + 3K = 12 \Rightarrow K = 4$
$a_n^{(p)} = 4n$
Step 3: $a_n = A(-2)^n + B + 4n$
Step 4: $n = 0$: $A + B = 0 \Rightarrow B = -A$ … (i)
$n = 1$: $A(-2) + B + 4 = 3 \Rightarrow -2A + B = -1$ … (ii)
Substitute $B = -A$: $-2A – A = -1 \Rightarrow -3A = -1 \Rightarrow A = \dfrac{1}{3}$, $B = -\dfrac{1}{3}$
Final solution: $\boxed{a_n = \dfrac{1}{3}(-2)^n – \dfrac{1}{3} + 4n}$
Question 14 (Workout): Solve $a_n – 4a_{n-1} + 4a_{n-2} = 8$ with $a_0 = 3$ and $a_1 = 6$.
Solution:
Step 1: Characteristic equation: $r^2 – 4r + 4 = 0 \Rightarrow (r-2)^2 = 0$, $r = 2$ (repeated)
$a_n^{(h)} = (A + Bn) \cdot 2^n$
Step 2: $f(n) = 8$ (constant). $r = 1$ is NOT a root (root is 2), so try $a_n^{(p)} = K$.
Substitute: $K – 4K + 4K = 8 \Rightarrow K = 8$
Step 3: $a_n = (A + Bn) \cdot 2^n + 8$
Step 4: $n = 0$: $A + 8 = 3 \Rightarrow A = -5$
$n = 1$: $(-5 + B) \cdot 2 + 8 = 6 \Rightarrow -10 + 2B + 8 = 6 \Rightarrow 2B = 8 \Rightarrow B = 4$
Final solution: $\boxed{a_n = (-5 + 4n) \cdot 2^n + 8}$
Verification: $a_0 = -5 + 8 = 3$ ✓, $a_1 = (-1) \cdot 2 + 8 = 6$ ✓, $a_2 = 3 \cdot 4 + 8 = 20$ (check: $a_2 = 4(6) – 4(3) + 8 = 24 – 12 + 8 = 20$ ✓)
Question 15 (MCQ): When solving $a_n – 2a_{n-1} = 3 \cdot 2^n$, the correct form to try for the particular solution is:
A) $K \cdot 2^n$ B) $K \cdot n \cdot 2^n$ C) $K \cdot n^2 \cdot 2^n$ D) $K \cdot 3^n$Answer: B
The homogeneous equation $a_n – 2a_{n-1} = 0$ has characteristic root $r = 2$. Since $f(n) = 3 \cdot 2^n$ uses the same base $d = 2$ which IS a root (multiplicity 1), we must multiply the usual guess $K \cdot 2^n$ by $n^1$. So the correct form is $K \cdot n \cdot 2^n$.
Solving Higher-Order Homogeneous Recurrence Relations
Sometimes you may encounter a third-order (or higher) recurrence relation. The method is the same as for second-order, but the characteristic equation is a higher-degree polynomial.
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.
Divide: $r^3 – 6r^2 + 11r – 6 = (r-1)(r^2 – 5r + 6) = (r-1)(r-2)(r-3) = 0$
Roots: $r_1 = 1$, $r_2 = 2$, $r_3 = 3$ (three distinct real roots)
Step 3: General solution:
Step 4: Initial conditions:
$n = 0$: $A + B + C = 0$ … (i)
$n = 1$: $A + 2B + 3C = 1$ … (ii)
$n = 2$: $A + 4B + 9C = 6$ … (iii)
(ii) – (i): $B + 2C = 1$ … (iv)
(iii) – (ii): $2B + 6C = 5$ … (v)
From (iv): $B = 1 – 2C$. Substitute into (v): $2(1-2C) + 6C = 5 \Rightarrow 2 – 4C + 6C = 5 \Rightarrow 2C = 3 \Rightarrow C = 3/2$
$B = 1 – 3 = -2$, $A = 0 – (-2) – 3/2 = 2 – 3/2 = 1/2$
Final solution: $\boxed{a_n = \dfrac{1}{2} – 2 \cdot 2^n + \dfrac{3}{2} \cdot 3^n}$
Generating Functions for Solving Recurrence Relations
Generating functions provide another way to solve recurrence relations. This method is powerful and works well for many types of problems. Let me explain the idea simply.
A generating function for a sequence $\{a_0, a_1, a_2, \ldots\}$ is the infinite series:
Think of $G(x)$ as a “container” that holds all the information about the sequence. The coefficient of $x^n$ in $G(x)$ is exactly $a_n$. By manipulating $G(x)$ algebraically (adding, multiplying, shifting), we can often find a closed-form expression for it, and then read off the coefficients.
How to Use Generating Functions to Solve Recurrence Relations
The basic approach has these steps:
Let me show you with a detailed example.
Step 1: $G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$
Step 2: Multiply the recurrence by $x^n$ and sum from $n = 1$ to $\infty$:
$\sum_{n=1}^{\infty} a_n x^n = \sum_{n=1}^{\infty} 2a_{n-1} x^n + \sum_{n=1}^{\infty} x^n$
The left side is $G(x) – a_0 = G(x) – 1$.
For the first term on the right: $\sum_{n=1}^{\infty} 2a_{n-1} x^n = 2x \sum_{n=1}^{\infty} a_{n-1} x^{n-1} = 2x \sum_{m=0}^{\infty} a_m x^m = 2x G(x)$
For the second term: $\sum_{n=1}^{\infty} x^n = \dfrac{x}{1-x}$ (geometric series)
So: $G(x) – 1 = 2x G(x) + \dfrac{x}{1-x}$
Step 3: Solve for $G(x)$:
$G(x) – 2x G(x) = 1 + \dfrac{x}{1-x}$
$G(x)(1 – 2x) = \dfrac{1-x+x}{1-x} = \dfrac{1}{1-x}$
$G(x) = \dfrac{1}{(1-2x)(1-x)}$
Step 4: Use partial fractions. Write:
$\dfrac{1}{(1-2x)(1-x)} = \dfrac{A}{1-2x} + \dfrac{B}{1-x}$
$1 = A(1-x) + B(1-2x)$
$x = 0$: $A + B = 1$
$x = 1/2$: $A(1/2) = 1 \Rightarrow A = 2$, $B = -1$
$G(x) = \dfrac{2}{1-2x} – \dfrac{1}{1-x}$
Now expand using $\dfrac{1}{1-rx} = \sum_{n=0}^{\infty} r^n x^n$:
$G(x) = 2\sum_{n=0}^{\infty} 2^n x^n – \sum_{n=0}^{\infty} x^n = \sum_{n=0}^{\infty} (2^{n+1} – 1) x^n$
Therefore: $a_n = 2^{n+1} – 1$
Verification: $a_0 = 2 – 1 = 1$ ✓, $a_1 = 4 – 1 = 3$ (check: $a_1 = 2(1)+1 = 3$ ✓), $a_2 = 8 – 1 = 7$ (check: $a_2 = 2(3)+1 = 7$ ✓)
$\dfrac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots = \displaystyle\sum_{n=0}^{\infty} x^n$
$\dfrac{1}{1-ax} = 1 + ax + a^2 x^2 + \cdots = \displaystyle\sum_{n=0}^{\infty} a^n x^n$
$\dfrac{1}{(1-x)^2} = 1 + 2x + 3x^2 + \cdots = \displaystyle\sum_{n=0}^{\infty} (n+1) x^n$
$\dfrac{1}{(1-x)^k} = \displaystyle\sum_{n=0}^{\infty} \binom{n+k-1}{k-1} x^n$
$\dfrac{x}{(1-x)^2} = x + 2x^2 + 3x^3 + \cdots = \displaystyle\sum_{n=1}^{\infty} n x^n$
Question 16 (Workout): Find the generating function for the Fibonacci sequence defined by $a_n = a_{n-1} + a_{n-2}$ for $n \geq 2$, with $a_0 = 0$ and $a_1 = 1$. Then find the closed-form formula for $a_n$.
Solution:
Step 1: $G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots = 0 + x + a_2 x^2 + a_3 x^3 + \cdots$
Step 2: Multiply by $x^n$ and sum from $n = 2$ to $\infty$:
$\sum_{n=2}^{\infty} a_n x^n = \sum_{n=2}^{\infty} a_{n-1} x^n + \sum_{n=2}^{\infty} a_{n-2} x^n$
Left side: $G(x) – a_0 – a_1 x = G(x) – x$
First right term: $x \sum_{n=2}^{\infty} a_{n-1} x^{n-1} = x(G(x) – a_0) = xG(x)$
Second right term: $x^2 \sum_{n=2}^{\infty} a_{n-2} x^{n-2} = x^2 G(x)$
So: $G(x) – x = xG(x) + x^2 G(x)$
Step 3: $G(x)(1 – x – x^2) = x$
Step 4: Factor $1 – x – x^2$. The roots of $r^2 – r – 1 = 0$ are $r = \dfrac{1 \pm \sqrt{5}}{2}$. So:
$1 – x – x^2 = -\left(x – \dfrac{1+\sqrt{5}}{2}\right)\left(x – \dfrac{1-\sqrt{5}}{2}\right) = -(x – \phi)(x + \hat\phi)$
where $\phi = \dfrac{1+\sqrt{5}}{2}$ (the golden ratio) and $\hat\phi = \dfrac{\sqrt{5}-1}{2} = \phi – 1 = \dfrac{1}{\phi}$.
After partial fractions and expansion (the algebra is lengthy), we get:
This is the famous Binet’s formula for the Fibonacci sequence.
Question 17 (MCQ): The generating function for the sequence $\{1, 1, 1, 1, \ldots\}$ is:
A) $\dfrac{x}{1-x}$ B) $\dfrac{1}{1-x}$ C) $\dfrac{1}{1+x}$ D) $1 + x + x^2$Answer: B
$G(x) = 1 + x + x^2 + x^3 + \cdots = \dfrac{1}{1-x}$ by the geometric series formula. This is the most basic generating function and you should know it by heart.
Exam Tips for Recurrence Relations
Dear students, here are my top tips to help you score well on your exam. I have seen many students make the same mistakes, so please read these carefully.
The most common mistake is getting the signs wrong. If the recurrence is $a_n – 5a_{n-1} + 6a_{n-2} = 0$, then the characteristic equation is $r^2 – 5r + 6 = 0$ — same signs! Do not change the signs.
A recurrence relation of order $k$ needs exactly $k$ initial conditions. If it is second-order, you need $a_0$ and $a_1$. If you are only given one initial condition, you cannot find unique values for both $A$ and $B$.
Before writing the general solution, always check if the discriminant is zero. If $c_1^2 – 4c_2 = 0$, you have a repeated root and must use $(A + Bn) r^n$, NOT $Ar^n + Br^n$. This is a very common exam trap.
If $f(n) = C \cdot d^n$ and $d$ is a root of the characteristic equation, you MUST multiply by $n$. Students often forget this and lose easy marks.
After finding the closed-form formula, plug in $n = 0$ and $n = 1$ to check against the initial conditions. Then compute one more term (like $a_2$) using both the recurrence and your formula to make sure they match. This takes only 1 minute and can save you many marks.
Always define your variable first. Then think: “How can I build an object of size $n$ from smaller objects?” Use case analysis based on the first element.
Memorize the forms for particular solutions: constant $f(n) \to$ constant guess, $C \cdot d^n \to$ $K \cdot d^n$ (or times $n$ if collision), polynomial $f(n) \to$ polynomial of same degree.
The recurrence $a_n = a_{n-1} + a_{n-2}$ appears very often in various forms (bit strings, climbing stairs, tilings). Practice these word problems until you can set up the recurrence relation quickly.
Practice Questions
Try these questions to test your understanding. Some are straightforward and some are more challenging. Good luck!
Practice 1: Find a recurrence relation and initial conditions for the number of ways to arrange $n$ people in a line if each person can be either facing forward or backward, but no two adjacent people can both be facing backward.
Solution: Let $a_n$ be the number of valid arrangements of $n$ people.
Case 1: The $n$-th person faces forward. Then the first $n-1$ people can be arranged in any valid way: $a_{n-1}$ ways.
Case 2: The $n$-th person faces backward. Then the $(n-1)$-th person MUST face forward. The first $n-2$ people can be arranged in any valid way: $a_{n-2}$ ways.
This is the same recurrence as the bit strings problem!
Practice 2: Solve $a_n – 7a_{n-1} + 12a_{n-2} = 0$ with $a_0 = 2$ and $a_1 = 7$.
Solution:
Characteristic equation: $r^2 – 7r + 12 = 0 \Rightarrow (r-3)(r-4) = 0 \Rightarrow r = 3, 4$
General solution: $a_n = A \cdot 3^n + B \cdot 4^n$
$n = 0$: $A + B = 2$ … (i)
$n = 1$: $3A + 4B = 7$ … (ii)
From (i): $A = 2 – B$. Sub into (ii): $3(2-B) + 4B = 7 \Rightarrow 6 – 3B + 4B = 7 \Rightarrow B = 1$, $A = 1$
Answer: $\boxed{a_n = 3^n + 4^n}$
Practice 3: Solve $a_n – 6a_{n-1} + 9a_{n-2} = 4 \cdot 3^n$ with $a_0 = 1$ and $a_1 = 4$.
Solution:
Homogeneous: $r^2 – 6r + 9 = 0 \Rightarrow (r-3)^2 = 0$, repeated root $r = 3$
$a_n^{(h)} = (A + Bn) \cdot 3^n$
Particular: $f(n) = 4 \cdot 3^n$. Since $r = 3$ is a root of multiplicity 2, multiply by $n^2$:
Try $a_n^{(p)} = K \cdot n^2 \cdot 3^n$
Substitute into the recurrence (dividing by $3^{n-2}$ after substitution):
$9Kn^2 – 6 \cdot 3K(n-1)^2 + 9K(n-2)^2 = 4 \cdot 9 = 36$
$9Kn^2 – 18K(n^2 – 2n + 1) + 9K(n^2 – 4n + 4) = 36$
$9Kn^2 – 18Kn^2 + 36Kn – 18K + 9Kn^2 – 36Kn + 36K = 36$
$(9K – 18K + 9K)n^2 + (36K – 36K)n + (-18K + 36K) = 36$
$0 + 0 + 18K = 36 \Rightarrow K = 2$
$a_n^{(p)} = 2n^2 \cdot 3^n$
General: $a_n = (A + Bn) \cdot 3^n + 2n^2 \cdot 3^n = (A + Bn + 2n^2) \cdot 3^n$
Initial conditions:
$n = 0$: $A = 1$
$n = 1$: $(1 + B + 2) \cdot 3 = 4 \Rightarrow 3(3 + B) = 4 \Rightarrow 9 + 3B = 4 \Rightarrow 3B = -5 \Rightarrow B = -5/3$
Answer: $\boxed{a_n = \left(1 – \dfrac{5}{3}n + 2n^2\right) \cdot 3^n}$
Practice 4: A person deposits 5,000 birr in a bank that pays 8% interest per year, compounded annually. They also add 1,000 birr at the end of each year. Find a recurrence relation for the amount $A_n$ after $n$ years, and solve it.
Solution:
The amount after $n$ years equals the amount after $n-1$ years plus interest, plus the 1,000 birr deposit:
This is $a_n = c \cdot a_{n-1} + d$ with $c = 1.08$, $d = 1000$, $a_0 = 5000$.
Using the formula $a_n = a_0 \cdot c^n + d \cdot \dfrac{c^n – 1}{c – 1}$:
$A_n = 5000 \cdot (1.08)^n + 1000 \cdot \dfrac{(1.08)^n – 1}{1.08 – 1}$
$= 5000 \cdot (1.08)^n + 1000 \cdot \dfrac{(1.08)^n – 1}{0.08}$
$= 5000 \cdot (1.08)^n + 12500 \cdot ((1.08)^n – 1)$
$= 5000(1.08)^n + 12500(1.08)^n – 12500$
Answer: $\boxed{A_n = 17500 \cdot (1.08)^n – 12500}$
Practice 5: Find the generating function for the sequence defined by $a_n = 3a_{n-1}$ for $n \geq 1$, with $a_0 = 2$. Then use it to find $a_n$.
Solution:
$G(x) = \sum_{n=0}^{\infty} a_n x^n$
Multiply recurrence by $x^n$ and sum from $n=1$ to $\infty$:
$\sum_{n=1}^{\infty} a_n x^n = 3\sum_{n=1}^{\infty} a_{n-1} x^n$
$G(x) – a_0 = 3x G(x)$
$G(x) – 2 = 3x G(x)$
$G(x)(1 – 3x) = 2$
$G(x) = \dfrac{2}{1 – 3x} = 2 \sum_{n=0}^{\infty} (3x)^n = \sum_{n=0}^{\infty} 2 \cdot 3^n x^n$
Answer: $\boxed{a_n = 2 \cdot 3^n}$
This matches the direct solution: $a_n = a_0 \cdot 3^n = 2 \cdot 3^n$. ✓
Practice 6: Find a recurrence relation for the number of $n$-digit ternary sequences (using digits 0, 1, 2) that contain an even number of 0s.
Solution: Let $a_n$ be the number of $n$-digit ternary sequences with an even number of 0s.
Case 1: The sequence starts with 1 or 2. There are 2 choices for the first digit, and the remaining $n-1$ digits must have an even number of 0s: $2a_{n-1}$ ways.
Case 2: The sequence starts with 0. Then the remaining $n-1$ digits must have an odd number of 0s. The total number of $(n-1)$-digit sequences is $3^{n-1}$, and the number with even 0s is $a_{n-1}$. So the number with odd 0s is $3^{n-1} – a_{n-1}$.
This is a first-order non-homogeneous recurrence that can be solved using the iteration method.
Practice 7 (MCQ): The closed-form solution of $a_n = a_{n-1} + a_{n-2}$ with $a_0 = 0$, $a_1 = 1$ at $n = 5$ is:
A) 3 B) 5 C) 8 D) 13Answer: B
This is the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, …
$a_0 = 0$, $a_1 = 1$, $a_2 = 1$, $a_3 = 2$, $a_4 = 3$, $a_5 = 5$
So $a_5 = 5$. Option B is correct.
Practice 8: Solve $a_n + 2a_{n-1} + a_{n-2} = 0$ with $a_0 = 1$ and $a_1 = 0$.
Solution:
Characteristic equation: $r^2 + 2r + 1 = 0 \Rightarrow (r+1)^2 = 0$, $r = -1$ (repeated)
General solution: $a_n = (A + Bn)(-1)^n$
$n = 0$: $A = 1$
$n = 1$: $(1 + B)(-1) = 0 \Rightarrow B = -1$
Answer: $\boxed{a_n = (1 – n)(-1)^n}$
Verification: $a_0 = 1$ ✓, $a_1 = 0$ ✓, $a_2 = (1-2)(1) = -1$ (check: $a_2 + 2a_1 + a_0 = -1 + 0 + 1 = 0$ ✓)