MATH 117 - ELEMENTS OF
MATHEMATICS - Homogeneous and
non-homogeneous recurrence relations
Question Bank - Set 1
Liberty University
Question 1
Question
Let anbe a sequence defined by the recurrence relation an= 2an−1−an−2for
n≥2, where a0= 1 and a1= 2. Find a closed-form expression for an.
Solution
We first find the characteristic equation of the recurrence relation an= 2an−1−
an−2:
r2= 2r−1
r2−2r+ 1 = 0
(r−1)2= 0
r= 1
Therefore, the characteristic equation has a repeated root at r= 1. Since
the roots are the same, we need to multiply one of the terms by nto find an
independent solution. So, the general solution for the homogeneous part of the
recurrence relation is:
a(h)
n=c1·1n+c2·n·1n=c1+c2n
To find a particular solution for the non-homogeneous part of the recurrence
relation, we assume a(p)
n=A(a constant).
Substitute a(p)
n=Ain the original recurrence relation:
A= 2A−A
Solving for A, we get A= 0.
Therefore, the general solution for the non-homogeneous part of the recur-
rence relation is simply a(p)
n= 0.
Thus, the general solution for the entire recurrence relation is the sum of the
homogeneous and non-homogeneous solutions:
an=a(h)
n+a(p)
n=c1+c2n
Now, we use the initial conditions a0= 1 and a1= 2 to find c1and c2:
a0=c1= 1
a1=c1+c2= 2
Solving the above equations simultaneously, we find c1= 1 and c2= 1.
Therefore, the closed-form expression for anis given by:
an= 1 + n
Question 2
Question
Find the particular solution to the non-homogeneous recurrence relation an=
3an−1−2an−2+ 1 given that a0= 1 and a1= 2.
Solution
To find the particular solution of the non-homogeneous recurrence relation, we
will first find the general solution to the homogeneous part of the equation and
then find a particular solution to the non-homogeneous part.
Step 1: Find the roots of the characteristic equation by setting an=rn:
rn= 3rn−1−2rn−2
This simplifies to:
r2−3r+ 2 = 0
Factoring the quadratic equation gives us:
(r−1)(r−2) = 0
So the roots are r1= 1 and r2= 2.
Therefore, the general solution to the homogeneous part is:
a(h)
n=A(1)n+B(2)n
where Aand Bare constants to be determined.
2
Step 2: Find the particular solution to the non-homogeneous part: Let’s
assume the particular solution has the form a(p)
n=K(a constant).
Plugging the particular solution back into the non-homogeneous equation,
we get:
K= 3K−2K+ 1
K=K+ 1
0=1
This equation has no solution, meaning that a(p)
nis not a constant. We need
to try a(p)
n=Cn +D.
Plugging this into the non-homogeneous equation, we get:
Cn +D= 3(C(n−1) + D)−2(C(n−2) + D)+1
Cn +D= 3C(n−1) + 3D−2C(n−2) −2D+ 1
Simplify by expanding and combining like terms:
Cn +D=Cn + 3C−3C+ 2C+ 1
D= 2C+ 1
Therefore, the particular solution is:
a(p)
n= 2n+ 1
Step 3: Find the particular solution: The general solution will be the sum
of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n
an=A(1)n+B(2)n+ 2n+ 1
Using the initial conditions a0= 1 and a1= 2, we can solve for Aand B:
A+B+ 1 = 1
A(1) + B(2) + 3 = 2
Solving these equations gives A= 0 and B= 1, so the particular solution is:
an= 2n+ 2n+ 1
Question 3
Question
Let ansatisfy the recurrence relation an+2 −5an+1 + 6an= 0 for n≥0 with
initial conditions a0= 2 and a1= 3. Find a closed-form expression for an.
3
Solution
Step 1: First, we find the characteristic equation of the given recurrence relation.
We assume that the solution has the form an=rn. Substituting this into the
recurrence relation, we get:
rn+2 −5rn+1 + 6rn= 0
r2−5r+ 6 = 0
Step 2: We factor the quadratic equation to find its roots:
(r−2)(r−3) = 0
r1= 2, r2= 3
Step 3: The general solution to the recurrence relation is then:
an=c1·2n+c2·3n
Step 4: Using the initial conditions a0= 2 and a1= 3, we can solve for c1
and c2. Substitute n= 0 into an=c1·2n+c2·3n:
a0=c1·20+c2·30=c1+c2= 2
Step 5: Substitute n= 1 into an=c1·2n+c2·3n:
a1=c1·21+c2·31= 2c1+ 3c2= 3
Step 6: Solving the system of equations:
(c1+c2= 2
2c1+ 3c2= 3
Step 7: From the first equation, we get c1= 2 −c2. Substituting this into
the second equation, we find 2(2 −c2)+3c2= 3. Solving yields c1= 1, c2= 1.
Step 8: Therefore, the closed-form expression for anis:
an= 2n+ 3n
Question 4
Question
Let anbe defined recursively by the following recurrence relation:
an= 2an−1−2an−2+n
with initial conditions a0= 1 and a1= 2. Determine an explicit formula for an.
4
Solution
To find an explicit formula for an, we first solve the homogeneous version of
the recurrence relation. Then, we will find a particular solution for the non-
homogeneous part, and combine the two to get the general formula for an.
Step 1: Find the characteristic equation For the homogeneous part of
the recurrence relation, we consider the equation an= 2an−1−2an−2. We write
this as:
an−2an−1+ 2an−2= 0
The characteristic equation corresponding to this homogeneous recurrence rela-
tion is:
r2−2r+ 2 = 0
Solving this quadratic equation gives us complex roots r= 1 ±i.
Step 2: Find the general solution for the homogeneous part The
general solution for the homogeneous part of the recurrence relation is of the
form:
an=c1·(1 + i)n+c2·(1 −i)n
where c1and c2are constants to be determined.
Step 3: Find a particular solution for the non-homogeneous part
For the non-homogeneous part n, we will assume a linear form an=an +band
substitute it into the original recurrence relation to find aand b.
Substitute an=an +binto the original recurrence relation:
an +b= 2(an −1 + b)−2(an −2 + b) + n
This simplifies to:
an +b= 2an −2a+ 2b+n
Equating coefficients, we get the following system of equations:
2a= 2a, 2b−2a= 0
Solving this system gives a=1
2and b= 0.
Step 4: Determine the general formula for anThe general formula for
anis the sum of the general solution of the homogeneous part and the particular
solution of the non-homogeneous part:
an=c1·(1 + i)n+c2·(1 −i)n+1
2n
Step 5: Applying initial conditions To find c1and c2, we use the initial
conditions a0= 1 and a1= 2:
a0=c1+c2= 1
a1=c1(1 + i) + c2(1 −i) + 1
2= 2
Solving these equations will give us the specific values of c1and c2, providing
the final explicit formula for an.
5
Question 5
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
To find a closed-form expression for an, we need to solve the non-homogeneous
recurrence relation. We will begin by finding the homogeneous solution and
then the particular solution.
Step 1: Find the homogeneous solution
We start by assuming that the solution to the homogeneous recurrence re-
lation is of the form an=cn. Substitute this into the homogeneous part of the
original recurrence relation to get:
cn= 2cn−1−cn−2
Divide every term by cn−2:
c2= 2c−1
c2−2c+ 1 = 0
(c−1)2= 0
c= 1
Therefore, the homogeneous solution is an=k1+k2n.
Step 2: Find the particular solution
Since the non-homogeneous part of the recurrence relation is 2n, we assume
the particular solution to be of the form a(p)
n=A2n. Substitute a(p)
ninto the
original recurrence relation:
A2n= 2(A2n−1)−(A2n−2)+2n
A2n= 2A2n−A2n−2+ 2n
A= 2A−A
2n+ 1
A= 2A−A
4+ 1
3A
4= 1
A=4
3
Therefore, the particular solution is a(p)
n=4
3·2n.
Step 3: Find the general solution
6
The general solution is the sum of the homogeneous solution and the partic-
ular solution:
an=k1+k2n+4
3·2n
Step 4: Find the constants using initial conditions
Using the initial conditions a0= 1 and a1= 3:
k1+4
3= 1
k1=−1
3
k1+k2+8
3= 3
−1
3+k2+8
3= 3
k2=10
3
Therefore, the closed-form expression for anis:
an=−1
3+10
3n+4
3·2n
Question 6
Question
Consider the non-homogeneous recurrence relation given by: an= 4an−1−
4an−2+ 2nwith initial conditions a0= 1 and a1= 2. Determine the explicit
formula for an.
Solution
Step 1: First, solve the associated homogeneous recurrence relation an= 4an−1−
4an−2.
The characteristic equation is r2= 4r−4, which simplifies to r2−4r+4 = 0.
This can be factored as (r−2)2= 0, so we have a repeated root of r= 2.
Therefore, the solution to the homogeneous recurrence relation is of the form
a(h)
n= (c1+c2n)2n.
Step 2: Now, we will find a particular solution to the non-homogeneous
recurrence relation.
Since the non-homogeneous term is 2n, we will try a particular solution of
the form a(p)
n=An2n.
Substitute a(p)
ninto the recurrence relation: An2n= 4(A(n−1)2n−1)−
4(A(n−2)2n−2)+2n.
Simplify the above equation to find A=1
4.
7
Therefore, the particular solution is a(p)
n=1
4n2n.
Step 3: We can now write the general solution to the non-homogeneous
recurrence relation as the sum of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n= (c1+c2n)2n+1
4n2n.
Step 4: Apply the initial conditions a0= 1 and a1= 2 to solve for c1and
c2.
From a0= 1, we get c1= 1.
From a1= 2, we get c1+ 2c2+1
4·1·2 = 2. Simplifying this equation, we
find c2=3
8.
Step 5: Finally, substitute c1= 1 and c2=3
8back into the general solution
to get the explicit formula for an:
an= (1 + 3
4n)2n.
Question 7
Question
Let anbe a sequence defined recursively by the recurrence relation:
an= 3an−1−2an−2+ 2n
with initial conditions a0= 2 and a1= 5. Determine a closed-form expres-
sion for an.
Solution
Step 1: First, we find the characteristic equation of the homogeneous part of
the recurrence relation (an= 3an−1−2an−2). The characteristic equation is
obtained by replacing anwith λn:
λn= 3λn−1−2λn−2
Dividing through by λn−2:
λ2= 3λ−2
λ2−3λ+ 2 = 0
This quadratic equation can be factored as:
(λ−1)(λ−2) = 0
So, the characteristic roots are λ1= 1 and λ2= 2.
Step 2: The general solution to the homogeneous part of the recurrence
relation is then given by:
an=C1·1n+C2·2n
8
Simplifying, we get:
an=C1+C2·2n
Step 3: Next, we find a particular solution for the complete recurrence re-
lation with the form an=A·2n. Substitute an=A·2ninto the original
recurrence relation and solve for A:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
A·2n= 3A·2n−1−2A·2n−2+ 2n
A=2n
2
Step 4: The complete solution to the recurrence relation is then the sum of
the general and particular solutions:
an=C1+C2·2n+2n
2
Using the initial conditions a0= 2 and a1= 5, we can solve for C1and C2:
a0=C1+C2= 2
a1=C1+ 2C2+ 1 = 5
Solving these equations, we find C1= 1 and C2= 1.
Therefore, the closed-form expression for anis:
an= 1 + 2n+2n
2= 1 + 3·2n
2
Question 8
Question
Consider the non-homogeneous linear recurrence relation given by: an= 2an−1−
an−2+n2+ 2n+ 1. If the initial conditions are a0= 1 and a1= 3, find a closed-
form expression for an.
Solution
To solve the non-homogeneous linear recurrence relation, we first need to find
the general solution for the associated homogeneous relation, an= 2an−1−an−2.
Let ah
nrepresent the homogeneous part of the solution, and let ap
nrepresent a
particular solution of the non-homogeneous equation.
9
Step 1: Find the homogeneous solution Consider the characteristic
equation r2= 2r−1. Solving for r, we get r= 1 and r=−1. Therefore, the
general solution to the homogeneous equation is:
ah
n=c1·1n+c2·(−1)n=c1+ (−1)n·c2
Step 2: Find a particular solution We try a particular solution of the
form ap
n=An2+Bn +C. Substituting this form into the non-homogeneous
equation and simplifying, we get:
An2+Bn +C= 2(An2+B(n−1)+C)−(A(n−1)2+B(n−1)+C)+n2+2n+1
An2+Bn +C= 2An2+ 2Bn −2A+n2+ 2n+ 1
Equating coefficients of like terms, we get the following system of equations:
2A=A=⇒A= 0
2B= 2B+ 2 =⇒0 = 2
−2A= 1 =⇒A=−1
2
Therefore, the particular solution is ap
n=−1
2n2+Bn +C
Step 3: Find the full solution Combining the homogeneous and partic-
ular solutions, we get:
an=ah
n+ap
n=c1+ (−1)n·c2−1
2n2+Bn +C
Step 4: Use initial conditions to find constants Given initial conditions
a0= 1 and a1= 3, we can substitute and solve for the constants c1,c2,B, and
C. We find:
a0=c1+c2= 1
a1=c1−c2−1
2+B+C= 3
Solving these equations simultaneously, we get c1= 2, c2=−1, B=3
2, and
C=5
2.
Step 5: Final solution Plugging the values of c1,c2,B, and Cback into
the full solution, we get the closed-form expression for an:
an= 2 + (−1)n−1
2n2+3
2n+5
2
Question 9
Question
Consider the non-homogeneous recurrence relation given by
an= 2an−1−an−2+n,
with initial conditions a0= 0 and a1= 1. Find a closed-form expression for an.
10
Solution
To find a closed-form expression for an, we first need to solve the associated
homogeneous recurrence relation an= 2an−1−an−2and then find a particular
solution for the non-homogeneous part n.
Step 1: Solve the homogeneous recurrence relation The characteristic
equation for the homogeneous part is r2= 2r−1, which simplifies to r2−2r+1 =
(r−1)2= 0. This gives a repeated root r= 1.
Therefore, the solution to the homogeneous recurrence relation is a(h)
n=
c1·1n+c2·n·1n=c1+c2n.
Step 2: Find a particular solution for the non-homogeneous part
Since the non-homogeneous part is a linear function n, we try a particular
solution of the form a(p)
n=An+B. Substituting this into the original recurrence
relation, we get:
An +B= 2(A(n−1) + B)−A(n−2) −B+n.
Solving for Aand Bgives A=−1 and B= 0.
Therefore, the particular solution is a(p)
n=−n.
Step 3: 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+c2n−n.
Step 4: Use initial conditions to find c1and c2Using the initial
conditions a0= 0 and a1= 1, we have:
c1+c2·0−0=0, c1+c2·1−1 = 1.
Solving these equations gives c1= 1 and c2= 1.
Step 5: Write the closed-form expression for anTherefore, the closed-
form expression for anis:
an= 1 + n−n= 1.
Question 10
Question
Consider the following non-homogeneous recurrence relation:
an= 2an−1−an−2+ 2n
with initial conditions a0= 1 and a1= 2. Find a closed-form expression for
an.
11
Solution
To solve this non-homogeneous recurrence relation, we first need to find the
general form of the solution to the associated homogeneous recurrence relation.
Let ah
nbe the homogeneous solution. The associated homogeneous recurrence
relation is:
ah
n= 2an−1−an−2
Step 1: Find the characteristic equation by assuming ah
n=rn:
Substitute ah
n=rninto the homogeneous recurrence relation:
rn= 2rn−1−rn−2
Divide by rn−2to simplify:
r2= 2r−1
The characteristic equation is r2−2r+ 1 = (r−1)2= 0. This gives us a
repeated root r= 1.
Step 2: Find the form of the homogeneous solution ah
n:
Since r= 1 is a repeated root, the form of the homogeneous solution is:
ah
n= (A+Bn)·1n=A+Bn
Step 3: Find a particular solution to the non-homogeneous recurrence re-
lation:
Let’s guess a particular solution of the form ap
n=C·2n, where Cis a
constant to be determined.
Substitute this form into the non-homogeneous recurrence relation:
C·2n= 2(C·2n−1)−(C·2n−2)+2n
This simplifies to C= 1. Therefore, ap
n= 2nis a particular solution.
Step 4: Find the general solution an:
The general solution is the sum of the homogeneous and particular solutions:
an=ah
n+ap
n=A+Bn + 2n
Step 5: Use the initial conditions to find Aand B:
a0=A+B·0+20=A= 1
a1=A+B+ 21=A+B+ 2 = 2
From the above equations, we find A= 1 and B=−1. Therefore, the
closed-form expression for anis:
an= 1 −n+ 2n
12
Question 11
Question
Consider the non-homogeneous recurrence relation given by:
an= 3an−1−2an−2+ 2n
Given that a0= 1 and a1= 3, find an explicit formula for an.
Solution
To find an explicit formula for an, we first need to find the homogeneous solution
a(H)
nand the particular solution a(P)
n.
Step 1: Find the homogeneous solution a(H)
nThe associated homoge-
neous recurrence relation is: an= 3an−1−2an−2. Let’s assume the homogeneous
solution has the form: a(H)
n=rn.
Substitute a(H)
n=rninto the homogeneous recurrence relation:
rn= 3rn−1−2rn−2
Divide by rn−2:
r2= 3r−2
r2−3r+ 2 = 0
This quadratic equation has roots r= 1 and r= 2. Therefore, the homogeneous
solution is:
a(H)
n=c1·1n+c2·2n=c1+c2·2n
Step 2: Find the particular solution a(P)
nLet’s assume the particular
solution has the form: a(P)
n=A·2n. Substitute a(P)
n=A·2ninto the non-
homogeneous recurrence relation:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
A=3
2A−1
2A+ 1
A=2
2= 1
Therefore, the particular solution is:
a(P)
n= 2n
Step 3: Find the general solution anThe general solution is the sum of
the homogeneous and particular solutions:
an=a(H)
n+a(P)
n=c1+c2·2n+ 2n
13
Step 4: Use initial conditions to find c1and c2Using the initial
conditions a0= 1 and a1= 3:
a0=c1+c2= 1
a1=c1+ 2c2+ 2 = 3
Solving these equations, we find c1= 1 and c2= 1.
Step 5: Write the explicit formula for anTherefore, the explicit formula
for anis:
an= 1 + 2n+ 2n
Question 12
Question
Let anbe the sequence defined by the recurrence relation an+2 = 4an+1 −4an,
where a0= 1 and a1= 3. Find a closed form expression for an.
Solution
Given: ansatisfies the recurrence relation an+2 = 4an+1 −4an, with initial
conditions a0= 1 and a1= 3.
Step 1: Find the characteristic equation. Let’s assume an=rnis a solution
to the recurrence relation. Substituting this into the recurrence relation, we get:
rn+2 = 4rn+1 −4rn
Dividing by rn(since r= 0), we get:
r2= 4r−4
r2−4r+ 4 = 0
(r−2)2= 0
r= 2,2
So, the characteristic equation is (r−2)2= 0.
Step 2: Find the general form of the solution. Since we have a repeated
root, the general solution will be of the form:
an= (c1+c2n)·2n
Step 3: Use initial conditions to solve for c1and c2. Given a0= 1 and
a1= 3:
a0= 1 = (c1)·20⇒c1= 1
a1= 3 = (c1+c2)·21⇒c1+c2= 3
14
Substitute c1= 1 into the second equation:
1 + c2= 3
c2= 2
Step 4: Write the closed form expression. Therefore, the closed form ex-
pression for anis:
an= 2n+ 2n·2n
Question 13
Question
Consider the homogeneous recurrence relation given by an+2 −3an+1 + 2an= 0
for n≥0, with initial conditions a0= 1 and a1= 2. Find a closed-form
expression for an.
Solution
Step 1: First, find the characteristic equation of the homogeneous recurrence
relation. The characteristic equation is r2−3r+ 2 = 0. Solve this quadratic
equation:
r=3±√32−4·1·2
2·1=3±√1
2
r=3±1
2= 2,1
Step 2: The general solution to the homogeneous recurrence relation is of
the form:
an=c1·2n+c2·1n=c1·2n+c2
Step 3: Use the initial conditions a0= 1 and a1= 2 to find the values of c1
and c2.
a0=c1·20+c2=c1+c2= 1
a1=c1·21+c2= 2c1+c2= 2
Step 4: Solve the system of equations formed by c1+c2= 1 and 2c1+c2= 2.
Subtract the first equation from the second:
c1= 1
Step 5: Substitute c1= 1 back into c1+c2= 1 to find c2:
1 + c2= 1 ⇒c2= 0
Step 6: The closed-form expression for anis:
an= 2n
15
Question 14
Question
Consider the following homogeneous recurrence relation:
an+3 + 3an+2 −4an+1 −4an= 0
with initial conditions a0= 1, a1= 2,and a2= 3. Find a closed-form expression
for an.
Solution
To solve the given homogeneous recurrence relation, we first need to find the
characteristic equation. Let’s assume an=rnand substitute it into the recur-
rence relation:
Step 1: Substitute an=rninto the recurrence relation:
rn+3 + 3rn+2 −4rn+1 −4rn= 0
Step 2: Divide the equation by rnand simplify:
r3+ 3r2−4r−4 = 0
Step 3: Factor the polynomial to find the roots:
(r+ 1)(r−1)2= 0
This gives us roots r1=−1 and r2= 1 with multiplicity 2.
Step 4: The general solution to the recurrence relation is:
an=C1(−1)n+C2n(−1)n+C3(1)n
where C1, C2,and C3are constants to be determined using initial conditions.
Step 5: Use the initial conditions to find the values of C1, C2,and C3:
a0= 1 : C1+C3= 1
a1= 2 : −C1+C2+C3= 2
a2=3:C1−2C2+C3= 3
Step 6: Solve the system of equations to find C1, C2,and C3: Solving the
system of equations, we find C1= 0, C2=−1,and C3= 1.
Step 7: Substitute the constants back into the general solution:
an=−n(−1)n+ (−1)n
So, the closed-form expression for anis an=−n(−1)n+ (−1)n.
16
Question 15
Question
Consider the following non-homogeneous recurrence relation:
an=an−1+ 2n
If the initial condition is a0= 1, find the explicit formula for an.
Solution
To solve this non-homogeneous recurrence relation, we first need to find the
solutions to the corresponding homogeneous relation by setting the right-hand
side to 0. Then, we will find a particular solution to the non-homogeneous part
and combine it with the homogeneous solutions to get the general solution.
Step 1: Find the homogeneous solution We consider the homogeneous
part of the recurrence relation:
an=an−1
This is a simple linear recurrence relation with characteristic equation:
r−1=0
r= 1
So, the homogeneous solution is a(H)
n=c·1n=c, where cis a constant.
Step 2: Find a particular solution For the non-homogeneous part of the
recurrence relation 2n, we assume a particular solution of the form a(P)
n=A·2n.
Substituting this into the original recurrence relation:
A·2n=A·2n−1+ 2n
Solving for A, we get A=−1.
So, the particular solution is a(P)
n=−2n.
Step 3: Find the general solution The general solution is the sum of
the homogeneous and particular solutions:
an=a(H)
n+a(P)
n
an=c−2n
Step 4: Find the value of cUsing the initial condition a0= 1, we have:
1 = c−20
c= 2
Step 5: Write the explicit formula for anThus, the explicit formula
for anis:
an= 2 −2n
17
Question 16
Question
Let anbe the nth term of a sequence defined by the recurrence relation an=
2an−1+ 3an−2for n≥2, with initial conditions a0= 1 and a1= 2. Find a
closed-form expression for an.
Solution
Step 1: Find the characteristic equation of the given recurrence relation. The
characteristic equation is obtained by setting the terms of the recurrence relation
without the subscripts to zero. For this recurrence relation, the characteristic
equation is:
r2= 2r+ 3
Step 2: Solve the characteristic equation to find the roots. To solve, we
rewrite the equation as r2−2r−3 = 0 and factorize it:
(r−3)(r+ 1) = 0
This gives us roots r1= 3 and r2=−1.
Step 3: Write the general solution of the recurrence relation. Since the roots
r1= 3 and r2=−1 are distinct, the general solution is of the form:
an=c1(3)n+c2(−1)n
where c1and c2are constants to be determined.
Step 4: Use the initial conditions a0= 1 and a1= 2 to find the values of
c1and c2. Substituting n= 0 and n= 1 into the general solution, we get the
following system of equations:
(c1+c2= 1
3c1−c2= 2
Step 5: Solve the system of equations to find c1and c2. Adding the two
equations gives 4c1= 3, so c1=3
4. Substituting back, we find c2=1
4.
Step 6: Substitute the values of c1and c2back into the general solution to
obtain the closed-form expression for an:
an=3
4·3n+1
4·(−1)n
Question 17
Question
Consider the following second order homogeneous recurrence relation: an=
2an−1−an−2with initial conditions a0= 1 and a1= 3. Find a closed-form
expression for an.
18
Solution
Step 1: Find the characteristic equation of the recurrence relation. The charac-
teristic equation is given by:
r2= 2r−1
r2−2r+ 1 = 0
(r−1)2= 0
r= 1 (double root)
Step 2: Write the general solution for the recurrence relation. Since we have
a double root, the general solution can be written as:
an= (c1+c2n)1n
an=c1+c2n
Step 3: Use the initial conditions to find the values of c1and c2. From
a0= 1:
1 = c1
From a1= 3:
3 = c1+c2
Solving these equations simultaneously, we find c1= 1 and c2= 2.
Step 4: Write the closed-form expression for an. Substitute the values of c1
and c2back into an=c1+c2n:
an= 1 + 2n
Question 18
Question
Let anbe defined recursively by the recurrence relation an= 3an−1−2an−2,
where a0= 1 and a1= 2. Find an explicit formula for an.
Solution
To find an explicit formula for an, we first need to find the characteristic equation
associated with the given recurrence relation. Let an=rnbe a solution to the
recurrence relation. Substituting this into the recurrence relation gives
rn= 3rn−1−2rn−2.
Dividing both sides by rn−2(assuming r= 0) gives the characteristic equa-
tion
r2= 3r−2.
19
Step 1: Find the roots of the characteristic equation. Solving r2= 3r−2
gives
r2−3r+ 2 = 0.
Factoring the quadratic equation, we get
(r−1)(r−2) = 0.
So the roots are r= 1 and r= 2.
Step 2: Write the general solution. Since the roots are distinct, the general
solution to the recurrence relation is
an=A(1)n+B(2)n,
where Aand Bare constants to be determined.
Step 3: Use the initial conditions to determine Aand B. Given a0= 1 and
a1= 2, we can set up a system of equations:
a0=1:A+B= 1,
a1=2:A+ 2B= 2.
Solving this system of equations gives A= 0 and B= 1.
Step 4: Write the explicit formula for an. Therefore, the explicit formula
for anis
an= 2n.
Question 19
Question
Consider the recurrence relation an= 3an−1−2an−2with initial conditions
a0= 1 and a1= 2. Find a closed-form expression for an.
Solution
To solve the recurrence relation, we first need to find the characteristic equation
by assuming a solution of the form an=rn. Substituting this into the recurrence
relation gives us:
rn= 3rn−1−2rn−2
Dividing by rn−2(since rncannot be zero) gives:
r2= 3r−2
This simplifies to:
r2−3r+ 2 = 0
Now we solve this quadratic equation to find the roots r1and r2:
(r−1)(r−2) = 0
20
r1= 1, r2= 2
So, the general solution to the homogeneous recurrence relation is:
a(h)
n=Arn
1+Brn
2=A(1)n+B(2)n=A+ 2nB
Next, we need to find a particular solution. Since the recurrence relation
is linear and non-homogeneous, we can try a particular solution of the form
an=k(a constant). Substituting this into the recurrence relation gives:
k= 3k−2k
k=k
This particular solution satisfies the recurrence relation.
Therefore, the general solution to the non-homogeneous recurrence relation
is:
an=a(h)
n+a(p)
n=A+ 2nB+k
Using the initial conditions a0= 1 and a1= 2, we can solve for A,B, and
k:
a0=A+B= 1
a1=A+ 2B+ 2 = 2
Solving these equations gives A= 0, B= 1, and k= 1.
Therefore, the closed-form expression for anis:
an= 2n+ 1
Question 20
Question
Consider the following recurrence relation:
an= 7an−1−10an−2+ 3 for n≥2
where a0= 1 and a1= 4. Find the explicit formula for an.
Solution
To find the explicit formula for an, we first solve the characteristic equation
associated with the homogeneous part of the recurrence relation.
Step 1: Find the characteristic equation
For a homogeneous recurrence relation of the form an=can−1+dan−2, the
characteristic equation is r2−cr −d= 0.
In this case, c= 7 and d=−10, so the characteristic equation is r2−7r+10 =
0.
Step 2: Solve the characteristic equation
21
Factoring the characteristic equation, we get (r−5)(r−2) = 0. So, the roots
are r1= 5 and r2= 2.
Step 3: Write down the homogeneous solution
The general form of the homogeneous solution is a(h)
n=A·5n+B·2n, where
Aand Bare constants to be determined.
Step 4: Find particular solution for the non-homogeneous part
For the non-homogeneous part 3, we assume a particular solution of the form
a(p)
n=k.
Substitute a(h)
nand a(p)
nback into the original recurrence relation to solve
for k:
k= 7k−10k+ 3
−2k= 3
k=−3
2
Step 5: Write down the general solution
The general solution is the sum of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=A·5n+B·2n−3
2
Step 6: Use initial conditions to find Aand B
Using the initial conditions a0= 1 and a1= 4:
a0=A·50+B·20−3
2= 1
A+B−3
2= 1
a1=A·51+B·21−3
2= 4
5A+ 2B−3
2= 4
Solving these equations simultaneously, we find A=11
4and B=−7
4.
Step 7: Write down the explicit formula for an
Therefore, the explicit formula for anis:
an=11
4·5n−7
4·2n−3
2
Question 21
Question
Let’s consider the sequence defined by the recurrence relation:
an+2 −5an+1 + 6an= 2n
with initial conditions a0= 1 and a1= 3. Determine the explicit formula
for an.
22
Solution
To solve this recurrence relation, we first solve the homogeneous version:
an+2 −5an+1 + 6an= 0
Step 1: Find the characteristic equation Let an=rn. Substitute this
into the homogeneous equation:
r2−5r+ 6 = 0
The characteristic equation is r2−5r+6 = 0, which factors to (r−2)(r−3) = 0.
So r1= 2 and r2= 3.
Step 2: Find the homogeneous solution The homogeneous solution is
of the form:
an=Arn
1+Brn
2
Plugging in r1= 2 and r2= 3, we get:
an=A(2n) + B(3n)
Step 3: Find coefficients using initial conditions Given a0= 1 and
a1= 3, we can set up a system of equations:
(A+B= 1
2A+ 3B= 3
Solving this system, we find A= 1 and B= 0.
Step 4: Write down the general solution Therefore, the general solution
to the homogeneous equation is:
an= 2n
Step 5: Find the particular solution Now we need to find a particular
solution to the original non-homogeneous equation. Since the right-hand side is
2n, we can try a particular solution of the form an=cn2n. Substituting this
into the equation, we get:
c(2n+2)−5c(2n+1)+6c(2n)=2n
c2n+2 −5c2n+1 + 6c2n= 2n
2c−10c+ 6c= 1
−2c= 1
c=−1
2
Step 6: Write down the complete solution Therefore, the complete
solution to the original non-homogeneous equation is:
an= 2n−1
2n2n
23
Question 22
Question
Let anbe defined by the recurrence relation an= 2an−1+ 3an−2for n≥2
with initial conditions a0= 1 and a1= 3. Find a formula for anfor all integers
n≥0.
Solution
Step 1: Find the characteristic equation
We can rewrite the recurrence relation as an−2an−1−3an−2= 0. The charac-
teristic equation is then r2−2r−3 = 0.
Step 2: Solve the characteristic equation
Factoring the characteristic equation, we have (r−3)(r+ 1) = 0. So, the roots
are r= 3 and r=−1.
Step 3: Write the general solution
Since we have distinct real roots, the general solution to the homogeneous part
of the recurrence relation is
an=A(3)n+B(−1)n.
Step 4: Use the initial conditions to find the values of Aand B
Substitute the initial conditions a0= 1 and a1= 3 into the general solution.
We get the equations:
(A+B= 1
3A−B= 3 .
Solving this system of equations, we find A= 1 and B= 0.
Step 5: Write the final formula
Therefore, the formula for anis
an= (3)n.
Question 23
Question
Consider the non-homogeneous recurrence relation defined by an= 2an−1+ 2n
with initial condition a0= 1. Find a closed-form expression for an.
Solution
To solve this non-homogeneous recurrence relation, we will first find the gen-
eral solution of the corresponding homogeneous relation, then find a particular
solution for the non-homogeneous part, and finally sum them up to obtain the
complete solution.
24
Step 1: Find the general solution
Let’s first write the homogeneous part of the recurrence relation:
an−2an−1= 0
This gives us the characteristic equation:
r−2=0
r= 2
Therefore, the general solution for the homogeneous part is:
a(h)
n=c·2n
Step 2: Find a particular solution
Now, we need to find a particular solution for the non-homogeneous part,
which is of the form a(p)
n=k·2n. Substituting this into the original recurrence
relation gives:
k·2n= 2(k·2n−1)+2n
k= 1
Therefore, a particular solution is a(p)
n= 2n.
Step 3: Find the complete solution
The complete solution is the sum of the general and particular solutions:
an=a(h)
n+a(p)
n
an=c·2n+ 2n
Step 4: Apply the initial condition
Using the initial condition a0= 1, we have:
a0=c·20+ 20=c+ 1 = 1
c= 0
Thus, the closed-form expression for anis:
an= 2n
Question 24
Question
Find a closed-form expression for the non-homogeneous recurrence relation de-
fined by an= 3an−1−2an−2+ 2nwith initial conditions a0= 1 and a1= 3.
25
Solution
Step 1: First, find the characteristic equation of the related homogeneous recur-
rence relation: an= 3an−1−2an−2. The characteristic equation is r2−3r+2 = 0,
which factors to (r−1)(r−2) = 0. Therefore, the characteristic roots are r1= 1
and r2= 2.
Step 2: Since the roots are distinct, the general solution to the homogeneous
recurrence relation is a(h)
n=A(1)n+B(2)n, where Aand Bare constants to be
determined.
Step 3: Next, we find a particular solution a(p)
nto the non-homogeneous
recurrence relation an= 3an−1−2an−2+ 2n. Since 2nis of the same form as
the non-homogeneity, we try a particular solution of the form a(p)
n=C(2)n,
where Cis a constant to be determined.
Step 4: Substitute a(p)
n=C(2)ninto the recurrence relation to get C(2)n=
3C(2)n−1−2C(2)n−2+ 2n. Dividing by 2n−2, we get 4C= 6C−2C+ 4, from
which we find that C=−2
3.
Step 5: The general solution to the non-homogeneous recurrence relation is
then the sum of the solutions to the homogeneous and particular parts: an=
a(h)
n+a(p)
n=A(1)n+B(2)n−2
3(2)n.
Step 6: Using the initial conditions a0= 1 and a1= 3, we plug these
values into the general solution to solve for Aand B:A+B−2
3= 1 and
A(1) + B(2) −2
3(2) = 3. Solving these equations gives A=5
3and B=1
3.
Step 7: Therefore, the closed-form expression for the non-homogeneous re-
currence relation is an=5
3(1)n+1
3(2)n−2
3(2)n. Simplifying this further gives
an=1
3(2n+ 2).
Thus, the solution to the non-homogeneous recurrence relation is an=
1
3(2n+ 2).
Question 25
Question
Let anbe defined by the recurrence relation an= 2an−1−an−2for n≥2, with
initial conditions a0= 1 and a1= 2. Find a formula for anfor n≥0.
Solution
Step 1: Find the characteristic equation by assuming a solution of the form
an=rn. The recurrence relation an= 2an−1−an−2can be rewritten as
r2= 2r−1, which simplifies to r2−2r+ 1 = 0. This quadratic equation factors
as (r−1)2= 0, so r= 1 is a repeated root.
Step 2: Write the general solution to the recurrence relation. Since r= 1 is
a repeated root, the general solution has the form an= (c1+c2n)1n=c1+c2n.
Step 3: Use the initial conditions a0= 1 and a1= 2 to find the values of
c1and c2. From a0= 1, we have c1= 1. From a1= 2, we have c1+c2= 2.
Substituting c1= 1, we find 1 + c2= 2, so c2= 1.
26
Step 4: Write the final formula for an. Therefore, the formula for anis
an= 1 + n.
Question 26
Question
Consider the following recurrence relation:
an+2 −4an+1 + 4an= 0
Given that a0= 2 and a1= 5, find a closed-form expression for an.
Solution
To find a closed-form expression for an, we first need to solve the characteristic
equation associated with the recurrence relation.
Step 1: Write down the characteristic equation
The characteristic equation for the given recurrence relation is:
r2−4r+ 4 = 0
Step 2: Solve the characteristic equation
Factoring the characteristic equation gives:
(r−2)2= 0
So, we have a repeated root r= 2.
Step 3: Write down the general solution
The general solution for the recurrence relation is of the form:
an=c1·2n+c2·n·2n
Step 4: Use initial conditions to find c1and c2
Using the initial conditions a0= 2 and a1= 5:
(c1+ 0 = 2
c1·2+2c2·2 = 5
Solving this system of equations gives c1= 2 and c2=3
2.
Step 5: Final closed-form expression for an
Substitute c1= 2 and c2=3
2into the general solution:
an= 2 ·2n+3
2·n·2n= 2n+1 +3n·2n
2
Therefore, the closed-form expression for anis an= 2n+1 +3n·2n
2.
27
Question 27
Question
Let (an) be a sequence defined by the recurrence relation an+1 = 3an+ 2, with
initial condition a0= 2. Determine a closed-form expression for an.
Solution
To solve the given recurrence relation, we first need to find the characteristic
equation associated with it. The characteristic equation is given by setting the
coefficient of anto 1: r−3 = 0. Solving this equation gives r= 3.
Step 1: The general solution for the homogeneous part of the recurrence
relation is of the form a(h)
n=c·3n, where cis a constant to be determined.
Step 2: Next, we need to find a particular solution a(p)
nto the non-homogeneous
part of the recurrence relation an+1 = 3an+ 2. Since the right-hand side is a
constant, we try a constant solution: a(p)
n=k, where kis a constant to be
determined.
Step 3: Substituting a(h)
nand a(p)
nback into the original recurrence relation,
we get:
k= 3k+ 2
Solving this equation gives k=−2.
Step 4: Therefore, the general solution to the non-homogeneous part of the
recurrence relation is a(p)
n=−2.
Step 5: Combining the solutions to the homogeneous and non-homogeneous
parts, we have an=a(h)
n+a(p)
n=c·3n−2.
Step 6: To find the value of the constant c, we use the initial condition
a0= 2.
2 = c·30−2 = c−2
Solving this equation gives c= 4.
Step 7: Therefore, the closed-form expression for the sequence (an) is an=
4·3n−2.
Question 28
Question
Consider the non-homogeneous recurrence relation defined by:
an+2 = 3an+1 −4an+ 2n, a0= 1, a1= 2
Find a closed-form expression for an.
28
Solution
To find the closed-form expression for an, we first solve the corresponding ho-
mogeneous recurrence relation:
an+2 = 3an+1 −4an
This characteristic equation is r2= 3r−4, which simplifies to r2−3r+ 4 = 0.
The roots of this characteristic equation are complex, 3±√32−4·4
2=3±i√7
2.
So, the general form of the solution to the homogeneous part of the recur-
rence relation is:
an=c1 3 + i√7
2!n
+c2 3−i√7
2!n
Next, we find a particular solution to the non-homogeneous recurrence re-
lation. We assume the particular solution has the form a(p)
n=An2nwhere A
is a constant to be determined. Substituting this into the non-homogeneous
recurrence relation, we get:
An2n+2 = 3An2n+1 −4An2n+ 2n
A2n+2 = 3A2n+1 −4A2n+ 2n
4A2n= 6A2n−4A2n+ 2n
A= 2−2=1
4
So, the particular solution is a(p)
n=1
4n2n.
Therefore, the general solution to the non-homogeneous recurrence relation
is:
an=c1 3 + i√7
2!n
+c2 3−i√7
2!n
+1
4n2n
Using the initial conditions a0= 1 and a1= 2, we can find the values of c1
and c2:
a0=c1+c2= 1
a1=c1 3 + i√7
2!+c2 3−i√7
2!+ 2 = 2
Solving these equations will give us the values of c1and c2, leading to the
final closed-form expression for an.
Question 29
Question
Consider the recurrence relation an= 3an−1−2an−2+2nwith initial conditions
a0= 1 and a1= 4. Find a closed-form expression for an.
29
Solution
Step 1: First, we solve the homogeneous part of the recurrence relation by
assuming an=a(h)
n. Thus, we have a(h)
n= 3a(h)
n−1−2a(h)
n−2.
Step 2: To find the characteristic equation, we substitute a(h)
n=rninto the
homogeneous part: rn= 3rn−1−2rn−2.
Step 3: Dividing by rn−2, we get r2= 3r−2, which simplifies to r2−3r+2 =
0. Factoring gives us (r−1)(r−2) = 0, so the characteristic roots are r= 1
and r= 2.
Step 4: The general solution to the homogeneous part is a(h)
n=c1·1n+c2·2n,
where c1and c2are constants to be determined.
Step 5: To find the particular solution, we assume a(p)
n=An ·2n, where A
is a constant to be determined.
Step 6: Substituting a(p)
ninto the original recurrence relation, we get An ·
2n= 3(An −1·2n−1)−2(An −2·2n−2)+2n.
Step 7: Simplifying and solving for A, we find A=−1. Therefore, the
particular solution to the non-homogeneous part is a(p)
n=−n·2n.
Step 8: Combining the homogeneous and particular solutions, we have the
general solution an=c1·1n+c2·2n−n·2n.
Step 9: Applying the initial conditions a0= 1 and a1= 4, we find c1=3
2
and c2=−1
2.
Step 10: Therefore, the closed-form expression for anis an=3
2−1
2·2n−n·2n.
Question 30
Question
Consider the following recurrence relation:
an= 5an−1−6an−2+ 2n, n ≥2
with initial conditions a0= 1 and a1= 3. Find a closed-form expression for
an.
Solution
To find a closed-form expression for an, we first need to solve the characteristic
equation associated with the homogeneous part of the recurrence relation.
Step 1: Write the characteristic equation The characteristic equation
for the homogeneous part is given by:
r2= 5r−6
This simplifies to:
r2−5r+ 6 = 0
Using the quadratic formula, we find the roots r1= 2 and r2= 3.
30
Step 2: Find the general solution for the homogeneous part The
general solution for the homogeneous part of the recurrence relation is:
an=c1·2n+c2·3n
Step 3: Find a particular solution for the non-homogeneous part
To find a particular solution for the non-homogeneous part 2n, we try a solution
of the form an=k·2n. Substituting this into the original recurrence relation,
we get:
k·2n= 5(k·2n−1)−6(k·2n−2)+2n
Solving for k, we find k=1
3.
Step 4: Write the general solution The general solution for the given
recurrence relation is:
an=c1·2n+c2·3n+1
3·2n
Step 5: Use initial conditions to find c1and c2Using the initial
conditions a0= 1 and a1= 3, we can set up a system of equations to solve for
c1and c2. This gives us:
c1+c2+1
3= 1
2c1+ 3c2+2
3= 3
Solving this system, we find c1=1
3and c2=2
3.
Step 6: Write the closed-form expression Finally, substituting c1=1
3
and c2=2
3into the general solution, we get:
an=1
3·2n+2
3·3n+1
3·2n=2
3·2n+2
3·3n
Therefore, the closed-form expression for anis an=2
3·2n+2
3·3n.
Question 31
Question
Consider the following non-homogeneous recurrence relation:
an= 3an−1+ 2n
where the initial condition is a0= 1. Determine the explicit formula for an.
31
Solution
To solve this non-homogeneous recurrence relation, we will first find the comple-
mentary function a(CF )
nby solving the associated homogeneous relation, then
find a particular solution a(P S)
n, and finally combine the two to get the general
solution.
Step 1: Find the complementary function a(CF )
nby solving the
associated homogeneous relation an= 3an−1.
The associated homogeneous relation is an= 3an−1, which is a first-order
linear homogeneous recurrence relation. Let’s assume the solution to this is of
the form a(CF )
n=rn.
Substitute a(CF )
n=rninto the homogeneous relation:
rn= 3rn−1
rn= 3rn
1=3
This equation has no solution, which means the homogeneous part has no
non-trivial solution.
Step 2: Find a particular solution a(P S)
nto the non-homogeneous
equation an= 3an−1+ 2n.
Since the particular part of the equation is 2n, let’s assume the particular
solution is of the form a(P S)
n=A·2n.
Substitute a(P S)
n=A·2ninto the original non-homogeneous relation:
A·2n= 3A·2n−1+ 2n
Divide by 2n:
A=3A
2+ 1
Solving for A, we get A=−2.
Therefore, the particular solution is a(P S)
n=−2·2n=−2n+1.
Step 3: Determine the general solution by combining the comple-
mentary function and the particular solution.
The general solution is:
an=a(CF )
n+a(P S)
n=a(CF )
n−2n+1
Since the homogeneous part has no non-trivial solution, the explicit formula
for anis an=−2n+1 .
Question 32
Question
Consider the non-homogeneous recurrence relation:
an= 2an−1−an−2+n, a0= 3, a1= 5.
32
Find a closed-form expression for an.
Solution
To find the closed-form expression for an, we first need to solve the associated
homogeneous recurrence relation and then find a particular solution to the non-
homogeneous recurrence relation.
Step 1: Solve the homogeneous recurrence relation We start by
considering the homogeneous part of the recurrence relation:
a(h)
n= 2a(h)
n−1−a(h)
n−2.
The characteristic equation is given by r2−2r+1 = 0, which factors as (r−1)2=
0. Thus, we have a repeated root r= 1.
Therefore, the general solution to the homogeneous recurrence relation is:
a(h)
n=c1·1n+c2·n·1n=c1+c2n.
Step 2: Find a particular solution to the non-homogeneous recur-
rence relation We will assume the particular solution has the form a(p)
n=
An +B. Substituting this into the non-homogeneous recurrence relation:
An +B= 2(A(n−1) + B)−A(n−2) −B+n.
Simplifying, we get:
An +B= 2An −2A+ 2B−An + 2A+B−B+n.
Which simplifies further to:
An +B=An + 2n.
Equating coefficients, we find A= 1 and B= 0.
Step 3: 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+ 1) + (c2+ 1)n.
Step 4: Find the values of c1and c2To find c1and c2, we use the initial
conditions a0= 3 and a1= 5:
a0= 3 ⇒c1+ 1 = 3 ⇒c1= 2,
a1= 5 ⇒c1+c2+ 1 = 5 ⇒2 + c2+ 1 = 5 ⇒c2= 2.
Step 5: Write the closed-form expression Thus, the closed-form ex-
pression for anis:
an= 2 + 1 + 2n= 3 + 2n.
33
Question 33
Question
Consider the non-homogeneous recurrence relation defined by an= 4an−1+ 3 ·
2n−1with initial condition a0= 1. Find the explicit formula for an.
Solution
Step 1: Find the homogeneous solution a(H)
nby solving the characteristic equa-
tion an= 4an−1. The characteristic equation is r= 4r, which has the solution
r= 4. Therefore, the homogeneous solution is a(H)
n=A·4n.
Step 2: Find a particular solution a(P)
nfor the non-homogeneous part of the
recursion. Guess a solution of the form a(P)
n=B·2n. Substituting into the
given recurrence relation, we get
B·2n= 4(B·2n−1)+3·2n−1.
Solving for B, we find B=3
2.
Step 3: The general solution for the recurrence relation is given by an=
a(H)
n+a(P)
n. Therefore, the general solution is an=A·4n+3
2·2n.
Step 4: Use the initial condition a0= 1 to solve for A. Substitute n= 0 and
a0= 1 into the general solution:
1 = A·40+3
2·20.
1 = A+3
2.
A=1
2.
Step 5: Finally, substitute A=1
2back into the general solution to get the
explicit formula for an. Thus, the explicit formula for anis
an=1
2·4n+3
2·2n.
Question 34
Question
Consider the non-homogeneous recurrence relation an= 3an−1−2an−2+ 2n
with initial conditions a0= 1 and a1= 2. Find a closed-form expression for an.
34
Solution
Step 1: First, find the characteristic equation by setting up the corresponding
homogeneous recurrence relation: an= 3an−1−2an−2. The characteristic
equation is r2−3r+ 2 = 0, which factors to (r−1)(r−2) = 0. Therefore, 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 a particular solution to the non-homogeneous part
of the recurrence relation. Since the non-homogeneous term is 2n, we guess
a particular solution of the form a(p)
n=C·2n, where Cis a constant to be
determined.
Step 4: Substitute a(p)
ninto the original recurrence relation and solve for C:
C·2n= 3(C·2n−1)−2(C·2n−2)+2n.
Step 5: Simplify the equation to solve for C:C·2n= 3C·2n−6C·2n−2+2n.
C=1
2.
Step 6: Therefore, the particular solution is a(p)
n=1
2·2n= 2n−1.
Step 7: The general solution to the non-homogeneous part of the recurrence
relation is the sum of the general solution to the homogeneous part and the
particular solution: an=a(h)
n+a(p)
n=A(1)n+B(2)n+ 2n−1.
Step 8: Apply the initial conditions a0= 1 and a1= 2: A+B+ 1 = 1 and
A+ 2B+ 2 = 2.
Step 9: Solve the system of equations to find Aand B: From the first
equation, we find A= 0. Substitute A= 0 into the second equation to find
B=1
2.
Step 10: Finally, the closed-form expression for anis: an=1
2·2n= 2n−1.
Question 35
Question
Let anbe defined recursively for all integers n≥1 as follows:
an= 2an−1−an−2+ 2n.
If a1= 1 and a2= 3, find a formula for anfor all n≥1.
Solution
To solve this recurrence relation, we first find the characteristic equation associ-
ated with the homogeneous part of the relation. The homogeneous part is given
by:
a(h)
n= 2an−1−an−2.
This gives us the characteristic equation r2−2r+ 1 = 0, which simplifies to
(r−1)2= 0. Thus, the characteristic root is r= 1 with multiplicity 2.
35
Therefore, the solution to the homogeneous part is:
a(h)
n=c1·1n+c2·n·1n=c1+c2n.
Next, we proceed to find a particular solution for the non-homogeneous part
of the relation. The non-homogeneous part is 2n, which is of the form P(n)=2n.
Since 2ndoes not match any term in the homogeneous solution, we assume a
particular solution of the form:
a(p)
n=An2n.
Substitute this into the original recurrence relation:
An2n= 2(A(n−1)2n−1)−A(n−2)2n−2+ 2n.
Simplify to find A=1
2. Thus, a particular solution is a(p)
n=1
2n2n.
Therefore, the general solution to the recurrence relation is:
an=a(h)
n+a(p)
n=c1+c2n+1
2n2n.
Using the initial conditions a1= 1 and a2= 3, we can solve for c1and c2:
1 = c1+c2,
3 = c1+ 2c2+ 2.
Solving these equations simultaneously gives us c1=7
4and c2=−3
4.
Therefore, the formula for anfor all n≥1 is:
an=7
4−3
4n+1
2n2n.
36
Solving for A, we get A= 0.
Therefore, the general solution for the non-homogeneous part of the recur-
rence relation is simply a(p)
n= 0.
Thus, the general solution for the entire recurrence relation is the sum of the
homogeneous and non-homogeneous solutions:
an=a(h)
n+a(p)
n=c1+c2n
Now, we use the initial conditions a0= 1 and a1= 2 to find c1and c2:
a0=c1= 1
a1=c1+c2= 2
Solving the above equations simultaneously, we find c1= 1 and c2= 1.
Therefore, the closed-form expression for anis given by:
an= 1 + n
Question 2
Question
Find the particular solution to the non-homogeneous recurrence relation an=
3an−1−2an−2+ 1 given that a0= 1 and a1= 2.
Solution
To find the particular solution of the non-homogeneous recurrence relation, we
will first find the general solution to the homogeneous part of the equation and
then find a particular solution to the non-homogeneous part.
Step 1: Find the roots of the characteristic equation by setting an=rn:
rn= 3rn−1−2rn−2
This simplifies to:
r2−3r+ 2 = 0
Factoring the quadratic equation gives us:
(r−1)(r−2) = 0
So the roots are r1= 1 and r2= 2.
Therefore, the general solution to the homogeneous part is:
a(h)
n=A(1)n+B(2)n
where Aand Bare constants to be determined.
2
Step 2: Find the particular solution to the non-homogeneous part: Let’s
assume the particular solution has the form a(p)
n=K(a constant).
Plugging the particular solution back into the non-homogeneous equation,
we get:
K= 3K−2K+ 1
K=K+ 1
0=1
This equation has no solution, meaning that a(p)
nis not a constant. We need
to try a(p)
n=Cn +D.
Plugging this into the non-homogeneous equation, we get:
Cn +D= 3(C(n−1) + D)−2(C(n−2) + D)+1
Cn +D= 3C(n−1) + 3D−2C(n−2) −2D+ 1
Simplify by expanding and combining like terms:
Cn +D=Cn + 3C−3C+ 2C+ 1
D= 2C+ 1
Therefore, the particular solution is:
a(p)
n= 2n+ 1
Step 3: Find the particular solution: The general solution will be the sum
of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n
an=A(1)n+B(2)n+ 2n+ 1
Using the initial conditions a0= 1 and a1= 2, we can solve for Aand B:
A+B+ 1 = 1
A(1) + B(2) + 3 = 2
Solving these equations gives A= 0 and B= 1, so the particular solution is:
an= 2n+ 2n+ 1
Question 3
Question
Let ansatisfy the recurrence relation an+2 −5an+1 + 6an= 0 for n≥0 with
initial conditions a0= 2 and a1= 3. Find a closed-form expression for an.
3
Solution
Step 1: First, we find the characteristic equation of the given recurrence relation.
We assume that the solution has the form an=rn. Substituting this into the
recurrence relation, we get:
rn+2 −5rn+1 + 6rn= 0
r2−5r+ 6 = 0
Step 2: We factor the quadratic equation to find its roots:
(r−2)(r−3) = 0
r1= 2, r2= 3
Step 3: The general solution to the recurrence relation is then:
an=c1·2n+c2·3n
Step 4: Using the initial conditions a0= 2 and a1= 3, we can solve for c1
and c2. Substitute n= 0 into an=c1·2n+c2·3n:
a0=c1·20+c2·30=c1+c2= 2
Step 5: Substitute n= 1 into an=c1·2n+c2·3n:
a1=c1·21+c2·31= 2c1+ 3c2= 3
Step 6: Solving the system of equations:
(c1+c2= 2
2c1+ 3c2= 3
Step 7: From the first equation, we get c1= 2 −c2. Substituting this into
the second equation, we find 2(2 −c2)+3c2= 3. Solving yields c1= 1, c2= 1.
Step 8: Therefore, the closed-form expression for anis:
an= 2n+ 3n
Question 4
Question
Let anbe defined recursively by the following recurrence relation:
an= 2an−1−2an−2+n
with initial conditions a0= 1 and a1= 2. Determine an explicit formula for an.
4
Solution
To find an explicit formula for an, we first solve the homogeneous version of
the recurrence relation. Then, we will find a particular solution for the non-
homogeneous part, and combine the two to get the general formula for an.
Step 1: Find the characteristic equation For the homogeneous part of
the recurrence relation, we consider the equation an= 2an−1−2an−2. We write
this as:
an−2an−1+ 2an−2= 0
The characteristic equation corresponding to this homogeneous recurrence rela-
tion is:
r2−2r+ 2 = 0
Solving this quadratic equation gives us complex roots r= 1 ±i.
Step 2: Find the general solution for the homogeneous part The
general solution for the homogeneous part of the recurrence relation is of the
form:
an=c1·(1 + i)n+c2·(1 −i)n
where c1and c2are constants to be determined.
Step 3: Find a particular solution for the non-homogeneous part
For the non-homogeneous part n, we will assume a linear form an=an +band
substitute it into the original recurrence relation to find aand b.
Substitute an=an +binto the original recurrence relation:
an +b= 2(an −1 + b)−2(an −2 + b) + n
This simplifies to:
an +b= 2an −2a+ 2b+n
Equating coefficients, we get the following system of equations:
2a= 2a, 2b−2a= 0
Solving this system gives a=1
2and b= 0.
Step 4: Determine the general formula for anThe general formula for
anis the sum of the general solution of the homogeneous part and the particular
solution of the non-homogeneous part:
an=c1·(1 + i)n+c2·(1 −i)n+1
2n
Step 5: Applying initial conditions To find c1and c2, we use the initial
conditions a0= 1 and a1= 2:
a0=c1+c2= 1
a1=c1(1 + i) + c2(1 −i) + 1
2= 2
Solving these equations will give us the specific values of c1and c2, providing
the final explicit formula for an.
5
Question 5
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
To find a closed-form expression for an, we need to solve the non-homogeneous
recurrence relation. We will begin by finding the homogeneous solution and
then the particular solution.
Step 1: Find the homogeneous solution
We start by assuming that the solution to the homogeneous recurrence re-
lation is of the form an=cn. Substitute this into the homogeneous part of the
original recurrence relation to get:
cn= 2cn−1−cn−2
Divide every term by cn−2:
c2= 2c−1
c2−2c+ 1 = 0
(c−1)2= 0
c= 1
Therefore, the homogeneous solution is an=k1+k2n.
Step 2: Find the particular solution
Since the non-homogeneous part of the recurrence relation is 2n, we assume
the particular solution to be of the form a(p)
n=A2n. Substitute a(p)
ninto the
original recurrence relation:
A2n= 2(A2n−1)−(A2n−2)+2n
A2n= 2A2n−A2n−2+ 2n
A= 2A−A
2n+ 1
A= 2A−A
4+ 1
3A
4= 1
A=4
3
Therefore, the particular solution is a(p)
n=4
3·2n.
Step 3: Find the general solution
6
The general solution is the sum of the homogeneous solution and the partic-
ular solution:
an=k1+k2n+4
3·2n
Step 4: Find the constants using initial conditions
Using the initial conditions a0= 1 and a1= 3:
k1+4
3= 1
k1=−1
3
k1+k2+8
3= 3
−1
3+k2+8
3= 3
k2=10
3
Therefore, the closed-form expression for anis:
an=−1
3+10
3n+4
3·2n
Question 6
Question
Consider the non-homogeneous recurrence relation given by: an= 4an−1−
4an−2+ 2nwith initial conditions a0= 1 and a1= 2. Determine the explicit
formula for an.
Solution
Step 1: First, solve the associated homogeneous recurrence relation an= 4an−1−
4an−2.
The characteristic equation is r2= 4r−4, which simplifies to r2−4r+4 = 0.
This can be factored as (r−2)2= 0, so we have a repeated root of r= 2.
Therefore, the solution to the homogeneous recurrence relation is of the form
a(h)
n= (c1+c2n)2n.
Step 2: Now, we will find a particular solution to the non-homogeneous
recurrence relation.
Since the non-homogeneous term is 2n, we will try a particular solution of
the form a(p)
n=An2n.
Substitute a(p)
ninto the recurrence relation: An2n= 4(A(n−1)2n−1)−
4(A(n−2)2n−2)+2n.
Simplify the above equation to find A=1
4.
7
Therefore, the particular solution is a(p)
n=1
4n2n.
Step 3: We can now write the general solution to the non-homogeneous
recurrence relation as the sum of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n= (c1+c2n)2n+1
4n2n.
Step 4: Apply the initial conditions a0= 1 and a1= 2 to solve for c1and
c2.
From a0= 1, we get c1= 1.
From a1= 2, we get c1+ 2c2+1
4·1·2 = 2. Simplifying this equation, we
find c2=3
8.
Step 5: Finally, substitute c1= 1 and c2=3
8back into the general solution
to get the explicit formula for an:
an= (1 + 3
4n)2n.
Question 7
Question
Let anbe a sequence defined recursively by the recurrence relation:
an= 3an−1−2an−2+ 2n
with initial conditions a0= 2 and a1= 5. Determine a closed-form expres-
sion for an.
Solution
Step 1: First, we find the characteristic equation of the homogeneous part of
the recurrence relation (an= 3an−1−2an−2). The characteristic equation is
obtained by replacing anwith λn:
λn= 3λn−1−2λn−2
Dividing through by λn−2:
λ2= 3λ−2
λ2−3λ+ 2 = 0
This quadratic equation can be factored as:
(λ−1)(λ−2) = 0
So, the characteristic roots are λ1= 1 and λ2= 2.
Step 2: The general solution to the homogeneous part of the recurrence
relation is then given by:
an=C1·1n+C2·2n
8
Simplifying, we get:
an=C1+C2·2n
Step 3: Next, we find a particular solution for the complete recurrence re-
lation with the form an=A·2n. Substitute an=A·2ninto the original
recurrence relation and solve for A:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
A·2n= 3A·2n−1−2A·2n−2+ 2n
A=2n
2
Step 4: The complete solution to the recurrence relation is then the sum of
the general and particular solutions:
an=C1+C2·2n+2n
2
Using the initial conditions a0= 2 and a1= 5, we can solve for C1and C2:
a0=C1+C2= 2
a1=C1+ 2C2+ 1 = 5
Solving these equations, we find C1= 1 and C2= 1.
Therefore, the closed-form expression for anis:
an= 1 + 2n+2n
2= 1 + 3·2n
2
Question 8
Question
Consider the non-homogeneous linear recurrence relation given by: an= 2an−1−
an−2+n2+ 2n+ 1. If the initial conditions are a0= 1 and a1= 3, find a closed-
form expression for an.
Solution
To solve the non-homogeneous linear recurrence relation, we first need to find
the general solution for the associated homogeneous relation, an= 2an−1−an−2.
Let ah
nrepresent the homogeneous part of the solution, and let ap
nrepresent a
particular solution of the non-homogeneous equation.
9
Step 1: Find the homogeneous solution Consider the characteristic
equation r2= 2r−1. Solving for r, we get r= 1 and r=−1. Therefore, the
general solution to the homogeneous equation is:
ah
n=c1·1n+c2·(−1)n=c1+ (−1)n·c2
Step 2: Find a particular solution We try a particular solution of the
form ap
n=An2+Bn +C. Substituting this form into the non-homogeneous
equation and simplifying, we get:
An2+Bn +C= 2(An2+B(n−1)+C)−(A(n−1)2+B(n−1)+C)+n2+2n+1
An2+Bn +C= 2An2+ 2Bn −2A+n2+ 2n+ 1
Equating coefficients of like terms, we get the following system of equations:
2A=A=⇒A= 0
2B= 2B+ 2 =⇒0 = 2
−2A= 1 =⇒A=−1
2
Therefore, the particular solution is ap
n=−1
2n2+Bn +C
Step 3: Find the full solution Combining the homogeneous and partic-
ular solutions, we get:
an=ah
n+ap
n=c1+ (−1)n·c2−1
2n2+Bn +C
Step 4: Use initial conditions to find constants Given initial conditions
a0= 1 and a1= 3, we can substitute and solve for the constants c1,c2,B, and
C. We find:
a0=c1+c2= 1
a1=c1−c2−1
2+B+C= 3
Solving these equations simultaneously, we get c1= 2, c2=−1, B=3
2, and
C=5
2.
Step 5: Final solution Plugging the values of c1,c2,B, and Cback into
the full solution, we get the closed-form expression for an:
an= 2 + (−1)n−1
2n2+3
2n+5
2
Question 9
Question
Consider the non-homogeneous recurrence relation given by
an= 2an−1−an−2+n,
with initial conditions a0= 0 and a1= 1. Find a closed-form expression for an.
10
Solution
To find a closed-form expression for an, we first need to solve the associated
homogeneous recurrence relation an= 2an−1−an−2and then find a particular
solution for the non-homogeneous part n.
Step 1: Solve the homogeneous recurrence relation The characteristic
equation for the homogeneous part is r2= 2r−1, which simplifies to r2−2r+1 =
(r−1)2= 0. This gives a repeated root r= 1.
Therefore, the solution to the homogeneous recurrence relation is a(h)
n=
c1·1n+c2·n·1n=c1+c2n.
Step 2: Find a particular solution for the non-homogeneous part
Since the non-homogeneous part is a linear function n, we try a particular
solution of the form a(p)
n=An+B. Substituting this into the original recurrence
relation, we get:
An +B= 2(A(n−1) + B)−A(n−2) −B+n.
Solving for Aand Bgives A=−1 and B= 0.
Therefore, the particular solution is a(p)
n=−n.
Step 3: 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+c2n−n.
Step 4: Use initial conditions to find c1and c2Using the initial
conditions a0= 0 and a1= 1, we have:
c1+c2·0−0=0, c1+c2·1−1 = 1.
Solving these equations gives c1= 1 and c2= 1.
Step 5: Write the closed-form expression for anTherefore, the closed-
form expression for anis:
an= 1 + n−n= 1.
Question 10
Question
Consider the following non-homogeneous recurrence relation:
an= 2an−1−an−2+ 2n
with initial conditions a0= 1 and a1= 2. Find a closed-form expression for
an.
11
Solution
To solve this non-homogeneous recurrence relation, we first need to find the
general form of the solution to the associated homogeneous recurrence relation.
Let ah
nbe the homogeneous solution. The associated homogeneous recurrence
relation is:
ah
n= 2an−1−an−2
Step 1: Find the characteristic equation by assuming ah
n=rn:
Substitute ah
n=rninto the homogeneous recurrence relation:
rn= 2rn−1−rn−2
Divide by rn−2to simplify:
r2= 2r−1
The characteristic equation is r2−2r+ 1 = (r−1)2= 0. This gives us a
repeated root r= 1.
Step 2: Find the form of the homogeneous solution ah
n:
Since r= 1 is a repeated root, the form of the homogeneous solution is:
ah
n= (A+Bn)·1n=A+Bn
Step 3: Find a particular solution to the non-homogeneous recurrence re-
lation:
Let’s guess a particular solution of the form ap
n=C·2n, where Cis a
constant to be determined.
Substitute this form into the non-homogeneous recurrence relation:
C·2n= 2(C·2n−1)−(C·2n−2)+2n
This simplifies to C= 1. Therefore, ap
n= 2nis a particular solution.
Step 4: Find the general solution an:
The general solution is the sum of the homogeneous and particular solutions:
an=ah
n+ap
n=A+Bn + 2n
Step 5: Use the initial conditions to find Aand B:
a0=A+B·0+20=A= 1
a1=A+B+ 21=A+B+ 2 = 2
From the above equations, we find A= 1 and B=−1. Therefore, the
closed-form expression for anis:
an= 1 −n+ 2n
12
Question 11
Question
Consider the non-homogeneous recurrence relation given by:
an= 3an−1−2an−2+ 2n
Given that a0= 1 and a1= 3, find an explicit formula for an.
Solution
To find an explicit formula for an, we first need to find the homogeneous solution
a(H)
nand the particular solution a(P)
n.
Step 1: Find the homogeneous solution a(H)
nThe associated homoge-
neous recurrence relation is: an= 3an−1−2an−2. Let’s assume the homogeneous
solution has the form: a(H)
n=rn.
Substitute a(H)
n=rninto the homogeneous recurrence relation:
rn= 3rn−1−2rn−2
Divide by rn−2:
r2= 3r−2
r2−3r+ 2 = 0
This quadratic equation has roots r= 1 and r= 2. Therefore, the homogeneous
solution is:
a(H)
n=c1·1n+c2·2n=c1+c2·2n
Step 2: Find the particular solution a(P)
nLet’s assume the particular
solution has the form: a(P)
n=A·2n. Substitute a(P)
n=A·2ninto the non-
homogeneous recurrence relation:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
A=3
2A−1
2A+ 1
A=2
2= 1
Therefore, the particular solution is:
a(P)
n= 2n
Step 3: Find the general solution anThe general solution is the sum of
the homogeneous and particular solutions:
an=a(H)
n+a(P)
n=c1+c2·2n+ 2n
13
Step 4: Use initial conditions to find c1and c2Using the initial
conditions a0= 1 and a1= 3:
a0=c1+c2= 1
a1=c1+ 2c2+ 2 = 3
Solving these equations, we find c1= 1 and c2= 1.
Step 5: Write the explicit formula for anTherefore, the explicit formula
for anis:
an= 1 + 2n+ 2n
Question 12
Question
Let anbe the sequence defined by the recurrence relation an+2 = 4an+1 −4an,
where a0= 1 and a1= 3. Find a closed form expression for an.
Solution
Given: ansatisfies the recurrence relation an+2 = 4an+1 −4an, with initial
conditions a0= 1 and a1= 3.
Step 1: Find the characteristic equation. Let’s assume an=rnis a solution
to the recurrence relation. Substituting this into the recurrence relation, we get:
rn+2 = 4rn+1 −4rn
Dividing by rn(since r= 0), we get:
r2= 4r−4
r2−4r+ 4 = 0
(r−2)2= 0
r= 2,2
So, the characteristic equation is (r−2)2= 0.
Step 2: Find the general form of the solution. Since we have a repeated
root, the general solution will be of the form:
an= (c1+c2n)·2n
Step 3: Use initial conditions to solve for c1and c2. Given a0= 1 and
a1= 3:
a0= 1 = (c1)·20⇒c1= 1
a1= 3 = (c1+c2)·21⇒c1+c2= 3
14
Substitute c1= 1 into the second equation:
1 + c2= 3
c2= 2
Step 4: Write the closed form expression. Therefore, the closed form ex-
pression for anis:
an= 2n+ 2n·2n
Question 13
Question
Consider the homogeneous recurrence relation given by an+2 −3an+1 + 2an= 0
for n≥0, with initial conditions a0= 1 and a1= 2. Find a closed-form
expression for an.
Solution
Step 1: First, find the characteristic equation of the homogeneous recurrence
relation. The characteristic equation is r2−3r+ 2 = 0. Solve this quadratic
equation:
r=3±√32−4·1·2
2·1=3±√1
2
r=3±1
2= 2,1
Step 2: The general solution to the homogeneous recurrence relation is of
the form:
an=c1·2n+c2·1n=c1·2n+c2
Step 3: Use the initial conditions a0= 1 and a1= 2 to find the values of c1
and c2.
a0=c1·20+c2=c1+c2= 1
a1=c1·21+c2= 2c1+c2= 2
Step 4: Solve the system of equations formed by c1+c2= 1 and 2c1+c2= 2.
Subtract the first equation from the second:
c1= 1
Step 5: Substitute c1= 1 back into c1+c2= 1 to find c2:
1 + c2= 1 ⇒c2= 0
Step 6: The closed-form expression for anis:
an= 2n
15
Question 14
Question
Consider the following homogeneous recurrence relation:
an+3 + 3an+2 −4an+1 −4an= 0
with initial conditions a0= 1, a1= 2,and a2= 3. Find a closed-form expression
for an.
Solution
To solve the given homogeneous recurrence relation, we first need to find the
characteristic equation. Let’s assume an=rnand substitute it into the recur-
rence relation:
Step 1: Substitute an=rninto the recurrence relation:
rn+3 + 3rn+2 −4rn+1 −4rn= 0
Step 2: Divide the equation by rnand simplify:
r3+ 3r2−4r−4 = 0
Step 3: Factor the polynomial to find the roots:
(r+ 1)(r−1)2= 0
This gives us roots r1=−1 and r2= 1 with multiplicity 2.
Step 4: The general solution to the recurrence relation is:
an=C1(−1)n+C2n(−1)n+C3(1)n
where C1, C2,and C3are constants to be determined using initial conditions.
Step 5: Use the initial conditions to find the values of C1, C2,and C3:
a0= 1 : C1+C3= 1
a1= 2 : −C1+C2+C3= 2
a2=3:C1−2C2+C3= 3
Step 6: Solve the system of equations to find C1, C2,and C3: Solving the
system of equations, we find C1= 0, C2=−1,and C3= 1.
Step 7: Substitute the constants back into the general solution:
an=−n(−1)n+ (−1)n
So, the closed-form expression for anis an=−n(−1)n+ (−1)n.
16
Question 15
Question
Consider the following non-homogeneous recurrence relation:
an=an−1+ 2n
If the initial condition is a0= 1, find the explicit formula for an.
Solution
To solve this non-homogeneous recurrence relation, we first need to find the
solutions to the corresponding homogeneous relation by setting the right-hand
side to 0. Then, we will find a particular solution to the non-homogeneous part
and combine it with the homogeneous solutions to get the general solution.
Step 1: Find the homogeneous solution We consider the homogeneous
part of the recurrence relation:
an=an−1
This is a simple linear recurrence relation with characteristic equation:
r−1=0
r= 1
So, the homogeneous solution is a(H)
n=c·1n=c, where cis a constant.
Step 2: Find a particular solution For the non-homogeneous part of the
recurrence relation 2n, we assume a particular solution of the form a(P)
n=A·2n.
Substituting this into the original recurrence relation:
A·2n=A·2n−1+ 2n
Solving for A, we get A=−1.
So, the particular solution is a(P)
n=−2n.
Step 3: Find the general solution The general solution is the sum of
the homogeneous and particular solutions:
an=a(H)
n+a(P)
n
an=c−2n
Step 4: Find the value of cUsing the initial condition a0= 1, we have:
1 = c−20
c= 2
Step 5: Write the explicit formula for anThus, the explicit formula
for anis:
an= 2 −2n
17
Question 16
Question
Let anbe the nth term of a sequence defined by the recurrence relation an=
2an−1+ 3an−2for n≥2, with initial conditions a0= 1 and a1= 2. Find a
closed-form expression for an.
Solution
Step 1: Find the characteristic equation of the given recurrence relation. The
characteristic equation is obtained by setting the terms of the recurrence relation
without the subscripts to zero. For this recurrence relation, the characteristic
equation is:
r2= 2r+ 3
Step 2: Solve the characteristic equation to find the roots. To solve, we
rewrite the equation as r2−2r−3 = 0 and factorize it:
(r−3)(r+ 1) = 0
This gives us roots r1= 3 and r2=−1.
Step 3: Write the general solution of the recurrence relation. Since the roots
r1= 3 and r2=−1 are distinct, the general solution is of the form:
an=c1(3)n+c2(−1)n
where c1and c2are constants to be determined.
Step 4: Use the initial conditions a0= 1 and a1= 2 to find the values of
c1and c2. Substituting n= 0 and n= 1 into the general solution, we get the
following system of equations:
(c1+c2= 1
3c1−c2= 2
Step 5: Solve the system of equations to find c1and c2. Adding the two
equations gives 4c1= 3, so c1=3
4. Substituting back, we find c2=1
4.
Step 6: Substitute the values of c1and c2back into the general solution to
obtain the closed-form expression for an:
an=3
4·3n+1
4·(−1)n
Question 17
Question
Consider the following second order homogeneous recurrence relation: an=
2an−1−an−2with initial conditions a0= 1 and a1= 3. Find a closed-form
expression for an.
18
Solution
Step 1: Find the characteristic equation of the recurrence relation. The charac-
teristic equation is given by:
r2= 2r−1
r2−2r+ 1 = 0
(r−1)2= 0
r= 1 (double root)
Step 2: Write the general solution for the recurrence relation. Since we have
a double root, the general solution can be written as:
an= (c1+c2n)1n
an=c1+c2n
Step 3: Use the initial conditions to find the values of c1and c2. From
a0= 1:
1 = c1
From a1= 3:
3 = c1+c2
Solving these equations simultaneously, we find c1= 1 and c2= 2.
Step 4: Write the closed-form expression for an. Substitute the values of c1
and c2back into an=c1+c2n:
an= 1 + 2n
Question 18
Question
Let anbe defined recursively by the recurrence relation an= 3an−1−2an−2,
where a0= 1 and a1= 2. Find an explicit formula for an.
Solution
To find an explicit formula for an, we first need to find the characteristic equation
associated with the given recurrence relation. Let an=rnbe a solution to the
recurrence relation. Substituting this into the recurrence relation gives
rn= 3rn−1−2rn−2.
Dividing both sides by rn−2(assuming r= 0) gives the characteristic equa-
tion
r2= 3r−2.
19
Step 1: Find the roots of the characteristic equation. Solving r2= 3r−2
gives
r2−3r+ 2 = 0.
Factoring the quadratic equation, we get
(r−1)(r−2) = 0.
So the roots are r= 1 and r= 2.
Step 2: Write the general solution. Since the roots are distinct, the general
solution to the recurrence relation is
an=A(1)n+B(2)n,
where Aand Bare constants to be determined.
Step 3: Use the initial conditions to determine Aand B. Given a0= 1 and
a1= 2, we can set up a system of equations:
a0=1:A+B= 1,
a1=2:A+ 2B= 2.
Solving this system of equations gives A= 0 and B= 1.
Step 4: Write the explicit formula for an. Therefore, the explicit formula
for anis
an= 2n.
Question 19
Question
Consider the recurrence relation an= 3an−1−2an−2with initial conditions
a0= 1 and a1= 2. Find a closed-form expression for an.
Solution
To solve the recurrence relation, we first need to find the characteristic equation
by assuming a solution of the form an=rn. Substituting this into the recurrence
relation gives us:
rn= 3rn−1−2rn−2
Dividing by rn−2(since rncannot be zero) gives:
r2= 3r−2
This simplifies to:
r2−3r+ 2 = 0
Now we solve this quadratic equation to find the roots r1and r2:
(r−1)(r−2) = 0
20
r1= 1, r2= 2
So, the general solution to the homogeneous recurrence relation is:
a(h)
n=Arn
1+Brn
2=A(1)n+B(2)n=A+ 2nB
Next, we need to find a particular solution. Since the recurrence relation
is linear and non-homogeneous, we can try a particular solution of the form
an=k(a constant). Substituting this into the recurrence relation gives:
k= 3k−2k
k=k
This particular solution satisfies the recurrence relation.
Therefore, the general solution to the non-homogeneous recurrence relation
is:
an=a(h)
n+a(p)
n=A+ 2nB+k
Using the initial conditions a0= 1 and a1= 2, we can solve for A,B, and
k:
a0=A+B= 1
a1=A+ 2B+ 2 = 2
Solving these equations gives A= 0, B= 1, and k= 1.
Therefore, the closed-form expression for anis:
an= 2n+ 1
Question 20
Question
Consider the following recurrence relation:
an= 7an−1−10an−2+ 3 for n≥2
where a0= 1 and a1= 4. Find the explicit formula for an.
Solution
To find the explicit formula for an, we first solve the characteristic equation
associated with the homogeneous part of the recurrence relation.
Step 1: Find the characteristic equation
For a homogeneous recurrence relation of the form an=can−1+dan−2, the
characteristic equation is r2−cr −d= 0.
In this case, c= 7 and d=−10, so the characteristic equation is r2−7r+10 =
0.
Step 2: Solve the characteristic equation
21
Factoring the characteristic equation, we get (r−5)(r−2) = 0. So, the roots
are r1= 5 and r2= 2.
Step 3: Write down the homogeneous solution
The general form of the homogeneous solution is a(h)
n=A·5n+B·2n, where
Aand Bare constants to be determined.
Step 4: Find particular solution for the non-homogeneous part
For the non-homogeneous part 3, we assume a particular solution of the form
a(p)
n=k.
Substitute a(h)
nand a(p)
nback into the original recurrence relation to solve
for k:
k= 7k−10k+ 3
−2k= 3
k=−3
2
Step 5: Write down the general solution
The general solution is the sum of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=A·5n+B·2n−3
2
Step 6: Use initial conditions to find Aand B
Using the initial conditions a0= 1 and a1= 4:
a0=A·50+B·20−3
2= 1
A+B−3
2= 1
a1=A·51+B·21−3
2= 4
5A+ 2B−3
2= 4
Solving these equations simultaneously, we find A=11
4and B=−7
4.
Step 7: Write down the explicit formula for an
Therefore, the explicit formula for anis:
an=11
4·5n−7
4·2n−3
2
Question 21
Question
Let’s consider the sequence defined by the recurrence relation:
an+2 −5an+1 + 6an= 2n
with initial conditions a0= 1 and a1= 3. Determine the explicit formula
for an.
22
Solution
To solve this recurrence relation, we first solve the homogeneous version:
an+2 −5an+1 + 6an= 0
Step 1: Find the characteristic equation Let an=rn. Substitute this
into the homogeneous equation:
r2−5r+ 6 = 0
The characteristic equation is r2−5r+6 = 0, which factors to (r−2)(r−3) = 0.
So r1= 2 and r2= 3.
Step 2: Find the homogeneous solution The homogeneous solution is
of the form:
an=Arn
1+Brn
2
Plugging in r1= 2 and r2= 3, we get:
an=A(2n) + B(3n)
Step 3: Find coefficients using initial conditions Given a0= 1 and
a1= 3, we can set up a system of equations:
(A+B= 1
2A+ 3B= 3
Solving this system, we find A= 1 and B= 0.
Step 4: Write down the general solution Therefore, the general solution
to the homogeneous equation is:
an= 2n
Step 5: Find the particular solution Now we need to find a particular
solution to the original non-homogeneous equation. Since the right-hand side is
2n, we can try a particular solution of the form an=cn2n. Substituting this
into the equation, we get:
c(2n+2)−5c(2n+1)+6c(2n)=2n
c2n+2 −5c2n+1 + 6c2n= 2n
2c−10c+ 6c= 1
−2c= 1
c=−1
2
Step 6: Write down the complete solution Therefore, the complete
solution to the original non-homogeneous equation is:
an= 2n−1
2n2n
23
Question 22
Question
Let anbe defined by the recurrence relation an= 2an−1+ 3an−2for n≥2
with initial conditions a0= 1 and a1= 3. Find a formula for anfor all integers
n≥0.
Solution
Step 1: Find the characteristic equation
We can rewrite the recurrence relation as an−2an−1−3an−2= 0. The charac-
teristic equation is then r2−2r−3 = 0.
Step 2: Solve the characteristic equation
Factoring the characteristic equation, we have (r−3)(r+ 1) = 0. So, the roots
are r= 3 and r=−1.
Step 3: Write the general solution
Since we have distinct real roots, the general solution to the homogeneous part
of the recurrence relation is
an=A(3)n+B(−1)n.
Step 4: Use the initial conditions to find the values of Aand B
Substitute the initial conditions a0= 1 and a1= 3 into the general solution.
We get the equations:
(A+B= 1
3A−B= 3 .
Solving this system of equations, we find A= 1 and B= 0.
Step 5: Write the final formula
Therefore, the formula for anis
an= (3)n.
Question 23
Question
Consider the non-homogeneous recurrence relation defined by an= 2an−1+ 2n
with initial condition a0= 1. Find a closed-form expression for an.
Solution
To solve this non-homogeneous recurrence relation, we will first find the gen-
eral solution of the corresponding homogeneous relation, then find a particular
solution for the non-homogeneous part, and finally sum them up to obtain the
complete solution.
24
Step 1: Find the general solution
Let’s first write the homogeneous part of the recurrence relation:
an−2an−1= 0
This gives us the characteristic equation:
r−2=0
r= 2
Therefore, the general solution for the homogeneous part is:
a(h)
n=c·2n
Step 2: Find a particular solution
Now, we need to find a particular solution for the non-homogeneous part,
which is of the form a(p)
n=k·2n. Substituting this into the original recurrence
relation gives:
k·2n= 2(k·2n−1)+2n
k= 1
Therefore, a particular solution is a(p)
n= 2n.
Step 3: Find the complete solution
The complete solution is the sum of the general and particular solutions:
an=a(h)
n+a(p)
n
an=c·2n+ 2n
Step 4: Apply the initial condition
Using the initial condition a0= 1, we have:
a0=c·20+ 20=c+ 1 = 1
c= 0
Thus, the closed-form expression for anis:
an= 2n
Question 24
Question
Find a closed-form expression for the non-homogeneous recurrence relation de-
fined by an= 3an−1−2an−2+ 2nwith initial conditions a0= 1 and a1= 3.
25
Solution
Step 1: First, find the characteristic equation of the related homogeneous recur-
rence relation: an= 3an−1−2an−2. The characteristic equation is r2−3r+2 = 0,
which factors to (r−1)(r−2) = 0. Therefore, the characteristic roots are r1= 1
and r2= 2.
Step 2: Since the roots are distinct, the general solution to the homogeneous
recurrence relation is a(h)
n=A(1)n+B(2)n, where Aand Bare constants to be
determined.
Step 3: Next, we find a particular solution a(p)
nto the non-homogeneous
recurrence relation an= 3an−1−2an−2+ 2n. Since 2nis of the same form as
the non-homogeneity, we try a particular solution of the form a(p)
n=C(2)n,
where Cis a constant to be determined.
Step 4: Substitute a(p)
n=C(2)ninto the recurrence relation to get C(2)n=
3C(2)n−1−2C(2)n−2+ 2n. Dividing by 2n−2, we get 4C= 6C−2C+ 4, from
which we find that C=−2
3.
Step 5: The general solution to the non-homogeneous recurrence relation is
then the sum of the solutions to the homogeneous and particular parts: an=
a(h)
n+a(p)
n=A(1)n+B(2)n−2
3(2)n.
Step 6: Using the initial conditions a0= 1 and a1= 3, we plug these
values into the general solution to solve for Aand B:A+B−2
3= 1 and
A(1) + B(2) −2
3(2) = 3. Solving these equations gives A=5
3and B=1
3.
Step 7: Therefore, the closed-form expression for the non-homogeneous re-
currence relation is an=5
3(1)n+1
3(2)n−2
3(2)n. Simplifying this further gives
an=1
3(2n+ 2).
Thus, the solution to the non-homogeneous recurrence relation is an=
1
3(2n+ 2).
Question 25
Question
Let anbe defined by the recurrence relation an= 2an−1−an−2for n≥2, with
initial conditions a0= 1 and a1= 2. Find a formula for anfor n≥0.
Solution
Step 1: Find the characteristic equation by assuming a solution of the form
an=rn. The recurrence relation an= 2an−1−an−2can be rewritten as
r2= 2r−1, which simplifies to r2−2r+ 1 = 0. This quadratic equation factors
as (r−1)2= 0, so r= 1 is a repeated root.
Step 2: Write the general solution to the recurrence relation. Since r= 1 is
a repeated root, the general solution has the form an= (c1+c2n)1n=c1+c2n.
Step 3: Use the initial conditions a0= 1 and a1= 2 to find the values of
c1and c2. From a0= 1, we have c1= 1. From a1= 2, we have c1+c2= 2.
Substituting c1= 1, we find 1 + c2= 2, so c2= 1.
26
Step 4: Write the final formula for an. Therefore, the formula for anis
an= 1 + n.
Question 26
Question
Consider the following recurrence relation:
an+2 −4an+1 + 4an= 0
Given that a0= 2 and a1= 5, find a closed-form expression for an.
Solution
To find a closed-form expression for an, we first need to solve the characteristic
equation associated with the recurrence relation.
Step 1: Write down the characteristic equation
The characteristic equation for the given recurrence relation is:
r2−4r+ 4 = 0
Step 2: Solve the characteristic equation
Factoring the characteristic equation gives:
(r−2)2= 0
So, we have a repeated root r= 2.
Step 3: Write down the general solution
The general solution for the recurrence relation is of the form:
an=c1·2n+c2·n·2n
Step 4: Use initial conditions to find c1and c2
Using the initial conditions a0= 2 and a1= 5:
(c1+ 0 = 2
c1·2+2c2·2 = 5
Solving this system of equations gives c1= 2 and c2=3
2.
Step 5: Final closed-form expression for an
Substitute c1= 2 and c2=3
2into the general solution:
an= 2 ·2n+3
2·n·2n= 2n+1 +3n·2n
2
Therefore, the closed-form expression for anis an= 2n+1 +3n·2n
2.
27
Question 27
Question
Let (an) be a sequence defined by the recurrence relation an+1 = 3an+ 2, with
initial condition a0= 2. Determine a closed-form expression for an.
Solution
To solve the given recurrence relation, we first need to find the characteristic
equation associated with it. The characteristic equation is given by setting the
coefficient of anto 1: r−3 = 0. Solving this equation gives r= 3.
Step 1: The general solution for the homogeneous part of the recurrence
relation is of the form a(h)
n=c·3n, where cis a constant to be determined.
Step 2: Next, we need to find a particular solution a(p)
nto the non-homogeneous
part of the recurrence relation an+1 = 3an+ 2. Since the right-hand side is a
constant, we try a constant solution: a(p)
n=k, where kis a constant to be
determined.
Step 3: Substituting a(h)
nand a(p)
nback into the original recurrence relation,
we get:
k= 3k+ 2
Solving this equation gives k=−2.
Step 4: Therefore, the general solution to the non-homogeneous part of the
recurrence relation is a(p)
n=−2.
Step 5: Combining the solutions to the homogeneous and non-homogeneous
parts, we have an=a(h)
n+a(p)
n=c·3n−2.
Step 6: To find the value of the constant c, we use the initial condition
a0= 2.
2 = c·30−2 = c−2
Solving this equation gives c= 4.
Step 7: Therefore, the closed-form expression for the sequence (an) is an=
4·3n−2.
Question 28
Question
Consider the non-homogeneous recurrence relation defined by:
an+2 = 3an+1 −4an+ 2n, a0= 1, a1= 2
Find a closed-form expression for an.
28
Solution
To find the closed-form expression for an, we first solve the corresponding ho-
mogeneous recurrence relation:
an+2 = 3an+1 −4an
This characteristic equation is r2= 3r−4, which simplifies to r2−3r+ 4 = 0.
The roots of this characteristic equation are complex, 3±√32−4·4
2=3±i√7
2.
So, the general form of the solution to the homogeneous part of the recur-
rence relation is:
an=c1 3 + i√7
2!n
+c2 3−i√7
2!n
Next, we find a particular solution to the non-homogeneous recurrence re-
lation. We assume the particular solution has the form a(p)
n=An2nwhere A
is a constant to be determined. Substituting this into the non-homogeneous
recurrence relation, we get:
An2n+2 = 3An2n+1 −4An2n+ 2n
A2n+2 = 3A2n+1 −4A2n+ 2n
4A2n= 6A2n−4A2n+ 2n
A= 2−2=1
4
So, the particular solution is a(p)
n=1
4n2n.
Therefore, the general solution to the non-homogeneous recurrence relation
is:
an=c1 3 + i√7
2!n
+c2 3−i√7
2!n
+1
4n2n
Using the initial conditions a0= 1 and a1= 2, we can find the values of c1
and c2:
a0=c1+c2= 1
a1=c1 3 + i√7
2!+c2 3−i√7
2!+ 2 = 2
Solving these equations will give us the values of c1and c2, leading to the
final closed-form expression for an.
Question 29
Question
Consider the recurrence relation an= 3an−1−2an−2+2nwith initial conditions
a0= 1 and a1= 4. Find a closed-form expression for an.
29
Solution
Step 1: First, we solve the homogeneous part of the recurrence relation by
assuming an=a(h)
n. Thus, we have a(h)
n= 3a(h)
n−1−2a(h)
n−2.
Step 2: To find the characteristic equation, we substitute a(h)
n=rninto the
homogeneous part: rn= 3rn−1−2rn−2.
Step 3: Dividing by rn−2, we get r2= 3r−2, which simplifies to r2−3r+2 =
0. Factoring gives us (r−1)(r−2) = 0, so the characteristic roots are r= 1
and r= 2.
Step 4: The general solution to the homogeneous part is a(h)
n=c1·1n+c2·2n,
where c1and c2are constants to be determined.
Step 5: To find the particular solution, we assume a(p)
n=An ·2n, where A
is a constant to be determined.
Step 6: Substituting a(p)
ninto the original recurrence relation, we get An ·
2n= 3(An −1·2n−1)−2(An −2·2n−2)+2n.
Step 7: Simplifying and solving for A, we find A=−1. Therefore, the
particular solution to the non-homogeneous part is a(p)
n=−n·2n.
Step 8: Combining the homogeneous and particular solutions, we have the
general solution an=c1·1n+c2·2n−n·2n.
Step 9: Applying the initial conditions a0= 1 and a1= 4, we find c1=3
2
and c2=−1
2.
Step 10: Therefore, the closed-form expression for anis an=3
2−1
2·2n−n·2n.
Question 30
Question
Consider the following recurrence relation:
an= 5an−1−6an−2+ 2n, n ≥2
with initial conditions a0= 1 and a1= 3. Find a closed-form expression for
an.
Solution
To find a closed-form expression for an, we first need to solve the characteristic
equation associated with the homogeneous part of the recurrence relation.
Step 1: Write the characteristic equation The characteristic equation
for the homogeneous part is given by:
r2= 5r−6
This simplifies to:
r2−5r+ 6 = 0
Using the quadratic formula, we find the roots r1= 2 and r2= 3.
30
Step 2: Find the general solution for the homogeneous part The
general solution for the homogeneous part of the recurrence relation is:
an=c1·2n+c2·3n
Step 3: Find a particular solution for the non-homogeneous part
To find a particular solution for the non-homogeneous part 2n, we try a solution
of the form an=k·2n. Substituting this into the original recurrence relation,
we get:
k·2n= 5(k·2n−1)−6(k·2n−2)+2n
Solving for k, we find k=1
3.
Step 4: Write the general solution The general solution for the given
recurrence relation is:
an=c1·2n+c2·3n+1
3·2n
Step 5: Use initial conditions to find c1and c2Using the initial
conditions a0= 1 and a1= 3, we can set up a system of equations to solve for
c1and c2. This gives us:
c1+c2+1
3= 1
2c1+ 3c2+2
3= 3
Solving this system, we find c1=1
3and c2=2
3.
Step 6: Write the closed-form expression Finally, substituting c1=1
3
and c2=2
3into the general solution, we get:
an=1
3·2n+2
3·3n+1
3·2n=2
3·2n+2
3·3n
Therefore, the closed-form expression for anis an=2
3·2n+2
3·3n.
Question 31
Question
Consider the following non-homogeneous recurrence relation:
an= 3an−1+ 2n
where the initial condition is a0= 1. Determine the explicit formula for an.
31
Solution
To solve this non-homogeneous recurrence relation, we will first find the comple-
mentary function a(CF )
nby solving the associated homogeneous relation, then
find a particular solution a(P S)
n, and finally combine the two to get the general
solution.
Step 1: Find the complementary function a(CF )
nby solving the
associated homogeneous relation an= 3an−1.
The associated homogeneous relation is an= 3an−1, which is a first-order
linear homogeneous recurrence relation. Let’s assume the solution to this is of
the form a(CF )
n=rn.
Substitute a(CF )
n=rninto the homogeneous relation:
rn= 3rn−1
rn= 3rn
1=3
This equation has no solution, which means the homogeneous part has no
non-trivial solution.
Step 2: Find a particular solution a(P S)
nto the non-homogeneous
equation an= 3an−1+ 2n.
Since the particular part of the equation is 2n, let’s assume the particular
solution is of the form a(P S)
n=A·2n.
Substitute a(P S)
n=A·2ninto the original non-homogeneous relation:
A·2n= 3A·2n−1+ 2n
Divide by 2n:
A=3A
2+ 1
Solving for A, we get A=−2.
Therefore, the particular solution is a(P S)
n=−2·2n=−2n+1.
Step 3: Determine the general solution by combining the comple-
mentary function and the particular solution.
The general solution is:
an=a(CF )
n+a(P S)
n=a(CF )
n−2n+1
Since the homogeneous part has no non-trivial solution, the explicit formula
for anis an=−2n+1 .
Question 32
Question
Consider the non-homogeneous recurrence relation:
an= 2an−1−an−2+n, a0= 3, a1= 5.
32
Find a closed-form expression for an.
Solution
To find the closed-form expression for an, we first need to solve the associated
homogeneous recurrence relation and then find a particular solution to the non-
homogeneous recurrence relation.
Step 1: Solve the homogeneous recurrence relation We start by
considering the homogeneous part of the recurrence relation:
a(h)
n= 2a(h)
n−1−a(h)
n−2.
The characteristic equation is given by r2−2r+1 = 0, which factors as (r−1)2=
0. Thus, we have a repeated root r= 1.
Therefore, the general solution to the homogeneous recurrence relation is:
a(h)
n=c1·1n+c2·n·1n=c1+c2n.
Step 2: Find a particular solution to the non-homogeneous recur-
rence relation We will assume the particular solution has the form a(p)
n=
An +B. Substituting this into the non-homogeneous recurrence relation:
An +B= 2(A(n−1) + B)−A(n−2) −B+n.
Simplifying, we get:
An +B= 2An −2A+ 2B−An + 2A+B−B+n.
Which simplifies further to:
An +B=An + 2n.
Equating coefficients, we find A= 1 and B= 0.
Step 3: 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+ 1) + (c2+ 1)n.
Step 4: Find the values of c1and c2To find c1and c2, we use the initial
conditions a0= 3 and a1= 5:
a0= 3 ⇒c1+ 1 = 3 ⇒c1= 2,
a1= 5 ⇒c1+c2+ 1 = 5 ⇒2 + c2+ 1 = 5 ⇒c2= 2.
Step 5: Write the closed-form expression Thus, the closed-form ex-
pression for anis:
an= 2 + 1 + 2n= 3 + 2n.
33
Question 33
Question
Consider the non-homogeneous recurrence relation defined by an= 4an−1+ 3 ·
2n−1with initial condition a0= 1. Find the explicit formula for an.
Solution
Step 1: Find the homogeneous solution a(H)
nby solving the characteristic equa-
tion an= 4an−1. The characteristic equation is r= 4r, which has the solution
r= 4. Therefore, the homogeneous solution is a(H)
n=A·4n.
Step 2: Find a particular solution a(P)
nfor the non-homogeneous part of the
recursion. Guess a solution of the form a(P)
n=B·2n. Substituting into the
given recurrence relation, we get
B·2n= 4(B·2n−1)+3·2n−1.
Solving for B, we find B=3
2.
Step 3: The general solution for the recurrence relation is given by an=
a(H)
n+a(P)
n. Therefore, the general solution is an=A·4n+3
2·2n.
Step 4: Use the initial condition a0= 1 to solve for A. Substitute n= 0 and
a0= 1 into the general solution:
1 = A·40+3
2·20.
1 = A+3
2.
A=1
2.
Step 5: Finally, substitute A=1
2back into the general solution to get the
explicit formula for an. Thus, the explicit formula for anis
an=1
2·4n+3
2·2n.
Question 34
Question
Consider the non-homogeneous recurrence relation an= 3an−1−2an−2+ 2n
with initial conditions a0= 1 and a1= 2. Find a closed-form expression for an.
34
Solution
Step 1: First, find the characteristic equation by setting up the corresponding
homogeneous recurrence relation: an= 3an−1−2an−2. The characteristic
equation is r2−3r+ 2 = 0, which factors to (r−1)(r−2) = 0. Therefore, 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 a particular solution to the non-homogeneous part
of the recurrence relation. Since the non-homogeneous term is 2n, we guess
a particular solution of the form a(p)
n=C·2n, where Cis a constant to be
determined.
Step 4: Substitute a(p)
ninto the original recurrence relation and solve for C:
C·2n= 3(C·2n−1)−2(C·2n−2)+2n.
Step 5: Simplify the equation to solve for C:C·2n= 3C·2n−6C·2n−2+2n.
C=1
2.
Step 6: Therefore, the particular solution is a(p)
n=1
2·2n= 2n−1.
Step 7: The general solution to the non-homogeneous part of the recurrence
relation is the sum of the general solution to the homogeneous part and the
particular solution: an=a(h)
n+a(p)
n=A(1)n+B(2)n+ 2n−1.
Step 8: Apply the initial conditions a0= 1 and a1= 2: A+B+ 1 = 1 and
A+ 2B+ 2 = 2.
Step 9: Solve the system of equations to find Aand B: From the first
equation, we find A= 0. Substitute A= 0 into the second equation to find
B=1
2.
Step 10: Finally, the closed-form expression for anis: an=1
2·2n= 2n−1.
Question 35
Question
Let anbe defined recursively for all integers n≥1 as follows:
an= 2an−1−an−2+ 2n.
If a1= 1 and a2= 3, find a formula for anfor all n≥1.
Solution
To solve this recurrence relation, we first find the characteristic equation associ-
ated with the homogeneous part of the relation. The homogeneous part is given
by:
a(h)
n= 2an−1−an−2.
This gives us the characteristic equation r2−2r+ 1 = 0, which simplifies to
(r−1)2= 0. Thus, the characteristic root is r= 1 with multiplicity 2.
35
Therefore, the solution to the homogeneous part is:
a(h)
n=c1·1n+c2·n·1n=c1+c2n.
Next, we proceed to find a particular solution for the non-homogeneous part
of the relation. The non-homogeneous part is 2n, which is of the form P(n)=2n.
Since 2ndoes not match any term in the homogeneous solution, we assume a
particular solution of the form:
a(p)
n=An2n.
Substitute this into the original recurrence relation:
An2n= 2(A(n−1)2n−1)−A(n−2)2n−2+ 2n.
Simplify to find A=1
2. Thus, a particular solution is a(p)
n=1
2n2n.
Therefore, the general solution to the recurrence relation is:
an=a(h)
n+a(p)
n=c1+c2n+1
2n2n.
Using the initial conditions a1= 1 and a2= 3, we can solve for c1and c2:
1 = c1+c2,
3 = c1+ 2c2+ 2.
Solving these equations simultaneously gives us c1=7
4and c2=−3
4.
Therefore, the formula for anfor all n≥1 is:
an=7
4−3
4n+1
2n2n.
36
