MATH 117 - ELEMENTS OF
MATHEMATICS - Homogeneous and
non-homogeneous recurrence relations
Question Bank - Set 4
Liberty University
Question 1
Question
Let anbe defined by the recurrence relation an+2 −4an+1 + 4an= 0 for n≥0
with initial conditions a0= 1 and a1= 2. Find a formula for anfor all n≥0.
Solution
Step 1: We first find the characteristic equation associated with the given re-
currence relation:
r2−4r+ 4 = 0
(r−2)2= 0
r= 2
Thus, the characteristic equation has a repeated root r= 2.
Step 2: The general solution to the homogeneous recurrence relation is then
of the form:
an=c1·2n+c2·n·2n
where c1and c2are constants to be determined.
Step 3: Using the initial conditions a0= 1 and a1= 2, we can set up the
following two equations:
a0=c1·20+c2·0·20=c1= 1
a1=c1·21+c2·1·21= 2c1+ 2c2= 2
Step 4: Solving the system of equations, we find c1= 1 and c2= 0. There-
fore, the formula for anis:
an= 2n
Question 2
Question
Consider a non-homogeneous linear recurrence relation of the form:
an= 2an−1−an−2+ 3n, a0= 1, a1= 2
Find a closed-form expression for anin terms of n.
Solution
To find a closed-form expression for an, we will first solve the associated homo-
geneous recurrence relation:
a(h)
n= 2a(h)
n−1−a(h)
n−2.
The characteristic equation for the homogeneous relation is r2= 2r−1,
which simplifies to r2−2r+ 1 = (r−1)2= 0. This yields a repeated root r= 1,
so the general form of a(h)
nis given by A·1n+B·n·1n=A+Bn.
Next, we assume anhas the form an=a(h)
n+a(p)
n, where a(p)
nis a particular
solution to the non-homogeneous recurrence:
a(p)
n=Akn.
Substitute an=Akninto the original recurrence relation to find k:
Akn= 2Akn−1−Akn−2+ 3n.
Dividing by kn−2, we get: k2= 2k−1 + 3
k2. Since we have a term 3n, we
set k= 3.
Therefore, a(p)
n=A·3nis a particular solution.
Now, we can express the general solution anin the form an=A+Bn+A′·3n.
Using the initial conditions a0= 1 and a1= 2, we can solve for A,B, and A′,
giving the closed-form expression for anin terms of n.
Question 3
Question
Let anbe a sequence defined by the recurrence relation:
an= 2an−1−an−2+ 2n
with initial conditions a0= 1 and a1= 3. Find a closed-form expression for an.
2
Solution
Step 1: Find the characteristic equation of the homogeneous part of the recur-
rence relation. This part is given by an= 2an−1−an−2.
The characteristic equation is r2= 2r−1 which simplifies to r2−2r+ 1 =
(r−1)2= 0. Thus, the characteristic root is r= 1.
Step 2: Write the general solution of the homogeneous part of the recurrence
relation.
Since the characteristic root is repeated, the general solution takes the form
a(h)
n= (c1+c2n)·1n=c1+c2n, where c1and c2are constants to be determined.
Step 3: Find a particular solution to the non-homogeneous part of the re-
currence relation. This part is 2n.
Since the non-homogeneous term 2nis a geometric progression, we guess
a particular solution of the form a(p)
n=c·2n, where cis a constant to be
determined.
Step 4: Substitute an=a(h)
n+a(p)
ninto the original recurrence relation and
solve for c.
Substituting into the original recurrence relation, we have:
(c1+c2n)+c·2n= 2((c1+c2(n−1))+c·2n−1)−((c1+c2(n−2))+c·2n−2)+2n
Step 5: Use the initial conditions a0= 1 and a1= 3 to solve for the constants
c1,c2, and c.
Given a0= 1 and a1= 3, we can solve for c1,c2, and cusing the expressions
for the general and particular solutions found in steps 2 and 3.
Step 6: Write the closed-form expression for an.
The closed-form expression for anis an=a(h)
n+a(p)
n. Substitute the values
of c1,c2, and cfound in step 5 to get the final expression.
Question 4
Question
Consider the following recurrence relation:
an= 5an−1−6an−2+ 2n
with initial conditions a0= 1 and a1= 4. Find the general solution to this
recurrence relation.
Solution
Step 1: First, we solve the associated homogeneous recurrence relation:
an= 5an−1−6an−2
The characteristic equation is r2−5r+6 = 0, which factors as (r−2)(r−3) =
0. Thus, the roots are r= 2 and r= 3.
3
So, the general solution to the homogeneous recurrence relation is:
a(h)
n=A(2n) + B(3n)
where Aand Bare constants to be determined.
Step 2: Next, we find a particular solution to the non-homogeneous recur-
rence relation an= 5an−1−6an−2+ 2n.
Since the non-homogeneity is 2n, we try a particular solution of the form
a(p)
n=c(2n). Substituting this into the recurrence relation, we get:
c(2n) = 5c(2n−1)−6c(2n−2)+2n
c=2n
2n+ 6(2n−1)−5(2n−2)
c=2n
2n(1 + 6(1/2) −5(1/4))
c=2n
2n(1 + 3 −5/4)
c=2n
2n(12 −5)/4
c=4
7
Therefore, a particular solution is a(p)
n=4
7(2n).
Step 3: The general solution to the non-homogeneous recurrence relation is
the sum of the general solution to the homogeneous recurrence relation and the
particular solution:
an=a(h)
n+a(p)
n=A(2n) + B(3n) + 4
7(2n)
Step 4: Using the initial conditions a0= 1 and a1= 4, we can solve for A
and B:
When n= 0: 1 = A+B+4
7
When n= 1: 4 = 2A+ 3B+8
7
Solving these simultaneous equations gives A=2
7and B=27
7.
Step 5: Thus, the general solution to the given recurrence relation is:
an=2
7(2n) + 27
7(3n) + 4
7(2n) = 6×2n+ 27 ×3n+ 4 ×2n
7
4
Question 5
Question
Let anbe a sequence defined by the recurrence relation
an= 5an−1−6an−2+ 2n
for n≥2, with initial conditions a0= 1 and a1= 2. Find a formula for anfor
all n≥0.
Solution
Step 1: First, we find the homogeneous solution of the recurrence relation.
We assume a(h)
n=rnand substitute it into the homogeneous version of the
recurrence relation:
an= 5an−1−6an−2
This gives us the characteristic equation:
rn= 5rn−1−6rn−2
Simplifying, we get:
r2−5r+ 6 = 0
This factors as (r−2)(r−3) = 0, so the characteristic roots are r1= 2 and
r2= 3. Therefore, the homogeneous solution is:
a(h)
n=A·2n+B·3n
Step 2: Next, we find a particular solution to the non-homogeneous recur-
rence relation. Here, the non-homogeneous term is 2n, so we try a particular
solution of the form a(p)
n=C·2n. Substituting this into the original recurrence
relation, we get:
C·2n= 5(C·2n−1)−6(C·2n−2)+2n
Solving for C, we find C=1
3. Therefore, the particular solution is:
a(p)
n=1
3·2n
Step 3: Thus, the general solution to the recurrence relation is the sum of
the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=A·2n+B·3n+1
3·2n
Using the initial conditions a0= 1 and a1= 2, we can solve for Aand B.
Substituting these values, we find A=−1
6and B=7
6. Therefore, the final
formula for anis:
an=−1
6·2n+7
6·3n+1
3·2n
5
Question 6
Question
Suppose we have a sequence defined by the recurrence relation: an= 3an−1+
4an−2for n≥2, with initial conditions a0= 1 and a1= 2. Find a general
formula for an.
Solution
Step 1: Finding the characteristic equation We assume an=rnand substitute
it into the recurrence relation to get:
rn= 3rn−1+ 4rn−2
Dividing by rn−2(since r= 0), we get:
r2= 3r+ 4
Step 2: Solving the characteristic equation This gives us the characteristic
equation:
r2−3r−4=0
Factoring the quadratic equation, we get (r−4)(r+ 1) = 0, so r= 4 or r=−1.
Step 3: Finding the general solution The general solution for the recurrence
relation is then:
an=Arn+Brm
where r= 4 and m=−1.
Step 4: Finding the constants Using the initial conditions a0= 1 and a1= 2,
we can solve for Aand B:
(a0=A+B= 1
a1= 4A−B= 2
Solving this system of equations gives A=2
3and B=1
3.
Step 5: Final formula for anThus, the general formula for anis:
an=2
3·4n+1
3·(−1)n
Question 7
Question
Consider the homogeneous recurrence relation: an= 2an−1−an−2with initial
conditions a0= 1 and a1= 3. Determine an explicit formula for the n-th term
of the sequence produced by this recurrence relation.
6
Solution
Step 1: Setting up the characteristic equation.
The characteristic equation for the given homogeneous recurrence relation is
r2= 2r−1. We can rewrite this as r2−2r+1 = 0, which factors as (r−1)2= 0.
Therefore, the characteristic equation has a repeated root of r= 1.
Step 2: Finding the general solution.
Since we have a repeated root of r= 1, the general solution to the homogeneous
recurrence relation is given by an= (A+Bn)(1)nwhere Aand Bare constants
to be determined.
Step 3: Applying the initial conditions.
Given that a0= 1 and a1= 3, we can substitute these values into the general
solution to find Aand B:
(a0=A·1 = A= 1
a1= (A+B)·1 = A+B= 3
From the first equation, we find A= 1. Substituting this into the second
equation gives 1 + B= 3, which implies B= 2.
Step 4: Final explicit formula.
Therefore, the explicit formula for the n-th term of the sequence is an= (1 +
2n)·1n= 1 + 2n.
Question 8
Question
Let anbe defined recursively by the recurrence relation:
an= 3an−1−2an−2+ 1
with initial conditions a0= 1 and a1= 2. Find a formula for anfor n≥2.
Solution
Step 1: First, we find the characteristic equation associated with the homoge-
neous part of the recurrence relation. The characteristic equation for anis:
λ2= 3λ−2
which simplifies to
λ2−3λ+ 2 = 0.
Step 2: Solve the characteristic equation λ2−3λ+ 2 = 0 by factoring:
(λ−1)(λ−2) = 0.
This gives us roots λ= 1 and λ= 2.
7
Step 3: The solution to the homogeneous part of the recurrence relation is
then
a(h)
n=c1·1n+c2·2n,
where c1and c2are constants to be determined.
Step 4: Next, we find the particular solution a(p)
nto the non-homogeneous
part of the recurrence relation. Since the non-homogeneous part is a constant,
we assume a(p)
n=Afor some constant A.
Step 5: Substitute a(p)
n=Ainto the original recurrence relation:
A= 3A−2A+ 1.
Step 6: Solve the equation A=A+ 1 to find the value of A. This yields
A= 1.
Step 7: The particular solution to the non-homogeneous part is a(p)
n= 1.
Step 8: The general solution to the recurrence relation is the sum of the
homogeneous and particular solutions:
an=a(h)
n+a(p)
n=c1·1n+c2·2n+ 1.
Step 9: Apply the initial conditions a0= 1 and a1= 2 to find the values of
c1and c2:
c1+c2+ 1 = 1,
c1·1 + c2·2 + 1 = 2.
Step 10: Solving the system of equations gives c1=−1 and c2= 1.
Step 11: Therefore, the formula for anfor n≥2 is:
an=−1·1n+ 1 ·2n+ 1.
Question 9
Question
Let anbe a sequence defined by the recurrence relation an= 5an−1−6an−2for
n≥2 with initial conditions a0= 2 and a1= 3. Find a closed-form expression
for an.
Solution
Step 1: Find the characteristic equation by assuming an=rn:
rn= 5rn−1−6rn−2
r2= 5r−6
r2−5r+ 6 = 0
(r−2)(r−3) = 0
8
r= 2,3
Step 2: The general solution is given by:
an=C1(2)n+C2(3)n
Step 3: Use the initial conditions to solve for C1and C2:
a0=2=C1+C2
a1= 3 = 2C1+ 3C2
Step 4: Solve the system of equations to find C1and C2:
(C1+C2= 2
2C1+ 3C2= 3
Step 5: The solution to the system is C1= 1 and C2= 1. Therefore, the
closed-form expression for anis:
an= 1 ·2n+ 1 ·3n
Question 10
Question
Let’s consider the following non-homogeneous recurrence relation:
an= 5an−1−6an−2+ 2n
Determine the particular solution for this recurrence relation.
Solution
To determine the particular solution for the non-homogeneous recurrence rela-
tion, we first need to find the general solution for the associated homogeneous
recurrence relation by setting the right-hand side to zero. Then we find a par-
ticular solution that satisfies the non-homogeneous term.
Step 1: Find the homogeneous solution. Assume an=rnfor some
constant r. Substitute this into the homogeneous recurrence relation an=
5an−1−6an−2to get:
rn= 5rn−1−6rn−2
Divide by rn−2:
r2= 5r−6
This is a quadratic equation with solutions r= 2 and r= 3. Therefore, the
homogeneous solution is:
a(h)
n=A·2n+B·3n
9
where Aand Bare constants to be determined.
Step 2: Find a particular solution. Guess a particular solution of the
form a(p)
n=C·2nwhere Cis a constant to be determined. Substitute this into
the non-homogeneous recurrence relation an= 5an−1−6an−2+ 2nto get:
C·2n= 5C·2n−1−6C·2n−2+ 2n
Simplify the equation:
C·2n= 5C·2n−3C·2n+ 2n
Solve for Cto get C=1
2. Therefore, the particular solution is:
a(p)
n=1
2·2n= 2n−1
Step 3: Determine the general solution. The general solution is the
sum of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=A·2n+B·3n+ 2n−1
Therefore, the particular solution for the non-homogeneous recurrence relation
is 2n−1.
Question 11
Question
Consider the non-homogeneous recurrence relation given by an= 3an−1−
2an−2+ 2nwith initial conditions a0= 1 and a1= 2. Find a closed-form
expression for an.
Solution
Step 1: First, we solve the associated homogeneous recurrence relation an−
3an−1+ 2an−2= 0. The characteristic equation is r2−3r+ 2 = 0, which factors
as (r−1)(r−2) = 0. So, the characteristic roots are r1= 1 and r2= 2.
Step 2: The general solution to the homogeneous part of the recurrence
relation is then a(h)
n=A(1)n+B(2)n, where Aand Bare constants to be
determined.
Step 3: Next, we find the particular solution to the non-homogeneous part.
Since the non-homogeneous term is of the form 2n, we guess a particular solution
of the form a(p)
n=C(2)n, where Cis a constant to be determined.
Step 4: Substituting the particular solution a(p)
n=C(2)ninto the original
non-homogeneous recurrence relation, we get:
C(2)n= 3(C(2)n−1)−2(C(2)n−2)+2n
10
Step 5: Dividing through by (2)n−2and simplifying, we find:
C= 3C−2C+ 22
C= 4
Step 6: Therefore, the particular solution is a(p)
n= 4(2)n.
Step 7: Finally, combining the particular and homogeneous solutions, we
have:
an=a(h)
n+a(p)
n=A(1)n+B(2)n+ 4(2)n
Step 8: Applying the initial conditions, a0= 1 and a1= 2, we can solve for
Aand B:
A+B+ 4 = 1
A(1) + B(2) + 4(2) = 2
Step 9: Solving this system of equations, we find A=−3 and B= 5.
Step 10: Therefore, the closed-form expression for anis:
an=−3(1)n+ 5(2)n+ 4(2)n=−3 + 9(2)n
Question 12
Question
Consider the non-homogeneous recurrence relation given by an= 2an−1−an−2+
2n. If a0= 1 and a1= 3, find a closed-form expression for an.
Solution
Step 1: Find the homogeneous solution We start by solving the correspond-
ing homogeneous recurrence relation an= 2an−1−an−2. The characteristic
equation is r2= 2r−1, which simplifies to r2−2r+ 1 = 0. This factors as
(r−1)2= 0, so the characteristic root is r= 1 with multiplicity 2. Hence, the
general homogeneous solution is a(h)
n=c1·1n+c2·n·1n=c1+c2n.
Step 2: Find the particular solution Now, we look for a particular solution
of the form a(p)
n=A2nto match the non-homogeneous term 2n. Substitute
this into the original non-homogeneous recurrence relation: A2n= 2 ·A2n−1−
A2n−2+ 2nDividing through by 2n, we get A= 2A−A+ 1, which gives A= 1.
Therefore, the particular solution is a(p)
n= 2n.
Step 3: Find the full solution The general solution of the non-homogeneous
recurrence relation is the sum of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=c1+c2n+ 2n.
Step 4: Use initial conditions to solve for constants Using the initial condi-
tions a0= 1 and a1= 3, we can find c1and c2: From a0= 1: c1+ 1 = 1 which
implies c1= 0. From a1= 3: 0 + 2 + 2 = 3 which implies c2= 1. Therefore,
the closed-form expression for anis an=n+ 2n.
11
Question 13
Question
Let ansatisfy the recurrence relation an= 2an−1+ 3n. If a0= 1, find a general
formula for an.
Solution
Step 1: First, we solve the corresponding homogeneous recurrence relation
an= 2an−1to find the general solution a(h)
n.
Since the homogeneous part is linear, we assume a solution of the form
a(h)
n=Crn, where Cis a constant to be determined.
Substitute a(h)
n=Crninto the homogeneous recurrence relation:
Crn= 2C(rn−1)
Divide both sides by Crn−1(assuming C= 0) to get:
r= 2
So, the general solution to the homogeneous recurrence relation is a(h)
n=
C·2n.
Step 2: Next, we find a particular solution a(p)
nto the non-homogeneous
recurrence relation an= 2an−1+ 3n.
Since 3nis a constant multiple of 3n, we try a particular solution of the form
a(p)
n=An3n, where Ais a constant to be determined.
Substitute a(p)
n=An3ninto the non-homogeneous recurrence relation:
An3n= 2A(n−1)3n−1+ 3n
Divide both sides by 3n(assuming 3n= 0) to get:
A=1
3
So, a particular solution is a(p)
n=1
3n3n=1
3n3n.
Step 3: The general solution to the original recurrence relation is the sum
of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=C·2n+1
3n3n
Step 4: Finally, we use the initial condition a0= 1 to find the value of the
constant C.
Substitute n= 0 and a0= 1 into the general solution:
1 = C·20+1
3·0·30
12
1 = C+ 0
C= 1
Thus, the general formula for anis:
an= 2n+1
3n3n
Question 14
Question
Consider the non-homogeneous linear recurrence relation given by:
an= 2an−1+ 3n, a0= 1
Find a closed-form expression for an.
Solution
To find a closed-form expression for an, we first need to solve the associated
homogeneous recurrence relation, then find a particular solution for the non-
homogeneous part, and finally combine both solutions using the principle of
superposition.
Step 1: Solve the homogeneous recurrence relation
The homogeneous recurrence relation is an= 2an−1. The characteristic
equation is r−2 = 0 which gives us r= 2.
So, the general solution to the homogeneous recurrence relation is a(h)
n=c·2n
where cis a constant to be determined.
Step 2: Find a particular solution for the non-homogeneous part
We will guess a particular solution in the form a(p)
n=b·3nwhere bis a
constant to be determined.
Substitute an=b·3ninto the non-homogeneous recurrence relation and
solve for b:
b·3n= 2(b·3n−1)+3n
b·3n= 2b·3n−1+ 3n
b=3n
3n−2·3n−1=1
1−2=−1
So, a particular solution to the non-homogeneous recurrence relation is
a(p)
n=−3n.
Step 3: Combine solutions using the principle of superposition
13
The general solution to the non-homogeneous recurrence relation is the sum
of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=c·2n−3n
Step 4: Find the value of cusing the initial condition a0= 1
Substitute n= 0 and a0= 1 into the general solution:
1 = c·20−30=c−1
c= 2
Step 5: Write the closed-form expression for an
Thus, the closed-form expression for anis:
an= 2 ·2n−3n= 2n+1 −3n
Question 15
Question
Let ansatisfy the recurrence relation an= 3an−1−2an−2for n≥2, with initial
conditions a0= 1 and a1= 3. Find a closed-form expression for an.
Solution
Step 1: First, let’s find the characteristic equation of the recurrence relation.
Assume a solution of the form an=rn. Substitute this into the recurrence
relation to get:
rn= 3rn−1−2rn−2
Step 2: Divide through by rn−2to simplify the equation:
r2= 3r−2
Step 3: Rearrange the equation to get the characteristic equation:
r2−3r+ 2 = 0
Step 4: Factor the quadratic to get:
(r−1)(r−2) = 0
Step 5: The roots of the characteristic equation are r= 1 and r= 2.
Therefore, the general solution of the recurrence relation is:
an=c1·1n+c2·2n
Step 6: To find c1and c2, use the initial conditions a0= 1 and a1= 3:
a0=c1·10+c2·20=c1= 1
14
a1=c1·11+c2·21=c1+ 2c2= 3
Step 7: Solve the system of equations to find c1and c2:
c1= 1
1+2c2= 3 ⇒2c2= 2 ⇒c2= 1
Step 8: Therefore, the closed-form expression for anis:
an= 1 + 2n
Question 16
Question
Let anbe defined by the recurrence relation an= 3an−1−2an−2for all integers
n≥2, with initial conditions a0= 1 and a1= 3. Determine a closed-form
expression for anfor all non-negative integers n.
Solution
Step 1: Find the characteristic equation for the given recurrence relation an=
3an−1−2an−2:
rn= 3rn−1−2rn−2
r2= 3r−2
r2−3r+ 2 = 0
Step 2: Solve the characteristic equation r2−3r+ 2 = 0: The characteristic
equation can be factored as (r−1)(r−2) = 0. Thus, the roots are r1= 1 and
r2= 2.
Step 3: Write the general form of the solution using the roots r1and r2:
an=c1·1n+c2·2n
an=c1+c2·2n
Step 4: Use the initial conditions a0= 1 and a1= 3 to solve for c1and c2:
From a0= 1:
a0=c1+c2·20=c1+c2= 1
From a1= 3:
a1=c1+c2·21=c1+ 2c2= 3
Step 5: Solve the system of equations to find c1and c2: Subtract the first
equation from the second equation:
c2= 2
15
Substitute c2= 2 back into the first equation:
c1+ 2 = 1 =⇒c1=−1
Step 6: Write the closed-form expression for anin terms of n: Thus, the
closed-form expression for anis:
an=−1+2·2n
Question 17
Question
Determine a closed-form expression for the sequence defined by the recurrence
relation:
an= 3an−1−2an−2+ 2nfor n≥2
given that a0= 1 and a1= 2.
Solution
We will begin by finding the characteristic equation of the homogeneous part of
the recurrence relation. Then we will find the particular solution for the non-
homogeneous part. Finally, we will combine the solutions to form the closed-
form expression for an.
Step 1: Find the characteristic equation
The characteristic equation for the homogeneous part of the recurrence re-
lation is given by:
rn= 3rn−1−2rn−2
Solving the characteristic equation gives us the roots r1= 2 and r2= 1.
Therefore, the homogeneous solution is of the form:
a(h)
n=c1·2n+c2·1n=c1·2n+c2
Step 2: Find the particular solution
In order to find the particular solution for the non-homogeneous part of
the recurrence relation, we will assume a solution of the form a(p)
n=A·2n.
Substituting this into the original recurrence relation, we obtain:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
Solving for A, we get A= 1. Therefore, the particular solution is a(p)
n= 2n.
Step 3: Form the closed-form expression
Since anis the sum of the homogeneous and particular solutions, we have:
16
an=a(h)
n+a(p)
n=c1·2n+c2+ 2n
Given a0= 1 and a1= 2, we can solve for c1and c2:
From a0:
1 = c1+c2+ 1
From a1:
2=2c1+c2+ 2
Solving these equations, we find c1= 0 and c2= 1.
Therefore, the closed-form expression for anis:
an= 1 + 2n
Question 18
Question
Consider the following non-homogeneous linear recurrence relation:
an= 2an−1−3an−2+n2+ 2n
with initial conditions a0= 1 and a1= 4. Find a closed-form expression for
an.
Solution
Step 1: Find the homogeneous solution by setting the non-homogeneous terms
to zero.
Setting n2= 0 and 2n= 0, we get the corresponding homogeneous recur-
rence relation:
an= 2an−1−3an−2
with characteristic equation r2= 2r−3, which factors to (r−3)(r+ 1) = 0.
Thus, the homogeneous solution is a(h)
n=c1·3n+c2·(−1)n.
Step 2: Find a particular solution for the non-homogeneous part.
Since the non-homogeneous terms are n2and 2n, we guess a particular so-
lution in the form:
a(p)
n=An2+B·2n
Substitute this back into the non-homogeneous recurrence relation to find
the values of Aand B.
An2+B·2n= 2(An2−2nA+B2n−1)−3(A(n−1)2−2(n−1)A+B2n−2)+n2+2n
17
Step 3: Solve for Aand B.
Expanding and simplifying the above equation, we get:
An2+B·2n= 2n2A+ 4B·2n−6nA −12B+n2+ 2n
Equating coefficients of n2and 2non both sides, we get the system of equa-
tions:
2A= 1 and 4B−6A= 0
Solving this system, we find A=1
2and B=3
4.
Therefore, the particular solution is a(p)
n=1
2n2+3
4·2n.
Step 4: Find the general solution by combining the homogeneous and par-
ticular solutions.
The general solution is given by an=a(h)
n+a(p)
n=c1·3n+c2·(−1)n+
1
2n2+3
4·2n.
Step 5: Use the initial conditions to find c1and c2.
Using a0= 1 and a1= 4, we can solve for c1and c2.
Substitute n= 0 and n= 1 into the general solution and solve the resulting
system of equations:
c1+3
4= 1 and 3c1−c2+3
2= 4
Solving this system gives c1=1
4and c2=3
2.
Therefore, the closed-form expression for anis:
an=1
4·3n+3
2·(−1)n+1
2n2+3
4·2n
Question 19
Question
Let anbe the sequence defined by the recurrence relation an= 2an−1−2an−2+
2nwith initial conditions a0= 0 and a1= 1. Find a closed-form expression for
an.
Solution
Step 1: Finding the homogeneous solution We first find the solution to the
homogeneous recurrence relation an= 2an−1−2an−2by assuming an=rn,
giving us the characteristic equation r2= 2r−2. Solving for rgives us r= 1
and r=−2, so the general solution to the homogeneous recurrence relation is
a(h)
n=c1·2n+c2·(−1)n.
Step 2: Finding a particular solution Next, we look for a particular solution
to the non-homogeneous recurrence relation an= 2an−1−2an−2+ 2n. Since
the non-homogeneous part is 2n, we try the particular solution a(p)
n=A·2n.
Substituting this into the recurrence relation, we get:
A·2n= 2(A·2n−1)−2(A·2n−2)+2n
18
A= 2A−A+ 1
A= 1
Therefore, a particular solution is a(p)
n= 2n.
Step 3: Combining solutions The general solution to the non-homogeneous
recurrence relation an= 2an−1−2an−2+2nis the sum of the homogeneous and
particular solutions:
an=a(h)
n+a(p)
n=c1·2n+c2·(−1)n+ 2n
Step 4: Applying initial conditions Using the initial conditions a0= 0 and
a1= 1, we get the following system of equations:
c1+c2= 0
2c1−c2+ 2 = 1
Solving this system of equations, we find c1= 1 and c2=−1. Hence, the
closed-form expression for anis:
an= 2n+ (−1)n+1
Question 20
Question
Let anbe the sequence defined recursively by a0= 1, a1= 2, and an+2 =
3an+1 −2anfor all n≥0. Find an explicit formula for an.
Solution
Step 1: First, we find the characteristic equation by setting an+2 = 3an+1 −2an
equal to rn+2 = 3rn+1 −2rn, where we assume an=rnfor some constant r.
Substitute an=rninto the equation to get:
rn+2 = 3rn+1 −2rn.
Step 2: Divide through by rnto simplify the equation:
r2= 3r−2.
Step 3: Rearranging the terms gives us the characteristic equation:
r2−3r+ 2 = 0.
Step 4: Solve the characteristic equation by factoring:
(r−1)(r−2) = 0.
19
Step 5: The roots of the characteristic equation are r1= 1 and r2= 2.
Step 6: Hence, the general solution is of the form an=c1(1)n+c2(2)nfor
some constants c1and c2.
Step 7: Applying the initial conditions a0= 1 and a1= 2, we have:
a0=c1+c2= 1,
a1=c1+ 2c2= 2.
Step 8: Solving the system of equations gives c1= 0 and c2= 1.
Step 9: Therefore, the explicit formula for anis:
an= 2n.
Question 21
Question
Consider the non-homogeneous recurrence relation an= 5an−1−6an−2+ 3n
with initial conditions a0= 2 and a1= 3. Find a closed-form expression for an.
Solution
Step 1: First, find the homogeneous solution to the related homogeneous re-
currence relation an= 5an−1−6an−2. The characteristic equation for the
homogeneous relation is r2= 5r−6, which simplifies to r2−5r+ 6 = 0. This
factors into (r−2)(r−3) = 0, so the characteristic roots are r1= 2 and r2= 3.
Step 2: The general homogeneous solution is then given by a(h)
n=A·2n+
B·3n, where Aand Bare constants to be determined.
Step 3: Next, we need to find a particular solution to the non-homogeneous
recurrence relation. Since the non-homogeneous term is 3n, we try a particular
solution of the form a(p)
n=c·3n.
Step 4: Substitute a(p)
ninto the original recurrence relation to get c·3n=
5c·3n−1−6c·3n−2+ 3n.
Step 5: This simplifies to 3c= 5c+ 3 −2c+ 1 which gives c=−1.
Step 6: Combining the homogeneous and particular solutions, we have an=
A·2n+B·3n−3n.
Step 7: Using the initial conditions a0= 2 and a1= 3, we can solve for
Aand B. From a0= 2, we get A+B−1 = 2 and from a1= 3, we get
2A+ 3B−3 = 3.
Step 8: Solving these two equations simultaneously, we find A= 2 and
B= 1.
Therefore, the closed-form expression for anis an= 2 ·2n+ 1 ·3n−3n.
20
Question 22
Question
Let anbe a sequence defined by the recurrence relation an= 3an−1−2an−2for
n≥2, with initial conditions a0= 1 and a1= 2. Find a closed-form expression
for an.
Solution
Step 1: First, we find the characteristic equation of the homogeneous part of the
recurrence relation. The characteristic equation is obtained by setting an=rn:
rn= 3rn−1−2rn−2
Step 2: Dividing the equation by rn−2gives:
r2= 3r−2
Step 3: Rearranging the terms, we get:
r2−3r+ 2 = 0
Step 4: Solving the quadratic equation r2−3r+ 2 = 0 gives us the roots
r1= 1 and r2= 2.
Step 5: The general solution to the homogeneous part of the recurrence
relation is then:
an=c1·1n+c2·2n
Step 6: Using the initial conditions a0= 1 and a1= 2, we can solve for c1
and c2. Substituting n= 0 into the general form, we get:
a0=c1+c2·20=c1+c2= 1
Step 7: Substituting n= 1 into the general form, we get:
a1=c1·11+c2·21=c1+ 2c2= 2
Step 8: Solving the system of equations c1+c2= 1 and c1+ 2c2= 2 gives
us c1= 0 and c2= 1.
Step 9: Therefore, the closed-form expression for anis:
an= 0 ·1n+ 1 ·2n= 2n
Question 23
Question
Consider the recurrence relation an= 2an−1−an−2+ 2nwith initial conditions
a0= 1 and a1= 3. Find a formula for an.
21
Solution
To solve this recurrence relation, we first need to find the characteristic equa-
tion associated with the homogeneous part of the relation. The characteristic
equation is given by r2= 2r−1, which simplifies to r2−2r+1 = 0. This factors
to (r−1)2= 0, so we have a repeated root r= 1.
Step 1: To find the solution to the homogeneous part, we have the form
a(h)
n=c1·1n+c2·n·1n. This simplifies to a(h)
n=c1+c2·n.
Step 2: Next, we need to find a particular solution to the non-homogeneous
part. Since 2nis a geometric sequence, we can try the particular solution of the
form a(p)
n=An ·2n. Substituting this into the original recurrence relation, we
get:
An ·2n= 2(An −1·2n−1)−(An −2·2n−2)+2n
This simplifies to An = 2An −1−1
2An −2 + 1, which implies A=1
2.
Step 3: Therefore, the general solution to the recurrence relation is an=
a(h)
n+a(p)
n=c1+c2·n+1
2·n·2n.
Step 4: Finally, we use the initial conditions a0= 1 and a1= 3 to find the
values of c1and c2.
Substitute n= 0: c1+c2·0 + 1
2·0·20= 1 gives c1= 1.
Substitute n= 1: c1+c2·1 + 1
2·1·21= 3 gives c1+c2+ 1 = 3, 1 + c2= 2,
c2= 1.
Step 5: Therefore, the formula for anis an= 1 + n+1
2·n·2n.
Question 24
Question
Let anbe the sequence defined by the recurrence relation: an= 2an−1−an−2+n
for all integers n≥2 with initial conditions a0= 1 and a1= 3. Find a closed-
form expression for an.
Solution
Step 1: Find the characteristic equation by assuming the solution has the form
an=rnwhere ris a constant.
rn= 2rn−1−rn−2
Dividing by rn−2, we get:
r2= 2r−1
which simplifies to:
r2−2r+ 1 = (r−1)2= 0
Hence, we have a repeated root r= 1.
22
Step 2: Find the general solution using the repeated root. Assuming the
solution has the form an=c1·1n+c2·n·1nwhere c1and c2are constants.
an=c1+c2n
Step 3: Use the initial conditions to determine the values of c1and c2. Given
a0= 1 and a1= 3, we have:
(c1= 1
c1+c2= 3
Solving the system of equations, we find c1= 1 and c2= 2.
Step 4: Write the closed-form expression for an. Substitute c1= 1 and
c2= 2 back into the general solution:
an= 1 + 2n
Therefore, the closed-form expression for the sequence anis an= 1 + 2n.
Question 25
Question
Consider the non-homogeneous recurrence relation defined by an= 2an−1−
an−2+ 2nwith initial conditions a0= 0 and a1= 1. Find a closed-form
expression for anin terms of n.
Solution
To solve the non-homogeneous recurrence relation, we must first find the solu-
tion to the corresponding homogeneous recurrence relation. Then, we’ll find a
particular solution to the non-homogeneous recurrence relation.
Step 1: Find the homogeneous solution The homogeneous recurrence
relation is given by an= 2an−1−an−2.
Assume a solution of the form an=rn. Substituting this into the homoge-
neous recurrence relation, we get:
rn= 2rn−1−rn−2
Divide by rn−2to get the characteristic equation:
r2= 2r−1
r2−2r+ 1 = 0
(r−1)2= 0
r= 1
23
Therefore, the homogeneous solution is a(h)
n=c1·1n+c2·n·1n=c1+c2n,
where c1and c2are constants to be determined.
Step 2: Find a particular solution Now, let’s find a particular solution
to the non-homogeneous recurrence relation. Since the non-homogeneity is 2n,
a possible form for the particular solution is a(p)
n=k·2n, where kis a constant
to be determined.
Substitute this particular solution into the non-homogeneous recurrence re-
lation:
k·2n= 2(k·2n−1)−(k·2n−2)+2n
k·2n= 2k·2n−1−k·2n−2+ 2n
k= 2k−k
4+ 1
7k
4= 1
k=4
7
Therefore, the particular solution is a(p)
n=4
7·2n.
Step 3: Find the general solution The general solution to the non-
homogeneous recurrence relation is the sum of the homogeneous and particular
solutions:
an=a(h)
n+a(p)
n=c1+c2n+4
7·2n
Step 4: Find the constants using initial conditions Use the initial
conditions a0= 0 and a1= 1 to find the values of c1and c2:
c1+c2·0 + 4
7·20= 0
c1+4
7= 0
c1=−4
7
c1+c2·1 + 4
7·21= 1
−4
7+c2+8
7= 1
c2=3
7
Step 5: Write the closed-form expression Therefore, the closed-form
expression for anin terms of nis:
an=−4
7+3
7·n+4
7·2n
24
Question 26
Question
Consider the following non-homogeneous recurrence relation:
an= 2an−1−(n−1)2n+ 2n
Given that the particular solution for the non-homogeneous part of the recur-
rence relation is bn=n+ 2, find the closed-form solution for an.
Solution
To find the closed-form solution for an, we need to solve the non-homogeneous
recurrence relation using the particular solution bn=n+ 2.
Step 1: Write down the full recurrence relation:
an= 2an−1−(n−1)2n+ 2n
Step 2: Write down the particular solution:
bn=n+ 2
Step 3: Substitute the particular solution into the non-homogeneous recur-
rence relation:
an= 2an−1−(n−1)2n+ 2n
n+ 2 = 2(n−1 + 2) −(n−1)2n+ 2n
Step 4: Simplify the equation:
n+ 2 = 2n+ 2 −2+2n−2n+ 2n
n+ 2 = 6n−2n
Step 5: Solve for anby adding the general solution cnto the particular
solution bn:
an=bn+cn
Step 6: Plug the particular solution bn=n+ 2 back into the equation:
an=n+2+cn
Step 7: Substitute the simplified non-homogeneous recurrence relation into
the equation:
n+ 2 = 6n−2n+cn
Step 8: Solve for cn:
cn=−5n+ 2n+ 2
Step 9: Therefore, the closed-form solution for anis:
an=n−5n+ 2n+ 2
25
Question 27
Question
Consider the following non-homogeneous recurrence relation:
an= 3an−1−2an−2+ 2n
If the initial conditions are a0= 1 and a1= 2, find a formula for anfor
n≥2.
Solution
To solve this non-homogeneous recurrence relation, we will first find the general
solution to the corresponding homogeneous recurrence relation and then find a
particular solution to the non-homogeneous equation.
Step 1: Find the homogeneous solution
The homogeneous part of the recurrence relation is given by:
a(h)
n= 3a(h)
n−1−2a(h)
n−2
Let’s assume a(h)
n=rn:
rn= 3rn−1−2rn−2
Dividing by rn−2, we get:
r2= 3r−2
r2−3r+ 2 = 0
(r−1)(r−2) = 0
So the characteristic equation has roots r= 1 and r= 2. Therefore, the
homogeneous solution is:
a(h)
n=c1·1n+c2·2n
a(h)
n=c1+c2·2n
Step 2: Find the particular solution
For the particular solution, we assume a(p)
n=A·2n:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
A=1
2
So the particular solution is a(p)
n=1
2·2n= 2n−1.
Step 3: Find the general solution
26
The general solution to the non-homogeneous recurrence relation is the sum
of the homogeneous and particular solutions:
an=c1+c2·2n+ 2n−1
Step 4: Apply initial conditions
Using the initial conditions a0= 1 and a1= 2, we can find c1and c2:
a0=c1+c2= 1
a1=c1+ 2c2+ 1 = 2
Solving these equations, we find c1=1
2and c2=1
2. Therefore, the formula
for anfor n≥2 is:
an=1
2+1
2·2n+ 2n−1
Question 28
Question
Consider the following recurrence relation:
an= 4an−1−4an−2+ 2n
where a0= 1 and a1= 2. Find the explicit formula for an.
Solution
To find the explicit formula for an, we need to solve the given recurrence relation
using the method of characteristic roots.
Step 1: Assume the solution has the form an=rn. Substitute an=rninto
the recurrence relation:
rn= 4rn−1−4rn−2+ 2n
Step 2: Rewrite the relation by dividing by rn−2:
r2= 4r−4+22r2
r2−4r+ 4 = 0
(r−2)2= 0
r= 2
Step 3: The characteristic root r= 2 has multiplicity 2. So, the general
solution of the homogeneous part is:
an=c1·2n+c2·n·2n
27
Step 4: Next, we find the particular solution for the non-homogeneous part.
Since 2nis of the form pnwhere p= 2 is not equal to any characteristic root,
we assume a particular solution of the form:
a(p)
n=A·2n
Substitute a(p)
n=A·2nback into the original recurrence relation:
A·2n= 4(A·2n−1)−4(A·2n−2)+2n
A= 1
Step 5: Therefore, the explicit formula for anis the sum of the homogeneous
and particular solutions:
an=c1·2n+c2·n·2n+ 2n
Question 29
Question
Consider the following recurrence relation:
an+2 −5an+1 + 6an= 3n, a0= 1, a1= 2.
Find a formula for anfor n≥0.
Solution
Step 1: First, we need to find the characteristic equation by setting an=rnin
the homogeneous part of the equation:
r2−5r+ 6 = 0.
Factoring this quadratic equation, we get:
(r−2)(r−3) = 0.
So, the characteristic roots are r1= 2 and r2= 3.
Step 2: The general solution to the homogeneous part of the recurrence
relation is then:
an=c1·2n+c2·3n.
Step 3: Next, we need to find a particular solution to the non-homogeneous
part of the equation. Since 3nis a term in the non-homogeneous part, we can
guess a particular solution of the form an=An3n.
Step 4: Substituting an=An3ninto the original equation gives:
A(3n+2)−5A(3n+1)+6A(3n) = 3n.
28
3n+2A−5·3·3n+1A+ 6 ·3nA= 3n.
3n+2A−15 ·3n+1A+ 6 ·3nA= 3n.
3n(9A−15A+ 6A) = 3n.
Step 5: Simplifying the above equation leads to the solution A=1
9.
Step 6: Therefore, the particular solution is:
an=1
9·3n=1
9·3n.
Step 7: Putting it all together, the general solution to the recurrence relation
is:
an=c1·2n+c2·3n+1
9·3n.
Step 8: Finally, applying the initial conditions a0= 1 and a1= 2 allows us
to solve for c1and c2, and we find the final formula for an.
Question 30
Question
Find a closed-form solution to the following recurrence relation:
an= 3an−1−2an−2+ 2n,where a0= 1 and a1= 3.
Solution
To solve this non-homogeneous recurrence relation, we will first find the closed-
form solution to the corresponding homogeneous recurrence relation and then
use the method of undetermined coefficients to find a particular solution for the
non-homogeneous term.
Step 1: Find the characteristic equation for the homogeneous part.
The homogeneous recurrence relation is given by an= 3an−1−2an−2. Let’s
assume the solution has the form an=rn. Substituting this into the recurrence
relation, we get:
rn= 3rn−1−2rn−2.
Dividing by rn−2, we simplify to:
r2= 3r−2.
This gives us the characteristic equation r2−3r+ 2 = 0, which factors as
(r−1)(r−2) = 0. So, the characteristic roots are r= 1,2.
Step 2: Find the homogeneous solution. The general solution to the
homogeneous part is: a(h)
n=c1(1)n+c2(2)n, where c1and c2are constants to
be determined from the initial conditions.
29
Step 3: Find a particular solution for the non-homogeneous part.
To find a particular solution for the non-homogeneous term 2n, we assume a
solution of the form a(p)
n=An2n, where Ais a constant to be determined.
Substitute a(p)
ninto the recurrence relation:
An2n= 3(A(n−1)2n−1)−2(A(n−2)2n−2)+2n.
Dividing by 2nand simplifying, we get:
A=2
3.
So, a particular solution is a(p)
n=2
3n2n.
Step 4: Combine the homogeneous and particular solutions. The
general solution to the non-homogeneous recurrence relation is the sum of the
homogeneous and particular solutions:
an=a(h)
n+a(p)
n=c1+c2(2)n+2
3n2n.
Step 5: Use initial conditions to find c1and c2.Using the initial
conditions a0= 1 and a1= 3, we can find c1and c2:
a0=c1+c2= 1,
a1=c1+ 2c2(2) + 2
3·1·2 = 3.
Solving these equations simultaneously, we find c1=1
3and c2=2
3.
Step 6: Final solution. Therefore, the closed-form solution to the given
non-homogeneous recurrence relation is:
an=1
3+2
3(2)n+2
3n2n.
Question 31
Question
Let anbe a sequence defined by the recurrence relation an+2 −7an+1 +12an= 0
with initial conditions a0= 2 and a1= 3. Find a formula for anfor n≥0.
Solution
To solve the given recurrence relation, we first assume that the solution has the
form an=rnfor some constant r. Substituting this into the recurrence relation
gives us the characteristic equation r2−7r+ 12 = 0.
Step 1: Solve the characteristic equation r2−7r+ 12 = 0.
The characteristic equation factors as (r−3)(r−4) = 0, so the roots are
r= 3 and r= 4.
30
Step 2: Write the general solution in terms of r= 3 and r= 4.
Since the roots are distinct, the general solution to the recurrence relation
is given by an=A·3n+B·4n, where Aand Bare constants to be determined.
Step 3: Use the initial conditions a0= 2 and a1= 3 to find Aand B.
Substitute n= 0 into the formula and set a0= 2:
2 = A·30+B·40=A+B
Substitute n= 1 into the formula and set a1= 3:
3 = A·31+B·41= 3A+ 4B
Solving the system of equations, we find A= 1 and B= 1.
Step 4: Write the final formula for an.
Therefore, the formula for anis an= 3n+ 4nfor n≥0.
Question 32
Question
Let ansatisfy the non-homogeneous recurrence relation an= 3an−1−2an−2+2n
for n≥2, with initial conditions a0= 1 and a1= 2. Find a formula for anin
terms of nwithout using the characteristic roots method.
Solution
Step 1: Find the homogeneous solution of the recurrence relation. Assume
a(h)
nhas the form a(h)
n=rn. Substitute this into the homogeneous relation
an= 3an−1−2an−2to get rn= 3rn−1−2rn−2. Dividing by rn−2, we have
r2= 3r−2, which factors as (r−1)(r−2) = 0. This gives us r1= 1 and r2= 2.
Step 2: Find a particular solution for the non-homogeneous part. Since
2nis a power of 2, assume a particular solution of the form a(p)
n=A·2n.
Substitute this into the non-homogeneous relation an= 3an−1−2an−2+ 2nto
get A·2n= 3(A·2n−1)−2(A·2n−2) + 2n. This simplifies to A=2
3. Therefore,
a(p)
n=2
3·2n=2n+1
3.
Step 3: Write the general solution as a sum of the homogeneous and partic-
ular solutions. Therefore, the general solution is an=a(h)
n+a(p)
n=c1·1n+c2·
2n+2n+1
3. Using the initial conditions a0= 1 and a1= 2, we find c1+c2+2
3= 1
and c1+ 2c2+4
3= 2.
Step 4: Solve for c1and c2. Subtracting the first equation from the second,
we get c2=1
3. Substituting this back into the first equation, we find c1=1
3.
Therefore, the formula for anin terms of nis an=1
3+1
3·2n+2n+1
3.
31
Question 33
Question
Consider the homogeneous linear recurrence relation given by:
an= 2an−1−2an−2
with initial conditions a0= 0 and a1= 1. Let bnbe the non-homogeneous
linear recurrence relation defined by:
bn= 2an+ 3
Calculate the first four terms of the sequence defined by bn.
Solution
Step 1: Find the characteristic equation of the homogeneous recurrence relation:
The characteristic equation is obtained by setting each term equal to zero:
r2= 2r−2
r2−2r+ 2 = 0
Step 2: Solve the characteristic equation:
Using the quadratic formula r=−b±√b2−4ac
2a, we have:
r=2±p(−2)2−4∗1∗2
2∗1
r=2±√4−8
2
r=2±√−4
2
r=2±2i
2
r= 1 ±i
So, the characteristic roots are complex with r1= 1 + iand r2= 1 −i.
Step 3: Write the general solution of the homogeneous recurrence relation:
The general solution takes the form:
an=c1(1 + i)n+c2(1 −i)n
Step 4: Use the initial conditions to find c1and c2:
Given a0= 0 and a1= 1, we have:
32
a0=c1+c2= 0
a1=c1(1 + i) + c2(1 −i)=1
Solving these equations simultaneously, we find c1=1
2iand c2=−1
2i.
Step 5: Calculate the terms of the non-homogeneous sequence bn:
Now, we use the relation bn= 2an+ 3 and substitute the expression for an
into it:
bn= 2 1
2i(1 + i)n−1
2i(1 −i)n+ 3
Now, calculate the first four terms of the sequence bnusing n= 0,1,2,3.
Question 34
Question
Let anbe defined recursively by the recurrence relation an= 2an−1−3an−2with
initial conditions a0= 1 and a1= 4. Find a formula for anfor all non-negative
integers n.
Solution
Step 1: Finding the characteristic equation The characteristic equation for the
given recurrence relation is r2= 2r−3, which simplifies to r2−2r+ 3 = 0.
Step 2: Finding the roots of the characteristic equation Using the quadratic
formula, r=−(−2)±√(−2)2−4∗1∗3
2∗1, we get r=2±√4−12
2=2±√−8
2= 1 ±i√2.
Step 3: Forming the general solution Since the roots are complex, the general
solution to the recurrence relation is an=c1(1 + i√2)n+c2(1 −i√2)n.
Step 4: Applying the initial conditions Substitute a0= 1 and a1= 4 into
the general solution. a0=c1(1 + i√2)0+c2(1 −i√2)0=c1+c2= 1 — (1)
a1=c1(1 + i√2)1+c2(1 −i√2)1=c1(1 + i√2) + c2(1 −i√2) = 4 — (2)
Step 5: Solving the system of equations From equations (1) and (2), we have
the system: c1+c2= 1, c1(1 + i√2) + c2(1 −i√2) = 4.
Solving this system, we find c1=4−2i√2
2√2and c2=2i√2
2√2.
Step 6: Final formula for anSubstitute the values of c1and c2into the
general solution to get the final formula for an:an=4−2i√2
2√2(1 + i√2)n+
2i√2
2√2(1 −i√2)n.
33
Question 35
Question
Let (an)n≥0be a sequence defined by the recurrence relation an+2 = 2an+1 −3an
for n≥0 with initial conditions a0= 1 and a1=−1. Find a closed-form formula
for an.
Solution
Step 1: Find the characteristic equation by assuming the solution has the form
an=rn. The characteristic equation is given by r2= 2r−3. Simplifying, we
have r2−2r+ 3 = 0.
Step 2: Solve the characteristic equation to find the roots. Using the
quadratic formula, we find that the roots are r=2±√(−2)2−4(1)(3)
2(1) = 1 ±i√2.
Step 3: Write the general solution to the homogeneous recurrence relation.
Since the roots are complex, the general solution will be of the form
an=A(1 + i√2)n+B(1 −i√2)n,
where Aand Bare constants to be determined.
Step 4: Use the initial conditions to find the values of Aand B. From the
initial conditions a0= 1 and a1=−1, we have:
a0=A(1 + i√2)0+B(1 −i√2)0=A+B= 1,
a1=A(1 + i√2) + B(1 −i√2) = (A+B) + i√2A−i√2B=−1.
Step 5: Solve for Aand B. Solving the system of equations from Step 4, we
find A=1
2+i√2
2and B=1
2−i√2
2.
Step 6: Write the closed-form formula for an. Substitute the values of A
and Bback into the general solution to get the closed-form formula for an:
an= 1
2+i√2
2!(1 + i√2)n+ 1
2−i√2
2!(1 −i√2)n.
34
Question 2
Question
Consider a non-homogeneous linear recurrence relation of the form:
an= 2an−1−an−2+ 3n, a0= 1, a1= 2
Find a closed-form expression for anin terms of n.
Solution
To find a closed-form expression for an, we will first solve the associated homo-
geneous recurrence relation:
a(h)
n= 2a(h)
n−1−a(h)
n−2.
The characteristic equation for the homogeneous relation is r2= 2r−1,
which simplifies to r2−2r+ 1 = (r−1)2= 0. This yields a repeated root r= 1,
so the general form of a(h)
nis given by A·1n+B·n·1n=A+Bn.
Next, we assume anhas the form an=a(h)
n+a(p)
n, where a(p)
nis a particular
solution to the non-homogeneous recurrence:
a(p)
n=Akn.
Substitute an=Akninto the original recurrence relation to find k:
Akn= 2Akn−1−Akn−2+ 3n.
Dividing by kn−2, we get: k2= 2k−1 + 3
k2. Since we have a term 3n, we
set k= 3.
Therefore, a(p)
n=A·3nis a particular solution.
Now, we can express the general solution anin the form an=A+Bn+A′·3n.
Using the initial conditions a0= 1 and a1= 2, we can solve for A,B, and A′,
giving the closed-form expression for anin terms of n.
Question 3
Question
Let anbe a sequence defined by the recurrence relation:
an= 2an−1−an−2+ 2n
with initial conditions a0= 1 and a1= 3. Find a closed-form expression for an.
2
Solution
Step 1: Find the characteristic equation of the homogeneous part of the recur-
rence relation. This part is given by an= 2an−1−an−2.
The characteristic equation is r2= 2r−1 which simplifies to r2−2r+ 1 =
(r−1)2= 0. Thus, the characteristic root is r= 1.
Step 2: Write the general solution of the homogeneous part of the recurrence
relation.
Since the characteristic root is repeated, the general solution takes the form
a(h)
n= (c1+c2n)·1n=c1+c2n, where c1and c2are constants to be determined.
Step 3: Find a particular solution to the non-homogeneous part of the re-
currence relation. This part is 2n.
Since the non-homogeneous term 2nis a geometric progression, we guess
a particular solution of the form a(p)
n=c·2n, where cis a constant to be
determined.
Step 4: Substitute an=a(h)
n+a(p)
ninto the original recurrence relation and
solve for c.
Substituting into the original recurrence relation, we have:
(c1+c2n)+c·2n= 2((c1+c2(n−1))+c·2n−1)−((c1+c2(n−2))+c·2n−2)+2n
Step 5: Use the initial conditions a0= 1 and a1= 3 to solve for the constants
c1,c2, and c.
Given a0= 1 and a1= 3, we can solve for c1,c2, and cusing the expressions
for the general and particular solutions found in steps 2 and 3.
Step 6: Write the closed-form expression for an.
The closed-form expression for anis an=a(h)
n+a(p)
n. Substitute the values
of c1,c2, and cfound in step 5 to get the final expression.
Question 4
Question
Consider the following recurrence relation:
an= 5an−1−6an−2+ 2n
with initial conditions a0= 1 and a1= 4. Find the general solution to this
recurrence relation.
Solution
Step 1: First, we solve the associated homogeneous recurrence relation:
an= 5an−1−6an−2
The characteristic equation is r2−5r+6 = 0, which factors as (r−2)(r−3) =
0. Thus, the roots are r= 2 and r= 3.
3
So, the general solution to the homogeneous recurrence relation is:
a(h)
n=A(2n) + B(3n)
where Aand Bare constants to be determined.
Step 2: Next, we find a particular solution to the non-homogeneous recur-
rence relation an= 5an−1−6an−2+ 2n.
Since the non-homogeneity is 2n, we try a particular solution of the form
a(p)
n=c(2n). Substituting this into the recurrence relation, we get:
c(2n) = 5c(2n−1)−6c(2n−2)+2n
c=2n
2n+ 6(2n−1)−5(2n−2)
c=2n
2n(1 + 6(1/2) −5(1/4))
c=2n
2n(1 + 3 −5/4)
c=2n
2n(12 −5)/4
c=4
7
Therefore, a particular solution is a(p)
n=4
7(2n).
Step 3: The general solution to the non-homogeneous recurrence relation is
the sum of the general solution to the homogeneous recurrence relation and the
particular solution:
an=a(h)
n+a(p)
n=A(2n) + B(3n) + 4
7(2n)
Step 4: Using the initial conditions a0= 1 and a1= 4, we can solve for A
and B:
When n= 0: 1 = A+B+4
7
When n= 1: 4 = 2A+ 3B+8
7
Solving these simultaneous equations gives A=2
7and B=27
7.
Step 5: Thus, the general solution to the given recurrence relation is:
an=2
7(2n) + 27
7(3n) + 4
7(2n) = 6×2n+ 27 ×3n+ 4 ×2n
7
4
Question 5
Question
Let anbe a sequence defined by the recurrence relation
an= 5an−1−6an−2+ 2n
for n≥2, with initial conditions a0= 1 and a1= 2. Find a formula for anfor
all n≥0.
Solution
Step 1: First, we find the homogeneous solution of the recurrence relation.
We assume a(h)
n=rnand substitute it into the homogeneous version of the
recurrence relation:
an= 5an−1−6an−2
This gives us the characteristic equation:
rn= 5rn−1−6rn−2
Simplifying, we get:
r2−5r+ 6 = 0
This factors as (r−2)(r−3) = 0, so the characteristic roots are r1= 2 and
r2= 3. Therefore, the homogeneous solution is:
a(h)
n=A·2n+B·3n
Step 2: Next, we find a particular solution to the non-homogeneous recur-
rence relation. Here, the non-homogeneous term is 2n, so we try a particular
solution of the form a(p)
n=C·2n. Substituting this into the original recurrence
relation, we get:
C·2n= 5(C·2n−1)−6(C·2n−2)+2n
Solving for C, we find C=1
3. Therefore, the particular solution is:
a(p)
n=1
3·2n
Step 3: Thus, the general solution to the recurrence relation is the sum of
the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=A·2n+B·3n+1
3·2n
Using the initial conditions a0= 1 and a1= 2, we can solve for Aand B.
Substituting these values, we find A=−1
6and B=7
6. Therefore, the final
formula for anis:
an=−1
6·2n+7
6·3n+1
3·2n
5
Question 6
Question
Suppose we have a sequence defined by the recurrence relation: an= 3an−1+
4an−2for n≥2, with initial conditions a0= 1 and a1= 2. Find a general
formula for an.
Solution
Step 1: Finding the characteristic equation We assume an=rnand substitute
it into the recurrence relation to get:
rn= 3rn−1+ 4rn−2
Dividing by rn−2(since r= 0), we get:
r2= 3r+ 4
Step 2: Solving the characteristic equation This gives us the characteristic
equation:
r2−3r−4=0
Factoring the quadratic equation, we get (r−4)(r+ 1) = 0, so r= 4 or r=−1.
Step 3: Finding the general solution The general solution for the recurrence
relation is then:
an=Arn+Brm
where r= 4 and m=−1.
Step 4: Finding the constants Using the initial conditions a0= 1 and a1= 2,
we can solve for Aand B:
(a0=A+B= 1
a1= 4A−B= 2
Solving this system of equations gives A=2
3and B=1
3.
Step 5: Final formula for anThus, the general formula for anis:
an=2
3·4n+1
3·(−1)n
Question 7
Question
Consider the homogeneous recurrence relation: an= 2an−1−an−2with initial
conditions a0= 1 and a1= 3. Determine an explicit formula for the n-th term
of the sequence produced by this recurrence relation.
6
Solution
Step 1: Setting up the characteristic equation.
The characteristic equation for the given homogeneous recurrence relation is
r2= 2r−1. We can rewrite this as r2−2r+1 = 0, which factors as (r−1)2= 0.
Therefore, the characteristic equation has a repeated root of r= 1.
Step 2: Finding the general solution.
Since we have a repeated root of r= 1, the general solution to the homogeneous
recurrence relation is given by an= (A+Bn)(1)nwhere Aand Bare constants
to be determined.
Step 3: Applying the initial conditions.
Given that a0= 1 and a1= 3, we can substitute these values into the general
solution to find Aand B:
(a0=A·1 = A= 1
a1= (A+B)·1 = A+B= 3
From the first equation, we find A= 1. Substituting this into the second
equation gives 1 + B= 3, which implies B= 2.
Step 4: Final explicit formula.
Therefore, the explicit formula for the n-th term of the sequence is an= (1 +
2n)·1n= 1 + 2n.
Question 8
Question
Let anbe defined recursively by the recurrence relation:
an= 3an−1−2an−2+ 1
with initial conditions a0= 1 and a1= 2. Find a formula for anfor n≥2.
Solution
Step 1: First, we find the characteristic equation associated with the homoge-
neous part of the recurrence relation. The characteristic equation for anis:
λ2= 3λ−2
which simplifies to
λ2−3λ+ 2 = 0.
Step 2: Solve the characteristic equation λ2−3λ+ 2 = 0 by factoring:
(λ−1)(λ−2) = 0.
This gives us roots λ= 1 and λ= 2.
7
Step 3: The solution to the homogeneous part of the recurrence relation is
then
a(h)
n=c1·1n+c2·2n,
where c1and c2are constants to be determined.
Step 4: Next, we find the particular solution a(p)
nto the non-homogeneous
part of the recurrence relation. Since the non-homogeneous part is a constant,
we assume a(p)
n=Afor some constant A.
Step 5: Substitute a(p)
n=Ainto the original recurrence relation:
A= 3A−2A+ 1.
Step 6: Solve the equation A=A+ 1 to find the value of A. This yields
A= 1.
Step 7: The particular solution to the non-homogeneous part is a(p)
n= 1.
Step 8: The general solution to the recurrence relation is the sum of the
homogeneous and particular solutions:
an=a(h)
n+a(p)
n=c1·1n+c2·2n+ 1.
Step 9: Apply the initial conditions a0= 1 and a1= 2 to find the values of
c1and c2:
c1+c2+ 1 = 1,
c1·1 + c2·2 + 1 = 2.
Step 10: Solving the system of equations gives c1=−1 and c2= 1.
Step 11: Therefore, the formula for anfor n≥2 is:
an=−1·1n+ 1 ·2n+ 1.
Question 9
Question
Let anbe a sequence defined by the recurrence relation an= 5an−1−6an−2for
n≥2 with initial conditions a0= 2 and a1= 3. Find a closed-form expression
for an.
Solution
Step 1: Find the characteristic equation by assuming an=rn:
rn= 5rn−1−6rn−2
r2= 5r−6
r2−5r+ 6 = 0
(r−2)(r−3) = 0
8
r= 2,3
Step 2: The general solution is given by:
an=C1(2)n+C2(3)n
Step 3: Use the initial conditions to solve for C1and C2:
a0=2=C1+C2
a1= 3 = 2C1+ 3C2
Step 4: Solve the system of equations to find C1and C2:
(C1+C2= 2
2C1+ 3C2= 3
Step 5: The solution to the system is C1= 1 and C2= 1. Therefore, the
closed-form expression for anis:
an= 1 ·2n+ 1 ·3n
Question 10
Question
Let’s consider the following non-homogeneous recurrence relation:
an= 5an−1−6an−2+ 2n
Determine the particular solution for this recurrence relation.
Solution
To determine the particular solution for the non-homogeneous recurrence rela-
tion, we first need to find the general solution for the associated homogeneous
recurrence relation by setting the right-hand side to zero. Then we find a par-
ticular solution that satisfies the non-homogeneous term.
Step 1: Find the homogeneous solution. Assume an=rnfor some
constant r. Substitute this into the homogeneous recurrence relation an=
5an−1−6an−2to get:
rn= 5rn−1−6rn−2
Divide by rn−2:
r2= 5r−6
This is a quadratic equation with solutions r= 2 and r= 3. Therefore, the
homogeneous solution is:
a(h)
n=A·2n+B·3n
9
where Aand Bare constants to be determined.
Step 2: Find a particular solution. Guess a particular solution of the
form a(p)
n=C·2nwhere Cis a constant to be determined. Substitute this into
the non-homogeneous recurrence relation an= 5an−1−6an−2+ 2nto get:
C·2n= 5C·2n−1−6C·2n−2+ 2n
Simplify the equation:
C·2n= 5C·2n−3C·2n+ 2n
Solve for Cto get C=1
2. Therefore, the particular solution is:
a(p)
n=1
2·2n= 2n−1
Step 3: Determine the general solution. The general solution is the
sum of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=A·2n+B·3n+ 2n−1
Therefore, the particular solution for the non-homogeneous recurrence relation
is 2n−1.
Question 11
Question
Consider the non-homogeneous recurrence relation given by an= 3an−1−
2an−2+ 2nwith initial conditions a0= 1 and a1= 2. Find a closed-form
expression for an.
Solution
Step 1: First, we solve the associated homogeneous recurrence relation an−
3an−1+ 2an−2= 0. The characteristic equation is r2−3r+ 2 = 0, which factors
as (r−1)(r−2) = 0. So, the characteristic roots are r1= 1 and r2= 2.
Step 2: The general solution to the homogeneous part of the recurrence
relation is then a(h)
n=A(1)n+B(2)n, where Aand Bare constants to be
determined.
Step 3: Next, we find the particular solution to the non-homogeneous part.
Since the non-homogeneous term is of the form 2n, we guess a particular solution
of the form a(p)
n=C(2)n, where Cis a constant to be determined.
Step 4: Substituting the particular solution a(p)
n=C(2)ninto the original
non-homogeneous recurrence relation, we get:
C(2)n= 3(C(2)n−1)−2(C(2)n−2)+2n
10
Step 5: Dividing through by (2)n−2and simplifying, we find:
C= 3C−2C+ 22
C= 4
Step 6: Therefore, the particular solution is a(p)
n= 4(2)n.
Step 7: Finally, combining the particular and homogeneous solutions, we
have:
an=a(h)
n+a(p)
n=A(1)n+B(2)n+ 4(2)n
Step 8: Applying the initial conditions, a0= 1 and a1= 2, we can solve for
Aand B:
A+B+ 4 = 1
A(1) + B(2) + 4(2) = 2
Step 9: Solving this system of equations, we find A=−3 and B= 5.
Step 10: Therefore, the closed-form expression for anis:
an=−3(1)n+ 5(2)n+ 4(2)n=−3 + 9(2)n
Question 12
Question
Consider the non-homogeneous recurrence relation given by an= 2an−1−an−2+
2n. If a0= 1 and a1= 3, find a closed-form expression for an.
Solution
Step 1: Find the homogeneous solution We start by solving the correspond-
ing homogeneous recurrence relation an= 2an−1−an−2. The characteristic
equation is r2= 2r−1, which simplifies to r2−2r+ 1 = 0. This factors as
(r−1)2= 0, so the characteristic root is r= 1 with multiplicity 2. Hence, the
general homogeneous solution is a(h)
n=c1·1n+c2·n·1n=c1+c2n.
Step 2: Find the particular solution Now, we look for a particular solution
of the form a(p)
n=A2nto match the non-homogeneous term 2n. Substitute
this into the original non-homogeneous recurrence relation: A2n= 2 ·A2n−1−
A2n−2+ 2nDividing through by 2n, we get A= 2A−A+ 1, which gives A= 1.
Therefore, the particular solution is a(p)
n= 2n.
Step 3: Find the full solution The general solution of the non-homogeneous
recurrence relation is the sum of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=c1+c2n+ 2n.
Step 4: Use initial conditions to solve for constants Using the initial condi-
tions a0= 1 and a1= 3, we can find c1and c2: From a0= 1: c1+ 1 = 1 which
implies c1= 0. From a1= 3: 0 + 2 + 2 = 3 which implies c2= 1. Therefore,
the closed-form expression for anis an=n+ 2n.
11
Question 13
Question
Let ansatisfy the recurrence relation an= 2an−1+ 3n. If a0= 1, find a general
formula for an.
Solution
Step 1: First, we solve the corresponding homogeneous recurrence relation
an= 2an−1to find the general solution a(h)
n.
Since the homogeneous part is linear, we assume a solution of the form
a(h)
n=Crn, where Cis a constant to be determined.
Substitute a(h)
n=Crninto the homogeneous recurrence relation:
Crn= 2C(rn−1)
Divide both sides by Crn−1(assuming C= 0) to get:
r= 2
So, the general solution to the homogeneous recurrence relation is a(h)
n=
C·2n.
Step 2: Next, we find a particular solution a(p)
nto the non-homogeneous
recurrence relation an= 2an−1+ 3n.
Since 3nis a constant multiple of 3n, we try a particular solution of the form
a(p)
n=An3n, where Ais a constant to be determined.
Substitute a(p)
n=An3ninto the non-homogeneous recurrence relation:
An3n= 2A(n−1)3n−1+ 3n
Divide both sides by 3n(assuming 3n= 0) to get:
A=1
3
So, a particular solution is a(p)
n=1
3n3n=1
3n3n.
Step 3: The general solution to the original recurrence relation is the sum
of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=C·2n+1
3n3n
Step 4: Finally, we use the initial condition a0= 1 to find the value of the
constant C.
Substitute n= 0 and a0= 1 into the general solution:
1 = C·20+1
3·0·30
12
1 = C+ 0
C= 1
Thus, the general formula for anis:
an= 2n+1
3n3n
Question 14
Question
Consider the non-homogeneous linear recurrence relation given by:
an= 2an−1+ 3n, a0= 1
Find a closed-form expression for an.
Solution
To find a closed-form expression for an, we first need to solve the associated
homogeneous recurrence relation, then find a particular solution for the non-
homogeneous part, and finally combine both solutions using the principle of
superposition.
Step 1: Solve the homogeneous recurrence relation
The homogeneous recurrence relation is an= 2an−1. The characteristic
equation is r−2 = 0 which gives us r= 2.
So, the general solution to the homogeneous recurrence relation is a(h)
n=c·2n
where cis a constant to be determined.
Step 2: Find a particular solution for the non-homogeneous part
We will guess a particular solution in the form a(p)
n=b·3nwhere bis a
constant to be determined.
Substitute an=b·3ninto the non-homogeneous recurrence relation and
solve for b:
b·3n= 2(b·3n−1)+3n
b·3n= 2b·3n−1+ 3n
b=3n
3n−2·3n−1=1
1−2=−1
So, a particular solution to the non-homogeneous recurrence relation is
a(p)
n=−3n.
Step 3: Combine solutions using the principle of superposition
13
The general solution to the non-homogeneous recurrence relation is the sum
of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=c·2n−3n
Step 4: Find the value of cusing the initial condition a0= 1
Substitute n= 0 and a0= 1 into the general solution:
1 = c·20−30=c−1
c= 2
Step 5: Write the closed-form expression for an
Thus, the closed-form expression for anis:
an= 2 ·2n−3n= 2n+1 −3n
Question 15
Question
Let ansatisfy the recurrence relation an= 3an−1−2an−2for n≥2, with initial
conditions a0= 1 and a1= 3. Find a closed-form expression for an.
Solution
Step 1: First, let’s find the characteristic equation of the recurrence relation.
Assume a solution of the form an=rn. Substitute this into the recurrence
relation to get:
rn= 3rn−1−2rn−2
Step 2: Divide through by rn−2to simplify the equation:
r2= 3r−2
Step 3: Rearrange the equation to get the characteristic equation:
r2−3r+ 2 = 0
Step 4: Factor the quadratic to get:
(r−1)(r−2) = 0
Step 5: The roots of the characteristic equation are r= 1 and r= 2.
Therefore, the general solution of the recurrence relation is:
an=c1·1n+c2·2n
Step 6: To find c1and c2, use the initial conditions a0= 1 and a1= 3:
a0=c1·10+c2·20=c1= 1
14
a1=c1·11+c2·21=c1+ 2c2= 3
Step 7: Solve the system of equations to find c1and c2:
c1= 1
1+2c2= 3 ⇒2c2= 2 ⇒c2= 1
Step 8: Therefore, the closed-form expression for anis:
an= 1 + 2n
Question 16
Question
Let anbe defined by the recurrence relation an= 3an−1−2an−2for all integers
n≥2, with initial conditions a0= 1 and a1= 3. Determine a closed-form
expression for anfor all non-negative integers n.
Solution
Step 1: Find the characteristic equation for the given recurrence relation an=
3an−1−2an−2:
rn= 3rn−1−2rn−2
r2= 3r−2
r2−3r+ 2 = 0
Step 2: Solve the characteristic equation r2−3r+ 2 = 0: The characteristic
equation can be factored as (r−1)(r−2) = 0. Thus, the roots are r1= 1 and
r2= 2.
Step 3: Write the general form of the solution using the roots r1and r2:
an=c1·1n+c2·2n
an=c1+c2·2n
Step 4: Use the initial conditions a0= 1 and a1= 3 to solve for c1and c2:
From a0= 1:
a0=c1+c2·20=c1+c2= 1
From a1= 3:
a1=c1+c2·21=c1+ 2c2= 3
Step 5: Solve the system of equations to find c1and c2: Subtract the first
equation from the second equation:
c2= 2
15
Substitute c2= 2 back into the first equation:
c1+ 2 = 1 =⇒c1=−1
Step 6: Write the closed-form expression for anin terms of n: Thus, the
closed-form expression for anis:
an=−1+2·2n
Question 17
Question
Determine a closed-form expression for the sequence defined by the recurrence
relation:
an= 3an−1−2an−2+ 2nfor n≥2
given that a0= 1 and a1= 2.
Solution
We will begin by finding the characteristic equation of the homogeneous part of
the recurrence relation. Then we will find the particular solution for the non-
homogeneous part. Finally, we will combine the solutions to form the closed-
form expression for an.
Step 1: Find the characteristic equation
The characteristic equation for the homogeneous part of the recurrence re-
lation is given by:
rn= 3rn−1−2rn−2
Solving the characteristic equation gives us the roots r1= 2 and r2= 1.
Therefore, the homogeneous solution is of the form:
a(h)
n=c1·2n+c2·1n=c1·2n+c2
Step 2: Find the particular solution
In order to find the particular solution for the non-homogeneous part of
the recurrence relation, we will assume a solution of the form a(p)
n=A·2n.
Substituting this into the original recurrence relation, we obtain:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
Solving for A, we get A= 1. Therefore, the particular solution is a(p)
n= 2n.
Step 3: Form the closed-form expression
Since anis the sum of the homogeneous and particular solutions, we have:
16
an=a(h)
n+a(p)
n=c1·2n+c2+ 2n
Given a0= 1 and a1= 2, we can solve for c1and c2:
From a0:
1 = c1+c2+ 1
From a1:
2=2c1+c2+ 2
Solving these equations, we find c1= 0 and c2= 1.
Therefore, the closed-form expression for anis:
an= 1 + 2n
Question 18
Question
Consider the following non-homogeneous linear recurrence relation:
an= 2an−1−3an−2+n2+ 2n
with initial conditions a0= 1 and a1= 4. Find a closed-form expression for
an.
Solution
Step 1: Find the homogeneous solution by setting the non-homogeneous terms
to zero.
Setting n2= 0 and 2n= 0, we get the corresponding homogeneous recur-
rence relation:
an= 2an−1−3an−2
with characteristic equation r2= 2r−3, which factors to (r−3)(r+ 1) = 0.
Thus, the homogeneous solution is a(h)
n=c1·3n+c2·(−1)n.
Step 2: Find a particular solution for the non-homogeneous part.
Since the non-homogeneous terms are n2and 2n, we guess a particular so-
lution in the form:
a(p)
n=An2+B·2n
Substitute this back into the non-homogeneous recurrence relation to find
the values of Aand B.
An2+B·2n= 2(An2−2nA+B2n−1)−3(A(n−1)2−2(n−1)A+B2n−2)+n2+2n
17
Step 3: Solve for Aand B.
Expanding and simplifying the above equation, we get:
An2+B·2n= 2n2A+ 4B·2n−6nA −12B+n2+ 2n
Equating coefficients of n2and 2non both sides, we get the system of equa-
tions:
2A= 1 and 4B−6A= 0
Solving this system, we find A=1
2and B=3
4.
Therefore, the particular solution is a(p)
n=1
2n2+3
4·2n.
Step 4: Find the general solution by combining the homogeneous and par-
ticular solutions.
The general solution is given by an=a(h)
n+a(p)
n=c1·3n+c2·(−1)n+
1
2n2+3
4·2n.
Step 5: Use the initial conditions to find c1and c2.
Using a0= 1 and a1= 4, we can solve for c1and c2.
Substitute n= 0 and n= 1 into the general solution and solve the resulting
system of equations:
c1+3
4= 1 and 3c1−c2+3
2= 4
Solving this system gives c1=1
4and c2=3
2.
Therefore, the closed-form expression for anis:
an=1
4·3n+3
2·(−1)n+1
2n2+3
4·2n
Question 19
Question
Let anbe the sequence defined by the recurrence relation an= 2an−1−2an−2+
2nwith initial conditions a0= 0 and a1= 1. Find a closed-form expression for
an.
Solution
Step 1: Finding the homogeneous solution We first find the solution to the
homogeneous recurrence relation an= 2an−1−2an−2by assuming an=rn,
giving us the characteristic equation r2= 2r−2. Solving for rgives us r= 1
and r=−2, so the general solution to the homogeneous recurrence relation is
a(h)
n=c1·2n+c2·(−1)n.
Step 2: Finding a particular solution Next, we look for a particular solution
to the non-homogeneous recurrence relation an= 2an−1−2an−2+ 2n. Since
the non-homogeneous part is 2n, we try the particular solution a(p)
n=A·2n.
Substituting this into the recurrence relation, we get:
A·2n= 2(A·2n−1)−2(A·2n−2)+2n
18
A= 2A−A+ 1
A= 1
Therefore, a particular solution is a(p)
n= 2n.
Step 3: Combining solutions The general solution to the non-homogeneous
recurrence relation an= 2an−1−2an−2+2nis the sum of the homogeneous and
particular solutions:
an=a(h)
n+a(p)
n=c1·2n+c2·(−1)n+ 2n
Step 4: Applying initial conditions Using the initial conditions a0= 0 and
a1= 1, we get the following system of equations:
c1+c2= 0
2c1−c2+ 2 = 1
Solving this system of equations, we find c1= 1 and c2=−1. Hence, the
closed-form expression for anis:
an= 2n+ (−1)n+1
Question 20
Question
Let anbe the sequence defined recursively by a0= 1, a1= 2, and an+2 =
3an+1 −2anfor all n≥0. Find an explicit formula for an.
Solution
Step 1: First, we find the characteristic equation by setting an+2 = 3an+1 −2an
equal to rn+2 = 3rn+1 −2rn, where we assume an=rnfor some constant r.
Substitute an=rninto the equation to get:
rn+2 = 3rn+1 −2rn.
Step 2: Divide through by rnto simplify the equation:
r2= 3r−2.
Step 3: Rearranging the terms gives us the characteristic equation:
r2−3r+ 2 = 0.
Step 4: Solve the characteristic equation by factoring:
(r−1)(r−2) = 0.
19
Step 5: The roots of the characteristic equation are r1= 1 and r2= 2.
Step 6: Hence, the general solution is of the form an=c1(1)n+c2(2)nfor
some constants c1and c2.
Step 7: Applying the initial conditions a0= 1 and a1= 2, we have:
a0=c1+c2= 1,
a1=c1+ 2c2= 2.
Step 8: Solving the system of equations gives c1= 0 and c2= 1.
Step 9: Therefore, the explicit formula for anis:
an= 2n.
Question 21
Question
Consider the non-homogeneous recurrence relation an= 5an−1−6an−2+ 3n
with initial conditions a0= 2 and a1= 3. Find a closed-form expression for an.
Solution
Step 1: First, find the homogeneous solution to the related homogeneous re-
currence relation an= 5an−1−6an−2. The characteristic equation for the
homogeneous relation is r2= 5r−6, which simplifies to r2−5r+ 6 = 0. This
factors into (r−2)(r−3) = 0, so the characteristic roots are r1= 2 and r2= 3.
Step 2: The general homogeneous solution is then given by a(h)
n=A·2n+
B·3n, where Aand Bare constants to be determined.
Step 3: Next, we need to find a particular solution to the non-homogeneous
recurrence relation. Since the non-homogeneous term is 3n, we try a particular
solution of the form a(p)
n=c·3n.
Step 4: Substitute a(p)
ninto the original recurrence relation to get c·3n=
5c·3n−1−6c·3n−2+ 3n.
Step 5: This simplifies to 3c= 5c+ 3 −2c+ 1 which gives c=−1.
Step 6: Combining the homogeneous and particular solutions, we have an=
A·2n+B·3n−3n.
Step 7: Using the initial conditions a0= 2 and a1= 3, we can solve for
Aand B. From a0= 2, we get A+B−1 = 2 and from a1= 3, we get
2A+ 3B−3 = 3.
Step 8: Solving these two equations simultaneously, we find A= 2 and
B= 1.
Therefore, the closed-form expression for anis an= 2 ·2n+ 1 ·3n−3n.
20
Question 22
Question
Let anbe a sequence defined by the recurrence relation an= 3an−1−2an−2for
n≥2, with initial conditions a0= 1 and a1= 2. Find a closed-form expression
for an.
Solution
Step 1: First, we find the characteristic equation of the homogeneous part of the
recurrence relation. The characteristic equation is obtained by setting an=rn:
rn= 3rn−1−2rn−2
Step 2: Dividing the equation by rn−2gives:
r2= 3r−2
Step 3: Rearranging the terms, we get:
r2−3r+ 2 = 0
Step 4: Solving the quadratic equation r2−3r+ 2 = 0 gives us the roots
r1= 1 and r2= 2.
Step 5: The general solution to the homogeneous part of the recurrence
relation is then:
an=c1·1n+c2·2n
Step 6: Using the initial conditions a0= 1 and a1= 2, we can solve for c1
and c2. Substituting n= 0 into the general form, we get:
a0=c1+c2·20=c1+c2= 1
Step 7: Substituting n= 1 into the general form, we get:
a1=c1·11+c2·21=c1+ 2c2= 2
Step 8: Solving the system of equations c1+c2= 1 and c1+ 2c2= 2 gives
us c1= 0 and c2= 1.
Step 9: Therefore, the closed-form expression for anis:
an= 0 ·1n+ 1 ·2n= 2n
Question 23
Question
Consider the recurrence relation an= 2an−1−an−2+ 2nwith initial conditions
a0= 1 and a1= 3. Find a formula for an.
21
Solution
To solve this recurrence relation, we first need to find the characteristic equa-
tion associated with the homogeneous part of the relation. The characteristic
equation is given by r2= 2r−1, which simplifies to r2−2r+1 = 0. This factors
to (r−1)2= 0, so we have a repeated root r= 1.
Step 1: To find the solution to the homogeneous part, we have the form
a(h)
n=c1·1n+c2·n·1n. This simplifies to a(h)
n=c1+c2·n.
Step 2: Next, we need to find a particular solution to the non-homogeneous
part. Since 2nis a geometric sequence, we can try the particular solution of the
form a(p)
n=An ·2n. Substituting this into the original recurrence relation, we
get:
An ·2n= 2(An −1·2n−1)−(An −2·2n−2)+2n
This simplifies to An = 2An −1−1
2An −2 + 1, which implies A=1
2.
Step 3: Therefore, the general solution to the recurrence relation is an=
a(h)
n+a(p)
n=c1+c2·n+1
2·n·2n.
Step 4: Finally, we use the initial conditions a0= 1 and a1= 3 to find the
values of c1and c2.
Substitute n= 0: c1+c2·0 + 1
2·0·20= 1 gives c1= 1.
Substitute n= 1: c1+c2·1 + 1
2·1·21= 3 gives c1+c2+ 1 = 3, 1 + c2= 2,
c2= 1.
Step 5: Therefore, the formula for anis an= 1 + n+1
2·n·2n.
Question 24
Question
Let anbe the sequence defined by the recurrence relation: an= 2an−1−an−2+n
for all integers n≥2 with initial conditions a0= 1 and a1= 3. Find a closed-
form expression for an.
Solution
Step 1: Find the characteristic equation by assuming the solution has the form
an=rnwhere ris a constant.
rn= 2rn−1−rn−2
Dividing by rn−2, we get:
r2= 2r−1
which simplifies to:
r2−2r+ 1 = (r−1)2= 0
Hence, we have a repeated root r= 1.
22
Step 2: Find the general solution using the repeated root. Assuming the
solution has the form an=c1·1n+c2·n·1nwhere c1and c2are constants.
an=c1+c2n
Step 3: Use the initial conditions to determine the values of c1and c2. Given
a0= 1 and a1= 3, we have:
(c1= 1
c1+c2= 3
Solving the system of equations, we find c1= 1 and c2= 2.
Step 4: Write the closed-form expression for an. Substitute c1= 1 and
c2= 2 back into the general solution:
an= 1 + 2n
Therefore, the closed-form expression for the sequence anis an= 1 + 2n.
Question 25
Question
Consider the non-homogeneous recurrence relation defined by an= 2an−1−
an−2+ 2nwith initial conditions a0= 0 and a1= 1. Find a closed-form
expression for anin terms of n.
Solution
To solve the non-homogeneous recurrence relation, we must first find the solu-
tion to the corresponding homogeneous recurrence relation. Then, we’ll find a
particular solution to the non-homogeneous recurrence relation.
Step 1: Find the homogeneous solution The homogeneous recurrence
relation is given by an= 2an−1−an−2.
Assume a solution of the form an=rn. Substituting this into the homoge-
neous recurrence relation, we get:
rn= 2rn−1−rn−2
Divide by rn−2to get the characteristic equation:
r2= 2r−1
r2−2r+ 1 = 0
(r−1)2= 0
r= 1
23
Therefore, the homogeneous solution is a(h)
n=c1·1n+c2·n·1n=c1+c2n,
where c1and c2are constants to be determined.
Step 2: Find a particular solution Now, let’s find a particular solution
to the non-homogeneous recurrence relation. Since the non-homogeneity is 2n,
a possible form for the particular solution is a(p)
n=k·2n, where kis a constant
to be determined.
Substitute this particular solution into the non-homogeneous recurrence re-
lation:
k·2n= 2(k·2n−1)−(k·2n−2)+2n
k·2n= 2k·2n−1−k·2n−2+ 2n
k= 2k−k
4+ 1
7k
4= 1
k=4
7
Therefore, the particular solution is a(p)
n=4
7·2n.
Step 3: Find the general solution The general solution to the non-
homogeneous recurrence relation is the sum of the homogeneous and particular
solutions:
an=a(h)
n+a(p)
n=c1+c2n+4
7·2n
Step 4: Find the constants using initial conditions Use the initial
conditions a0= 0 and a1= 1 to find the values of c1and c2:
c1+c2·0 + 4
7·20= 0
c1+4
7= 0
c1=−4
7
c1+c2·1 + 4
7·21= 1
−4
7+c2+8
7= 1
c2=3
7
Step 5: Write the closed-form expression Therefore, the closed-form
expression for anin terms of nis:
an=−4
7+3
7·n+4
7·2n
24
Question 26
Question
Consider the following non-homogeneous recurrence relation:
an= 2an−1−(n−1)2n+ 2n
Given that the particular solution for the non-homogeneous part of the recur-
rence relation is bn=n+ 2, find the closed-form solution for an.
Solution
To find the closed-form solution for an, we need to solve the non-homogeneous
recurrence relation using the particular solution bn=n+ 2.
Step 1: Write down the full recurrence relation:
an= 2an−1−(n−1)2n+ 2n
Step 2: Write down the particular solution:
bn=n+ 2
Step 3: Substitute the particular solution into the non-homogeneous recur-
rence relation:
an= 2an−1−(n−1)2n+ 2n
n+ 2 = 2(n−1 + 2) −(n−1)2n+ 2n
Step 4: Simplify the equation:
n+ 2 = 2n+ 2 −2+2n−2n+ 2n
n+ 2 = 6n−2n
Step 5: Solve for anby adding the general solution cnto the particular
solution bn:
an=bn+cn
Step 6: Plug the particular solution bn=n+ 2 back into the equation:
an=n+2+cn
Step 7: Substitute the simplified non-homogeneous recurrence relation into
the equation:
n+ 2 = 6n−2n+cn
Step 8: Solve for cn:
cn=−5n+ 2n+ 2
Step 9: Therefore, the closed-form solution for anis:
an=n−5n+ 2n+ 2
25
Question 27
Question
Consider the following non-homogeneous recurrence relation:
an= 3an−1−2an−2+ 2n
If the initial conditions are a0= 1 and a1= 2, find a formula for anfor
n≥2.
Solution
To solve this non-homogeneous recurrence relation, we will first find the general
solution to the corresponding homogeneous recurrence relation and then find a
particular solution to the non-homogeneous equation.
Step 1: Find the homogeneous solution
The homogeneous part of the recurrence relation is given by:
a(h)
n= 3a(h)
n−1−2a(h)
n−2
Let’s assume a(h)
n=rn:
rn= 3rn−1−2rn−2
Dividing by rn−2, we get:
r2= 3r−2
r2−3r+ 2 = 0
(r−1)(r−2) = 0
So the characteristic equation has roots r= 1 and r= 2. Therefore, the
homogeneous solution is:
a(h)
n=c1·1n+c2·2n
a(h)
n=c1+c2·2n
Step 2: Find the particular solution
For the particular solution, we assume a(p)
n=A·2n:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
A=1
2
So the particular solution is a(p)
n=1
2·2n= 2n−1.
Step 3: Find the general solution
26
The general solution to the non-homogeneous recurrence relation is the sum
of the homogeneous and particular solutions:
an=c1+c2·2n+ 2n−1
Step 4: Apply initial conditions
Using the initial conditions a0= 1 and a1= 2, we can find c1and c2:
a0=c1+c2= 1
a1=c1+ 2c2+ 1 = 2
Solving these equations, we find c1=1
2and c2=1
2. Therefore, the formula
for anfor n≥2 is:
an=1
2+1
2·2n+ 2n−1
Question 28
Question
Consider the following recurrence relation:
an= 4an−1−4an−2+ 2n
where a0= 1 and a1= 2. Find the explicit formula for an.
Solution
To find the explicit formula for an, we need to solve the given recurrence relation
using the method of characteristic roots.
Step 1: Assume the solution has the form an=rn. Substitute an=rninto
the recurrence relation:
rn= 4rn−1−4rn−2+ 2n
Step 2: Rewrite the relation by dividing by rn−2:
r2= 4r−4+22r2
r2−4r+ 4 = 0
(r−2)2= 0
r= 2
Step 3: The characteristic root r= 2 has multiplicity 2. So, the general
solution of the homogeneous part is:
an=c1·2n+c2·n·2n
27
Step 4: Next, we find the particular solution for the non-homogeneous part.
Since 2nis of the form pnwhere p= 2 is not equal to any characteristic root,
we assume a particular solution of the form:
a(p)
n=A·2n
Substitute a(p)
n=A·2nback into the original recurrence relation:
A·2n= 4(A·2n−1)−4(A·2n−2)+2n
A= 1
Step 5: Therefore, the explicit formula for anis the sum of the homogeneous
and particular solutions:
an=c1·2n+c2·n·2n+ 2n
Question 29
Question
Consider the following recurrence relation:
an+2 −5an+1 + 6an= 3n, a0= 1, a1= 2.
Find a formula for anfor n≥0.
Solution
Step 1: First, we need to find the characteristic equation by setting an=rnin
the homogeneous part of the equation:
r2−5r+ 6 = 0.
Factoring this quadratic equation, we get:
(r−2)(r−3) = 0.
So, the characteristic roots are r1= 2 and r2= 3.
Step 2: The general solution to the homogeneous part of the recurrence
relation is then:
an=c1·2n+c2·3n.
Step 3: Next, we need to find a particular solution to the non-homogeneous
part of the equation. Since 3nis a term in the non-homogeneous part, we can
guess a particular solution of the form an=An3n.
Step 4: Substituting an=An3ninto the original equation gives:
A(3n+2)−5A(3n+1)+6A(3n) = 3n.
28
3n+2A−5·3·3n+1A+ 6 ·3nA= 3n.
3n+2A−15 ·3n+1A+ 6 ·3nA= 3n.
3n(9A−15A+ 6A) = 3n.
Step 5: Simplifying the above equation leads to the solution A=1
9.
Step 6: Therefore, the particular solution is:
an=1
9·3n=1
9·3n.
Step 7: Putting it all together, the general solution to the recurrence relation
is:
an=c1·2n+c2·3n+1
9·3n.
Step 8: Finally, applying the initial conditions a0= 1 and a1= 2 allows us
to solve for c1and c2, and we find the final formula for an.
Question 30
Question
Find a closed-form solution to the following recurrence relation:
an= 3an−1−2an−2+ 2n,where a0= 1 and a1= 3.
Solution
To solve this non-homogeneous recurrence relation, we will first find the closed-
form solution to the corresponding homogeneous recurrence relation and then
use the method of undetermined coefficients to find a particular solution for the
non-homogeneous term.
Step 1: Find the characteristic equation for the homogeneous part.
The homogeneous recurrence relation is given by an= 3an−1−2an−2. Let’s
assume the solution has the form an=rn. Substituting this into the recurrence
relation, we get:
rn= 3rn−1−2rn−2.
Dividing by rn−2, we simplify to:
r2= 3r−2.
This gives us the characteristic equation r2−3r+ 2 = 0, which factors as
(r−1)(r−2) = 0. So, the characteristic roots are r= 1,2.
Step 2: Find the homogeneous solution. The general solution to the
homogeneous part is: a(h)
n=c1(1)n+c2(2)n, where c1and c2are constants to
be determined from the initial conditions.
29
Step 3: Find a particular solution for the non-homogeneous part.
To find a particular solution for the non-homogeneous term 2n, we assume a
solution of the form a(p)
n=An2n, where Ais a constant to be determined.
Substitute a(p)
ninto the recurrence relation:
An2n= 3(A(n−1)2n−1)−2(A(n−2)2n−2)+2n.
Dividing by 2nand simplifying, we get:
A=2
3.
So, a particular solution is a(p)
n=2
3n2n.
Step 4: Combine the homogeneous and particular solutions. The
general solution to the non-homogeneous recurrence relation is the sum of the
homogeneous and particular solutions:
an=a(h)
n+a(p)
n=c1+c2(2)n+2
3n2n.
Step 5: Use initial conditions to find c1and c2.Using the initial
conditions a0= 1 and a1= 3, we can find c1and c2:
a0=c1+c2= 1,
a1=c1+ 2c2(2) + 2
3·1·2 = 3.
Solving these equations simultaneously, we find c1=1
3and c2=2
3.
Step 6: Final solution. Therefore, the closed-form solution to the given
non-homogeneous recurrence relation is:
an=1
3+2
3(2)n+2
3n2n.
Question 31
Question
Let anbe a sequence defined by the recurrence relation an+2 −7an+1 +12an= 0
with initial conditions a0= 2 and a1= 3. Find a formula for anfor n≥0.
Solution
To solve the given recurrence relation, we first assume that the solution has the
form an=rnfor some constant r. Substituting this into the recurrence relation
gives us the characteristic equation r2−7r+ 12 = 0.
Step 1: Solve the characteristic equation r2−7r+ 12 = 0.
The characteristic equation factors as (r−3)(r−4) = 0, so the roots are
r= 3 and r= 4.
30
Step 2: Write the general solution in terms of r= 3 and r= 4.
Since the roots are distinct, the general solution to the recurrence relation
is given by an=A·3n+B·4n, where Aand Bare constants to be determined.
Step 3: Use the initial conditions a0= 2 and a1= 3 to find Aand B.
Substitute n= 0 into the formula and set a0= 2:
2 = A·30+B·40=A+B
Substitute n= 1 into the formula and set a1= 3:
3 = A·31+B·41= 3A+ 4B
Solving the system of equations, we find A= 1 and B= 1.
Step 4: Write the final formula for an.
Therefore, the formula for anis an= 3n+ 4nfor n≥0.
Question 32
Question
Let ansatisfy the non-homogeneous recurrence relation an= 3an−1−2an−2+2n
for n≥2, with initial conditions a0= 1 and a1= 2. Find a formula for anin
terms of nwithout using the characteristic roots method.
Solution
Step 1: Find the homogeneous solution of the recurrence relation. Assume
a(h)
nhas the form a(h)
n=rn. Substitute this into the homogeneous relation
an= 3an−1−2an−2to get rn= 3rn−1−2rn−2. Dividing by rn−2, we have
r2= 3r−2, which factors as (r−1)(r−2) = 0. This gives us r1= 1 and r2= 2.
Step 2: Find a particular solution for the non-homogeneous part. Since
2nis a power of 2, assume a particular solution of the form a(p)
n=A·2n.
Substitute this into the non-homogeneous relation an= 3an−1−2an−2+ 2nto
get A·2n= 3(A·2n−1)−2(A·2n−2) + 2n. This simplifies to A=2
3. Therefore,
a(p)
n=2
3·2n=2n+1
3.
Step 3: Write the general solution as a sum of the homogeneous and partic-
ular solutions. Therefore, the general solution is an=a(h)
n+a(p)
n=c1·1n+c2·
2n+2n+1
3. Using the initial conditions a0= 1 and a1= 2, we find c1+c2+2
3= 1
and c1+ 2c2+4
3= 2.
Step 4: Solve for c1and c2. Subtracting the first equation from the second,
we get c2=1
3. Substituting this back into the first equation, we find c1=1
3.
Therefore, the formula for anin terms of nis an=1
3+1
3·2n+2n+1
3.
31
Question 33
Question
Consider the homogeneous linear recurrence relation given by:
an= 2an−1−2an−2
with initial conditions a0= 0 and a1= 1. Let bnbe the non-homogeneous
linear recurrence relation defined by:
bn= 2an+ 3
Calculate the first four terms of the sequence defined by bn.
Solution
Step 1: Find the characteristic equation of the homogeneous recurrence relation:
The characteristic equation is obtained by setting each term equal to zero:
r2= 2r−2
r2−2r+ 2 = 0
Step 2: Solve the characteristic equation:
Using the quadratic formula r=−b±√b2−4ac
2a, we have:
r=2±p(−2)2−4∗1∗2
2∗1
r=2±√4−8
2
r=2±√−4
2
r=2±2i
2
r= 1 ±i
So, the characteristic roots are complex with r1= 1 + iand r2= 1 −i.
Step 3: Write the general solution of the homogeneous recurrence relation:
The general solution takes the form:
an=c1(1 + i)n+c2(1 −i)n
Step 4: Use the initial conditions to find c1and c2:
Given a0= 0 and a1= 1, we have:
32
a0=c1+c2= 0
a1=c1(1 + i) + c2(1 −i)=1
Solving these equations simultaneously, we find c1=1
2iand c2=−1
2i.
Step 5: Calculate the terms of the non-homogeneous sequence bn:
Now, we use the relation bn= 2an+ 3 and substitute the expression for an
into it:
bn= 2 1
2i(1 + i)n−1
2i(1 −i)n+ 3
Now, calculate the first four terms of the sequence bnusing n= 0,1,2,3.
Question 34
Question
Let anbe defined recursively by the recurrence relation an= 2an−1−3an−2with
initial conditions a0= 1 and a1= 4. Find a formula for anfor all non-negative
integers n.
Solution
Step 1: Finding the characteristic equation The characteristic equation for the
given recurrence relation is r2= 2r−3, which simplifies to r2−2r+ 3 = 0.
Step 2: Finding the roots of the characteristic equation Using the quadratic
formula, r=−(−2)±√(−2)2−4∗1∗3
2∗1, we get r=2±√4−12
2=2±√−8
2= 1 ±i√2.
Step 3: Forming the general solution Since the roots are complex, the general
solution to the recurrence relation is an=c1(1 + i√2)n+c2(1 −i√2)n.
Step 4: Applying the initial conditions Substitute a0= 1 and a1= 4 into
the general solution. a0=c1(1 + i√2)0+c2(1 −i√2)0=c1+c2= 1 — (1)
a1=c1(1 + i√2)1+c2(1 −i√2)1=c1(1 + i√2) + c2(1 −i√2) = 4 — (2)
Step 5: Solving the system of equations From equations (1) and (2), we have
the system: c1+c2= 1, c1(1 + i√2) + c2(1 −i√2) = 4.
Solving this system, we find c1=4−2i√2
2√2and c2=2i√2
2√2.
Step 6: Final formula for anSubstitute the values of c1and c2into the
general solution to get the final formula for an:an=4−2i√2
2√2(1 + i√2)n+
2i√2
2√2(1 −i√2)n.
33
Question 35
Question
Let (an)n≥0be a sequence defined by the recurrence relation an+2 = 2an+1 −3an
for n≥0 with initial conditions a0= 1 and a1=−1. Find a closed-form formula
for an.
Solution
Step 1: Find the characteristic equation by assuming the solution has the form
an=rn. The characteristic equation is given by r2= 2r−3. Simplifying, we
have r2−2r+ 3 = 0.
Step 2: Solve the characteristic equation to find the roots. Using the
quadratic formula, we find that the roots are r=2±√(−2)2−4(1)(3)
2(1) = 1 ±i√2.
Step 3: Write the general solution to the homogeneous recurrence relation.
Since the roots are complex, the general solution will be of the form
an=A(1 + i√2)n+B(1 −i√2)n,
where Aand Bare constants to be determined.
Step 4: Use the initial conditions to find the values of Aand B. From the
initial conditions a0= 1 and a1=−1, we have:
a0=A(1 + i√2)0+B(1 −i√2)0=A+B= 1,
a1=A(1 + i√2) + B(1 −i√2) = (A+B) + i√2A−i√2B=−1.
Step 5: Solve for Aand B. Solving the system of equations from Step 4, we
find A=1
2+i√2
2and B=1
2−i√2
2.
Step 6: Write the closed-form formula for an. Substitute the values of A
and Bback into the general solution to get the closed-form formula for an:
an= 1
2+i√2
2!(1 + i√2)n+ 1
2−i√2
2!(1 −i√2)n.
34
