MATH 117 - ELEMENTS OF
MATHEMATICS - Homogeneous and
non-homogeneous recurrence relations
Question Bank - Set 5
Liberty University
Question 1
Question
Find a closed-form solution for the following non-homogeneous recurrence rela-
tion:
an= 3an−1−2an−2+ 2nwhere a0= 1 and a1= 2.
Solution
To solve the given non-homogeneous recurrence relation, we first need to find
the homogeneous solution and then a particular solution.
Step 1: Find the homogeneous solution Assume the homogeneous so-
lution has the form a(h)
n=rn. Substitute this into the homogeneous part of the
relation, an= 3an−1−2an−2, to get:
rn= 3rn−1−2rn−2
Divide by rn−2(assuming r= 0) to get the characteristic equation:
r2= 3r−2
This gives us the characteristic roots r= 1 and r= 2. Therefore, the
homogeneous solution is:
a(h)
n=c1·1n+c2·2n=c1+c2·2n
Step 2: Find a particular solution To find a particular solution for
the non-homogeneous part 2n, we guess a solution of the form a(p)
n=A·2n.
Substitute this into the non-homogeneous part of the relation, an= 2n, to get:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
Divide through by 2nto simplify and solve for A:
A=1
2
Therefore, the particular solution is a(p)
n=1
2·2n= 2n−1.
Step 3: Find the general solution Combining the homogeneous and
particular solutions, the general solution to the non-homogeneous recurrence
relation is:
an=a(h)
n+a(p)
n=c1+c2·2n+ 2n−1
Step 4: Use initial conditions to find c1and c2Using the initial
conditions a0= 1 and a1= 2, we can solve for c1and c2:
When n= 0:
1 = c1+c2·20+ 20−1=c1+c2+1
2
When n= 1:
2 = c1+c2·21+ 21−1=c1+ 2c2+ 1
Solving these simultaneous equations, we find c1=1
2and c2=3
2.
Therefore, the closed-form solution for the non-homogeneous recurrence re-
lation is:
an=1
2+3
2·2n+ 2n−1
Question 2
Question
Let anbe a sequence defined recursively by the recurrence relation an= 3an−1−
2an−2with initial conditions a0= 2 and a1= 5. Find a formula for an.
Solution
To find a formula for an, we first need to solve the characteristic equation associ-
ated with the given recurrence relation an= 3an−1−2an−2. The characteristic
equation is r2= 3r−2, which simplifies to r2−3r+ 2 = 0. This equation
factors as (r−1)(r−2) = 0, so the roots are r1= 1 and r2= 2.
Therefore, the general solution to the homogenous recurrence relation is of
the form an=c1·1n+c2·2n, where c1and c2are constants to be determined.
Substitute the initial conditions a0= 2 and a1= 5 into the general solution:
(2 = c1·10+c2·20=c1+c2
5 = c1·11+c2·21=c1+ 2c2
2
Solving the system of equations gives c1= 3 and c2=−1. Therefore, the
formula for anis an= 3 ·1n−1·2n. Simplifying further, we get:
an= 3 −2n
Question 3
Question
Let ansatisfy the non-homogeneous recurrence relation an= 3an−1−2an−2+2n.
If a0= 1 and a1= 2, find a formula for anin terms of n.
Solution
Step 1: First, let’s find the general solution to the corresponding homogeneous
recurrence relation an= 3an−1−2an−2. The characteristic equation is r2=
3r−2, which simplifies to r2−3r+ 2 = 0. The roots of this equation are r1= 1
and r2= 2. Therefore, the general solution to the homogeneous part of the
recurrence relation is a(h)
n=c1·1n+c2·2n.
Step 2: Next, we need to find a particular solution for the non-homogeneous
part 2n. We assume the particular solution has the form a(p)
n=A·2n. Substi-
tuting this into the original non-homogeneous recurrence relation, we get:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
A·2n= 3A·2n−1−2A·2n−2+ 2n
A=2n
2= 2n−1
So, the particular solution is a(p)
n= 2n−1.
Step 3: Therefore, the general solution to the non-homogeneous recurrence
relation is the sum of the general solution to the homogeneous part and the
particular solution to the non-homogeneous part:
an=a(h)
n+a(p)
n=c1·1n+c2·2n+ 2n−1
Step 4: To find the values of c1and c2, we use the initial conditions a0= 1
and a1= 2:
a0=c1·10+c2·20+ 2−1=c1+c2+1
2= 1
a1=c1·11+c2·21+ 20=c1+ 2c2+ 1 = 2
Solving these equations, we find c1=1
2and c2=1
2. Therefore, the formula
for anin terms of nis:
an=1
2+1
2·2n+ 2n−1=1
2+ 2n+ 2n−1
3
Question 4
Question
Consider the following recurrence relation:
an= 6an−1−9an−2+ 4n
Given that the initial conditions are a0= 1 and a1= 3, find a closed-form
expression for an.
Solution
Step 1: Finding the homogeneous solution Let’s first consider the homogeneous
part of the recurrence relation:
an= 6an−1−9an−2
The characteristic equation associated with this homogeneous recurrence rela-
tion is:
r2= 6r−9
r2−6r+ 9 = 0
(r−3)2= 0
This gives us a repeated root r= 3.
Therefore, the homogeneous solution is of the form:
a(h)
n=c1·3n+c2·n·3n
Step 2: Finding the particular solution Now, let’s find a particular solution
for the non-homogeneous part. Since the non-homogeneous term is 4n, we
assume a particular solution of the form a(p)
n=A·4n.
Substitute an=A·4nback into the original recurrence relation:
A·4n= 6(A·4n−1)−9(A·4n−2)+4n
A=4n
7
Therefore, the particular solution is a(p)
n=4n
7.
Step 3: Finding the complete solution The complete solution is the sum of
the homogeneous and particular solutions:
an=a(h)
n+a(p)
n
an=c1·3n+c2·n·3n+4n
7
4
Step 4: Applying initial conditions Using the initial conditions a0= 1 and
a1= 3:
a0= 1 →c1+1
7= 1
a1= 3 →3c1+ 3c2+4
7= 3
Solving these two equations gives c1=6
7and c2=−2
7.
Thus, the closed-form expression for anis:
an=6
7·3n−2
7·n·3n+4n
7
Question 5
Question
Let anbe defined by the recurrence relation an= 6an−1−9an−2for all integers
n≥2 with initial conditions a0= 3 and a1= 6. Find a formula for an.
Solution
Step 1: Find the characteristic equation by assuming an=rnfor some constant
r.
rn= 6rn−1−9rn−2
Divide through by rn−2to get
r2= 6r−9
r2−6r+ 9 = 0
(r−3)2= 0
r= 3
Step 2: Since the characteristic equation has a repeated root, the general
form of the solution will be
an= (A+Bn)3n
for some constants Aand B.
Step 3: Use the initial conditions a0= 3 and a1= 6 to solve for Aand B.
a0= (A)30=A= 3
a1= (A+B)31= 3 + 3B= 6
B= 1
Step 4: Thus, the formula for anis
an= 3 + n·3n
5
Question 6
Question
Consider the non-homogeneous recurrence relation an= 2an−1−3an−2+ 2n
with initial conditions a0= 1 and a1= 2. Find the explicit formula for an.
Solution
Step 1: Find the homogeneous solution a(H)
nby solving the characteristic equa-
tion r2−2r+ 3 = 0. The characteristic equation has roots r= 1 ±i√2, so the
homogeneous solution is of the form
a(H)
n=c1·(1 + i√2)n+c2·(1 −i√2)n.
Step 2: Find a particular solution a(P)
nof the non-homogeneous equation.
We guess a particular solution of the form a(P)
n=A·2n. Substitute this into
the non-homogeneous equation to get
A·2n= 2(A·2n−1)−3(A·2n−2)+2n.
Step 3: Solve for A in the above equation. Solving the equation yields
A=−2
3.
Step 4: Write down the general solution. The general solution is given by
an=a(H)
n+a(P)
n=c1·(1 + i√2)n+c2·(1 −i√2)n−2
3·2n.
Step 5: Apply the initial conditions to find c1and c2. Using a0= 1 and
a1= 2, we can find c1and c2.
c1+c2−2
3= 1
c1·(1 + i√2) + c2·(1 −i√2) −4
3= 2.
Solving these simultaneous equations gives c1=5
6and c2=1
6.
Step 6: Plug in the values of c1and c2into the general solution. Therefore,
the explicit formula for anis
an=5
6·(1 + i√2)n+1
6·(1 −i√2)n−2
3·2n.
Question 7
Question
Consider the following non-homogeneous recurrence relation:
an+2 −8an+1 + 16an=n
Find the general solution to this non-homogeneous recurrence relation.
6
Solution
To find the general solution to the non-homogeneous recurrence relation, we
need to first find the general solution to the associated homogeneous recurrence
relation, then find a particular solution to the non-homogeneous part, and finally
add these two solutions together.
Step 1: Find the general solution to the associated homogeneous
recurrence relation.
The associated homogeneous recurrence relation is obtained by setting the
right-hand side to 0:
an+2 −8an+1 + 16an= 0
The characteristic equation is:
r2−8r+ 16 = 0
Solving this quadratic equation, we find that r= 4. Thus, the general
solution to the associated homogeneous recurrence relation is:
an=c1·4n+c2·n·4n
where c1and c2are constants to be determined.
Step 2: Find a particular solution to the non-homogeneous part.
To find a particular solution, we assume that anhas the form of the right-
hand side of the non-homogeneous relation, n. Since it is a linear function, we
assume an=An +B.
Substitute an=An +Bback into the original non-homogeneous recurrence
relation:
(A(n+ 2) + B)−8(A(n+ 1) + B) + 16(An +B) = n
Solving for Aand B, we get A=1
2and B=1
16 .
Therefore, the particular solution is an=1
2n+1
16 .
Step 3: Write out the general solution.
The general solution to the non-homogeneous recurrence relation is the sum
of the general solution to the associated homogeneous recurrence relation and
the particular solution to the non-homogeneous part:
an=c1·4n+c2·n·4n+1
2n+1
16
Question 8
Question
Let (an) be a sequence defined by the recurrence relation an+2 = 4an+1−4an+3n
for n≥0 with initial conditions a0= 1 and a1= 2. Find a closed-form
expression for an.
7
Solution
Step 1: Write down the characteristic equation associated with the homogeneous
part of the recurrence relation: an+2 = 4an+1 −4an. The characteristic equation
is r2= 4r−4, which simplifies to r2−4r+4 = 0. Factoring this gives (r−2)2= 0,
so we have a repeated root r= 2.
Step 2: Use the repeated root r= 2 to write down the solution to the
homogeneous part. The solution to the homogeneous part is then a(h)
n= (c1+
c2n)2n.
Step 3: Find a particular solution to the non-homogeneous part of the re-
currence relation. Since the non-homogeneous part is 3n, we try a particular
solution of the form a(p)
n=An3n. Substituting this into the original recurrence
relation gives:
An3n+2 = 4An3n+1 −4An3n+ 3n.
Step 4: Solve for Aby comparing coefficients of 3n. Solving An3n+2 =
4An3n+1 −4An3n+ 3nfor Agives:
9A= 12A−4A+ 1,
which simplifies to A=1
4.
Step 5: Write down the general solution to the non-homogeneous part. The
general solution to the non-homogeneous part is a(p)
n=1
4n3n.
Step 6: Combine the homogeneous and non-homogeneous solutions to get
the general solution. The general solution to the original recurrence relation is
then:
an=a(h)
n+a(p)
n= (c1+c2n)2n+1
4n3n.
Step 7: Use the initial conditions a0= 1 and a1= 2 to solve for c1and
c2. Substitute n= 0 and n= 1 into an= (c1+c2n)2n+1
4n3nand solve the
resulting system of equations to find c1and c2.
Thus, the closed-form expression for anis:
an=3
22n+1
4n3n−1
2.
Question 9
Question
Find a closed-form expression for the following non-homogeneous recurrence
relation:
an= 3an−1−2an−2+ 2nwith initial conditions a0= 1 and a1= 2.
8
Solution
To find a closed-form expression for the non-homogeneous recurrence relation,
we need to solve the homogeneous part an= 3an−1−2an−2and then find a
particular solution for the non-homogeneous part an= 2n.
Step 1: Solve the homogeneous part The characteristic equation of the
homogeneous part is given by r2= 3r−2 which simplifies to r2−3r+ 2 = 0.
The roots of this characteristic equation are r1= 1 and r2= 2.
Therefore, the general solution of the homogeneous part is a(h)
n=c1·1n+
c2·2n.
Step 2: Find a particular solution Since the non-homogeneous part is
2n, we can try a particular solution of the form a(p)
n=A·2n. Substituting this
into the original recurrence relation, we get:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
Solving this equation, we find A=2
3. Therefore, a particular solution is
a(p)
n=2
3·2n.
Step 3: Determine the complete solution The complete solution is the
sum of the general solution of the homogeneous part and the particular solution:
an=a(h)
n+a(p)
n=c1·1n+c2·2n+2
3·2n
Step 4: Apply initial conditions Using the initial conditions a0= 1 and
a1= 2, we can find c1and c2.
a0= 1 : c1+c2+2
3= 1
a1=2: c1+ 2c2+4
3= 2
Solving these equations, we find c1=1
3and c2=1
3.
Step 5: Final solution Therefore, the closed-form expression for anis:
an=1
3·1n+1
3·2n+2
3·2n
Question 10
Question
Let anbe a sequence defined by the recurrence relation an+2 = 3an+1 −2an+n2,
where a0= 1 and a1= 2. Find a closed-form expression for an.
9
Solution
Step 1: Find the homogeneous solution. We first consider the homogeneous part
of the recurrence relation, which is an+2 = 3an+1 −2an. Setting an=rn, we
get the characteristic equation r2= 3r−2, which simplifies to r2−3r+ 2 = 0.
Factoring, we find (r−2)(r−1) = 0, so the solutions are r= 1 and r= 2.
Therefore, the homogeneous solution is a(h)
n=A(1)n+B(2)nfor some constants
Aand B.
Step 2: Find a particular solution. Now, we need to find a particular solution
to the non-homogeneous part of the recurrence relation, n2. Since the non-
homogeneous term is a polynomial of degree 2, we guess a particular solution
of the form a(p)
n=cn2+dn +e. Substituting this into the original recurrence
relation, we get
c(n+ 2)2+d(n+ 2) + e= 3(c(n+ 1)2+d(n+ 1) + e)−2(cn2+dn +e) + n2.
This simplifies to c=1
2and d=−1. There is no contribution from the constant
term, so eis arbitrary. Thus, a particular solution is a(p)
n=1
2n2−n+e.
Step 3: Combine the solutions. The general solution is the sum of the
homogeneous and particular solutions, so
an=A(1)n+B(2)n+1
2n2−n+e.
Step 4: Solve for the constants. Using the initial conditions a0= 1 and
a1= 2, we get a system of equations to solve for A,B, and e:
A+B+e= 1
A(1) + B(2) + 1
2−1 + e= 2
Solving this system, we find A= 0, B=3
2, and e=1
2.
Therefore, the closed-form expression for anis an=3
2(2)n+1
2n2−n+1
2.
Question 11
Question
Let’s consider the recurrence relation defined as an= 2an−1−3an−2with initial
conditions a0= 1 and a1= 4. Solve this recurrence relation and find a formula
for an.
Solution
Step 1: Find the characteristic equation by assuming the solution is of the form
an=rn. The characteristic equation is given by r2= 2r−3, which simplifies
to r2−2r+ 3 = 0.
10
Step 2: Solve the characteristic equation to find the roots. Using the
quadratic formula, we have r=2±√(−2)2−4∗1∗3
2∗1. This simplifies to r= 1 ±i√2.
Step 3: Write the general solution using the roots. Since the roots are
complex conjugates, the general solution is an=c1(1 + i√2)n+c2(1 −i√2)n.
Step 4: Use the initial conditions to find the values of c1and c2. Substitute
a0= 1 and a1= 4 into the general solution: For a0= 1, we get c1+c2= 1. For
a1= 4, we get c1(1 + i√2) + c2(1 −i√2) = 4.
Step 5: Solve the system of equations from step 4 to find c1and c2. From
the first equation, we can write c1in terms of c2as c1= 1 −c2. Substitute c1
in the second equation and solve for c2.
Step 6: Once c2is found, substitute back to find c1.
Step 7: Finally, substitute the values of c1and c2into the general solution
to get the formula for an.
Question 12
Question
Let anbe the sequence defined by the recurrence relation an+2−5an+1+6an= 0,
with initial conditions a0= 1 and a1= 3. Find an explicit formula for an.
Solution
Step 1: First, we need to find the characteristic equation for the given recurrence
relation. Let’s assume an=rnand substitute it into the relation to get rn(r2−
5r+ 6) = 0. Therefore, the characteristic equation is r2−5r+ 6 = 0.
Step 2: We can factor the characteristic equation to get (r−2)(r−3) = 0.
Thus, the roots are r1= 2 and r2= 3.
Step 3: Since the roots are distinct, the general solution to the recurrence
relation is given by an=A·2n+B·3n.
Step 4: Using the initial conditions a0= 1 and a1= 3, we can set up a
system of equations to solve for Aand B. Substituting n= 0 and n= 1 into
the general solution, we get:
(A+B= 1
2A+ 3B= 3
Step 5: Solving the system of equations, we find A=3
2and B=−1
2.
Step 6: Therefore, the explicit formula for the sequence anis an=3
2·2n−
1
2·3n.
11
Question 13
Question
Let anbe defined by the recurrence relation an= 4an−1−4an−2for n≥2, with
initial conditions a0= 2 and a1= 3. Find a formula for an.
Solution
Step 1: Find the characteristic equation by assuming an=rnwhere ris a
constant.
rn= 4rn−1−4rn−2
Divide both sides by rn−2to simplify:
r2= 4r−4
r2−4r+ 4 = 0
(r−2)2= 0
This gives us a repeated root r= 2.
Step 2: The general solution to the homogeneous recurrence relation is of
the form an=c1·2n+c2·n·2n.
Step 3: Use the initial conditions to find the values of c1and c2.
a0=2=c1·20+c2·0·20=c1
a1=3=c1·21+c2·1·21= 2c1+ 2c2
Solving these equations give c1= 2 and c2=−1
2.
Step 4: The formula for anis thus an= 2 ·2n−1
2·n·2n.
Question 14
Question
Let ansatisfy the recurrence relation an= 2an−1−3an−2for n≥2, with initial
conditions a0= 2 and a1= 1. Find a closed-form expression for an.
Solution
Step 1: Find the characteristic equation by assuming a solution of the form
an=rn.
rn= 2rn−1−3rn−2
Divide by rn−2:
r2= 2r−3
r2−2r+ 3 = 0
12
Step 2: Solve the characteristic equation. We can solve the quadratic equa-
tion r2−2r+ 3 = 0 using the quadratic formula:
r=−(−2) ±p(−2)2−4∗1∗3
2∗1
r=2±√4−12
2
r= 1 ±i√2
Step 3: Write the general solution as a linear combination of the basis of
solutions. The general solution to the homogeneous equation is:
an=c1(1 + i√2)n+c2(1 −i√2)n
Step 4: Use the initial conditions to solve for c1and c2.
a0=2=c1+c2
a1= 1 = c1(1 + i√2) + c2(1 −i√2)
Step 5: Solve the equations to find c1and c2. We have a system of equations:
c1+c2= 2
c1(1 + i√2) + c2(1 −i√2) = 1
Solving this system, we find c1=2
3−1
3i√2 and c2=4
3+1
3i√2.
Therefore, the closed-form expression for anis:
an=2
3(1 + i√2)n+4
3(1 −i√2)n
Question 15
Question
Consider the following non-homogeneous recurrence relation:
an= 2an−1−an−2+ 2n
with initial conditions a0= 1 and a1= 2. Find the explicit formula for an.
Solution
To solve the non-homogeneous recurrence relation, we first need to find the
general solution to the associated homogeneous recurrence relation:
an= 2an−1−an−2
13
Step 1: Find the general solution to the homogeneous recurrence
relation Assume the solution to the homogeneous recurrence relation is in the
form an=rn. Substituting this into the homogeneous recurrence relation, we
get:
rn= 2rn−1−rn−2
r2= 2r−1
The characteristic equation is 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:
an=c1·1n+c2·n·1n=c1+c2n
Step 2: Find a particular solution to the non-homogeneous recur-
rence relation To find a particular solution to the non-homogeneous recurrence
relation, we make an educated guess based on the form of the non-homogeneous
term. Since 2nis an exponential function and the recurrence relation is linear,
we guess a particular solution of the form an=An2n, where Ais a constant to
be determined. Substituting this into the recurrence relation, we get:
An2n= 2(A(n−1)2n−1)−A(n−2)2n−2+ 2n
Simplify the equation above to find A.
Step 3: Determine the value of AWorking out the equation obtained
from Step 2, we get:
An2n= 2A(n−1)2n−1−A(n−2)2n−2+ 2n
Now, solve for A.
Step 4: Find the explicit formula for anThe explicit formula for anis
the sum of the general solution to the homogeneous recurrence relation and the
particular solution to the non-homogeneous recurrence relation:
an=c1+c2n+An2n
Using the initial conditions a0= 1 and a1= 2, we can solve for c1,c2, and
Ato find the explicit formula for an.
Question 16
Question
Consider the non-homogeneous recurrence relation an= 4an−1−4an−2+ 2n
with initial conditions a0= 1 and a1= 3. Find a closed-form expression for an.
14
Solution
Step 1: First, let’s find the corresponding homogeneous recurrence relation. We
do this by setting the non-homogeneous term to zero. Therefore, the homoge-
neous recurrence relation is a(h)
n= 4an−1−4an−2.
Step 2: Next, we seek for a particular solution of the non-homogeneous re-
currence relation. Since the non-homogeneous term 2nis a geometric sequence,
it is reasonable to assume a particular solution of the form a(p)
n=A2n, where
Ais a constant to be determined.
Step 3: Substituting a(p)
n=A2ninto the non-homogeneous recurrence rela-
tion, we get
A2n= 4(A2n−1)−4(A2n−2)+2n
Step 4: Simplifying the above equation, we have
A= 4A2−1−4A2−2+ 1
Step 5: Solving the above equation, we find A=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 recurrence relation is
given by the sum of the homogeneous solution and the particular solution, i.e.,
an=a(h)
n+a(p)
n.
Step 8: With the initial conditions a0= 1 and a1= 3, we find a(h)
0= 1 and
a(h)
1= 3.
Step 9: Therefore, a0=a(h)
0+a(p)
0, which implies 1 = 1 + A. Thus, A= 0.
Step 10: Similarly, a1=a(h)
1+a(p)
1gives 3 = 3 + A. This also yields A= 0.
Step 11: Hence, the closed-form expression for anis an=a(h)
n+a(p)
n=
a(h)
n= 2n−1.
Question 17
Question
Consider the following non-homogeneous recurrence relation:
an= 2an−1+ 3n
where a0= 1.
Find a closed-form expression for an.
Solution
To solve this non-homogeneous recurrence relation, we first find the complemen-
tary function CF by solving the corresponding homogeneous relation:
a(H)
n= 2an−1
15
Step 1: Find the homogeneous solution The characteristic equation is
given by:
r−2=0
r= 2
So the homogeneous solution is:
a(H)
n=c·2n
Step 2: Find the particular solution We guess that the particular solu-
tion is of the form a(P)
n=An ·3n.
Step 3: Substitute the particular solution into the original recur-
rence relation
An ·3n= 2(An −1·3n−1)+3n
An ·3n= 2A(n−1) ·3n+ 3n
Step 4: Solve for A Solving for A, we get:
An = 2A(n−1) + 1
An = 2An −2A+ 1
A=−1
Step 5: Write down the particular solution The particular solution is
a(P)
n=−n·3n
Step 6: Write down the general solution and solve for cusing the
initial condition The general solution is given by:
an=a(H)
n+a(P)
n
an=c·2n−n·3n
Using the initial condition a0= 1:
1 = c−0
c= 1
Step 7: Final solution Therefore, the closed-form expression for anis:
an= 2n−n·3n
Question 18
Question
Let anbe a sequence defined by the recurrence relation an= 2an−1−an−2+1 for
all integers n≥2, with initial conditions a0= 1 and a1= 3. Find a closed-form
expression for an.
16
Solution
Step 1: First, let’s find the characteristic polynomial of the recurrence relation.
The characteristic polynomial is obtained by setting an=xnand substituting
it into the recurrence relation an= 2an−1−an−2+ 1:
xn= 2xn−1−xn−2+ 1
Step 2: Rearrange the equation to obtain the characteristic polynomial:
xn−2xn−1+xn−2−1 = 0
xn−2(x2−2x+ 1) −1=0
xn−2(x−1)2−1=0
Step 3: The characteristic equation has a repeated root of 1. Therefore, the
general solution takes the form:
an=A·1n+B·n·1n
an=A+Bn
Step 4: Next, we use the initial conditions a0= 1 and a1= 3 to solve for A
and B. From a0= 1:
A= 1
Step 5: From a1= 3:
A+B(1) = 3
1 + B= 3
B= 2
Step 6: Therefore, the closed-form expression for anis:
an= 1 + 2n
Question 19
Question
Let anbe defined by the recurrence relation an= 2an−1−2an−2for n≥2 with
initial conditions a0= 1 and a1= 2. Find a closed-form expression for an.
17
Solution
To solve the given recurrence relation, we first need to find the characteristic
equation associated with it. The characteristic equation is given by r2= 2r−2,
which simplifies to r2−2r+ 2 = 0.
Step 1: Find the roots of the characteristic equation Using the
quadratic formula, we find that the roots of the characteristic equation are
r=2±√22−4·1·2
2= 1 ±i. Therefore, the general solution to the homogeneous
recurrence relation is of the form an=c1·(1 + i)n+c2·(1 −i)n.
Step 2: Use initial conditions to determine c1and c2Substitute the
initial conditions a0= 1 and a1= 2 into the general solution:
(a0=c1(1 + i)0+c2(1 −i)0=c1+c2= 1
a1=c1(1 + i)1+c2(1 −i)1=c1(1 + i) + c2(1 −i)=2
From the first equation, we have c2= 1 −c1. Substitute this into the second
equation:
c1(1 + i) + (1 −c1)(1 −i)=2
c1+ic1+ 1 −i−c1+ic1= 2
2ic1−i= 1
c1=1 + i
2i
c1=1
2−1
2i
Therefore, c2= 1 −c1=1
2+1
2i. Substituting back into the general solution,
we get:
an=1
2−1
2i(1 + i)n+1
2+1
2i(1 −i)n
Hence, the closed-form expression for anis an=1
22ncos(nπ/4)+ 1
22nsin(nπ/4)
or an= 2n−1cos(nπ/4) + 2n−1sin(nπ/4).
Question 20
Question
Consider the non-homogeneous recurrence relation an= 2an−1−an−2+2nwith
initial conditions a0= 1 and a1= 3. Find a closed-form expression for an.
18
Solution
Step 1: First, solve the associated homogeneous recurrence relation a(h)
n=
2a(h)
n−1−a(h)
n−2.
Characteristic equation: r2−2r+ 1 = 0
(r−1)2= 0
r= 1 (Repeated root)
So the general solution for the homogeneous part is a(h)
n=c1·1n+c2·n·1n=
c1+c2n.
Step 2: Now, find a particular solution for the non-homogeneous recurrence
relation. Let’s guess a particular solution of the form a(p)
n=A·2n. Substitute
into the non-homogeneous recurrence relation to get:
−A·2n−2= 2 ·(−A·2n−1)−(−A·2n−2)+2n
Solving this, we find A=1
3.
So the particular solution is a(p)
n=1
3·2n.
Step 3: The general solution for the non-homogeneous part is the sum of the
homogeneous and particular solutions.
an=a(h)
n+a(p)
n=c1+c2n+1
3·2n
Step 4: Using the initial conditions a0= 1 and a1= 3, we can find the
values of c1and c2.
a0=c1+c2·0 + 1
3·20= 1
c1+1
3= 1
c1=2
3
a1=c1+c2·1 + 1
3·21= 3
2
3+c2+2
3= 3
c2=5
3
Step 5: Thus, the closed-form expression for anis an=2
3+5
3n+1
3·2n.
Question 21
Question
Consider the non-homogeneous recurrence relation given by
19
an= 3an−1−2an−2+ 2n
with initial conditions a0= 1 and a1= 2. Find the explicit formula for an.
Solution
Step 1: First, find the homogeneous solution a(H)
nby setting the right-hand
side to zero and solving the characteristic equation rn= 3rn−1−2rn−2. The
characteristic equation is r2−3r+ 2 = 0, which factors as (r−1)(r−2) = 0.
So, the roots are r1= 1 and r2= 2, and the homogeneous solution is a(H)
n=
A·1n+B·2n, where Aand Bare constants to be determined.
Step 2: Next, find a particular solution a(P)
nby guessing that it has the form
a(P)
n=C·2n. Substitute an=C·2ninto the original recurrence relation to
find C:
C·2n= 3(C·2n−1)−2(C·2n−2)+2n
C·2n= 3C·2n−1−2C·2n−2+ 2n
C=2n
2= 2n−1
Therefore, a(P)
n= 2n−1.
Step 3: The general solution is the sum of the homogeneous and particular
solutions: an=a(H)
n+a(P)
n. Plugging in the initial conditions a0= 1 and
a1= 2, we can solve for Aand B: 1 = A+B(from a0= 1)
2 = A+ 2B(from a1= 2)
Solving these equations gives A=−1 and B= 2, so the explicit formula for
anis
an=−1·1n+ 2 ·2n= 2n+1 −1
Question 22
Question
Let anbe defined by the recurrence relation an= 2an−1−2an−2+ 3nfor n≥2,
where a0= 1 and a1= 3. Find a closed-form expression for an.
Solution
Step 1: Solve the homogeneous part of the recurrence relation.
The homogeneous part is an= 2an−1−2an−2. We can try a solution of the
form an=rnfor some r:
rn= 2rn−1−2rn−2
r2= 2r−2
r2−2r+ 2 = 0
20
This equation has complex roots r= 1 ±i. Therefore, the solution to the
homogeneous part is of the form:
a(h)
n=c1(1 + i)n+c2(1 −i)n
Step 2: Find a particular solution for the non-homogeneous part.
The non-homogeneous term is 3n, which is a geometric sequence. We can
make an educated guess that a particular solution is of the form a(p)
n=A·3n.
Substitute an=A·3ninto the original recurrence relation:
A·3n= 2(A·3n−1)−2(A·3n−2)+3n
A·3n= 2A·3n−2A·3n−1+ 3n
A=3n
3n−2·3n−1+ 2 ·3n−2
A=3n
3n−6·3n−2+ 6 ·3n−2
A=3n
3n−6·3n−1
A=1
1−2·3−1
A=1
1−2/3
A=3
1
A= 3
So, a particular solution for the non-homogeneous part is a(p)
n= 3·3n= 3n+1.
Step 3: Combine the homogeneous and particular solutions.
Therefore, the general solution to the recurrence relation is:
an=a(h)
n+a(p)
n=c1(1 + i)n+c2(1 −i)n+ 3n+1
Step 4: Use initial conditions to find c1and c2.
Using the initial conditions a0= 1 and a1= 3:
a0=c1(1 + i)0+c2(1 −i)0+ 31=c1+c2+ 3 = 1
a1=c1(1 + i)1+c2(1 −i)1+ 32=c1(1 + i) + c2(1 −i) + 9 = 3
Solving this system of equations, we find c1=3
2−3i
2and c2=3
2+3i
2.
Therefore, the closed-form expression for anis:
an= (3
2−3i
2)(1 + i)n+ (3
2+3i
2)(1 −i)n+ 3n+1
21
Question 23
Question
Let anbe a sequence defined recursively by the relation an+1 = 2an−2nfor
n≥0 with the initial condition a0= 4. Find a closed-form expression for an.
Solution
Step 1: Write the characteristic equation for the homogeneous version of the
recurrence relation.
The homogeneous version of the recurrence relation is an+1 = 2an. This
gives us the characteristic equation r= 2, with the solution a(h)
n=C·2n.
Step 2: Find a particular solution for the non-homogeneous part.
For the non-homogeneous part −2n, we try a particular solution of the form
a(p)
n=An ·2n. Substituting this into the original recurrence relation gives:
An ·2n+1 = 2(An ·2n)−2n
An ·2n+1 = 2An ·2n−2n
An ·2·2n= 2An ·2n−2n
2An ·2n= 2An ·2n−2n
2n= 0
This implies that A=−1/2.
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−1
2·n·2n
Step 4: Apply the initial condition to solve for C.
Given that a0= 4, we have:
4 = C·20−1
2·0·20
4 = C
Step 5: Write the closed-form expression for an.
Thus, the closed-form expression for anis:
an= 4 ·2n−1
2·n·2n
Question 24
Question
Let anbe a sequence defined by the recurrence relation an+2 −4an+1 +4an= 2n
for n≥0 with initial conditions a0= 1 and a1= 2. Find a closed-form
expression for an.
Solution
Step 1: First, let’s find the characteristic equation for the homogeneous part of
the recurrence relation. The characteristic equation is given by r2−4r+ 4 = 0.
22
This factors to (r−2)2= 0, so we have a repeated root r= 2.
Step 2: The solution to the homogeneous part is then given by a(h)
n=
c1·2n+c2·n·2n.
Step 3: Now, let’s find a particular solution to the non-homogeneous part
of the recurrence relation. Since the right-hand side is 2n, a good guess for a
particular solution is a(p)
n=A·2n.
Step 4: Substituting a(p)
n=A·2ninto the recurrence relation gives:
(A·2n+2)−4(A·2n+1) + 4(A·2n)=2n.
Step 5: This simplifies to 4A−4A+ 4A= 1, so 4A= 1 and A=1
4.
Step 6: Therefore, the particular solution is a(p)
n=1
4·2n.
Step 7: Combining the homogeneous and particular solutions, the general
solution is:
an=a(h)
n+a(p)
n=c1·2n+c2·n·2n+1
4·2n.
Step 8: Using the initial conditions a0= 1 and a1= 2, we can find the
values of c1and c2. Plugging in n= 0: c1+c2+1
4= 1. Plugging in n= 1:
2c1+ 2c2+1
2= 2.
Step 9: Solving the system of equations, we find c1=1
2and c2=−1
4.
Step 10: Therefore, the closed-form expression for anis an=1
2·2n−1
4·n·
2n+1
4·2n.
Question 25
Question
Let andenote the nth term of a sequence defined by the recurrence relation
an+2 −5an+1 + 6an= 0 for all integers n≥0, with initial conditions a0= 4
and a1= 6. Find a formula for anfor all non-negative integers n.
Solution
Step 1: Find the characteristic equation. Given the recurrence relation an+2 −
5an+1 + 6an= 0, we represent it as a characteristic equation r2−5r+ 6 = 0.
Simplifying, we get (r−2)(r−3) = 0, so the roots are r1= 2 and r2= 3.
Step 2: Find the general solution. Since the roots are distinct, the general
solution takes the form an=c1·2n+c2·3n.
Step 3: Determine the values of c1and c2. Using the initial conditions a0= 4
and a1= 6, we have the system of equations: c1+c2= 4, 2c1+ 3c2= 6.
Solving this system, we find c1= 3 and c2= 1.
Step 4: Write the formula for an. Therefore, the formula for anis an=
3·2n+ 1 ·3n.
23
Question 26
Question
Let andenote the nth term of a sequence defined by the recurrence relation
an+1 = 2an−an−1where a0= 1 and a1= 2. Find a closed-form expression for
an.
Solution
Step 1: Find the characteristic equation. The characteristic equation for the
given recurrence relation is r2= 2r−1.
Step 2: Solve for the roots of the characteristic equation. To find the roots
of the characteristic equation, we need to solve r2−2r+ 1 = 0. This factors as
(r−1)2= 0, so r= 1 with multiplicity 2.
Step 3: Write down the general form of the solution. Since r= 1 is a
repeated root, the general form of the solution is an= (c1+c2n)·1n.
Step 4: Use the initial conditions to find the values of c1and c2. Given that
a0= 1 and a1= 2, we have:
(c1= 1
c1+c2= 2
Step 5: Solve for c1and c2. From the first equation, we have c1= 1.
Substitute c1= 1 into the second equation to solve for c2: 1 + c2= 2, so c2= 1.
Step 6: Write the closed-form expression for an. Therefore, the closed-form
expression for anis an= (1 + n).
Question 27
Question
Consider a sequence defined by the recurrence relation:
an= 3an−1−2an−2+ 2n
with initial conditions a0= 1 and a1= 2. Determine the explicit formula for
an.
Solution
Step 1: First, we solve the homogeneous part of the recurrence relation. We set
an=a(h)
n:
a(h)
n= 3a(h)
n−1−2a(h)
n−2
Step 2: To solve a(h)
n, we assume the solution is of the form a(h)
n=rn, where
ris a constant.
24
Step 3: Substituting this into the homogeneous part of the equation gives
us:
rn= 3rn−1−2rn−2
Step 4: Dividing through by rn−2(assuming r= 0) gives us the characteristic
equation:
r2= 3r−2
Step 5: Solving the characteristic equation r2−3r+ 2 = 0 gives us the roots
r= 1 and r= 2.
Step 6: The solution to the homogeneous part of the recurrence relation is
then given by:
a(h)
n=c1·1n+c2·2n
a(h)
n=c1+c2·2n
Step 7: Now, we find a particular solution to the non-homogeneous part of
the recurrence relation. We will assume a(p)
n=A·2n.
Step 8: Substituting a(p)
ninto the original recurrence relation gives us:
A·2n= 3A·2n−1−2A·2n−2+ 2n
Step 9: After simplifying, we get A= 1.
Step 10: Therefore, the general solution to the non-homogeneous part is:
a(p)
n= 2n
Step 11: The general solution to the original recurrence relation is the sum
of the homogeneous and particular solutions:
an=c1+c2·2n+ 2n
Step 12: Using the initial conditions a0= 1 and a1= 2, we find c1=−1
and c2= 2.
Step 13: Therefore, the explicit formula for anis:
an=−1+2·2n+ 2n
Question 28
Question
Consider the homogeneous recurrence relation an= 3an−1−2an−2with initial
conditions a0= 1 and a1= 4. Determine a formula for anin terms of n.
25
Solution
Step 1: Find the characteristic equation by assuming an=rn. Setting an=rn
in the homogeneous recurrence relation gives:
rn= 3rn−1−2rn−2
Dividing by rn−2yields:
r2= 3r−2
r2−3r+ 2 = 0
Step 2: Solve the characteristic equation. Factoring the equation gives:
(r−1)(r−2) = 0
So, the roots are r1= 1 and r2= 2.
Step 3: Write the general solution. The general solution for the homogeneous
recurrence relation is:
an=c1(1)n+c2(2)n
an=c1+ 2nc2
Step 4: Apply the initial conditions to find c1and c2. Using the initial
conditions a0= 1 and a1= 4, we have:
a0=c1+ 20c2=c1+c2= 1
a1=c1+ 21c2=c1+ 2c2= 4
Step 5: Solve the system of equations to find c1and c2. Subtracting the first
equation from the second gives:
2c2= 3
c2=3
2
Substitute c2=3
2back into the first equation to find c1:
c1+3
2= 1
c1= 1 −3
2=−1
2
Step 6: Write the formula for an. Therefore, the formula for anin terms of
nis:
an=−1
2+3
2×2n
an=−1
2+ 3(2n)
26
Question 29
Question
Find a closed-form expression for the sequence defined by the recurrence relation
an= 5an−1−6an−2+ 2n, with initial conditions a0= 1 and a1= 3.
Solution
Step 1: Finding the homogeneous solution
Let’s first find the solution to the homogeneous part of the recurrence re-
lation by setting an=rn. Substituting this into the homogeneous part of the
recurrence relation, an= 5an−1−6an−2, we get:
rn= 5rn−1−6rn−2
Dividing by rn−2(assuming r= 0), we obtain the characteristic equation:
r2−5r+ 6 = 0
Factoring the quadratic equation, we get:
(r−2)(r−3) = 0
Thus, the homogeneous solution is:
a(h)
n=c1·2n+c2·3n
Step 2: Finding a particular solution
We now need to find a particular solution for the non-homogeneous part of
the recurrence relation, an= 2n. Since 2nis a term in the recurrence relation,
we try a particular solution of the form a(p)
n=c·2n.
Substitute this trial particular solution into the original recurrence relation:
c·2n= 5(c·2n−1)−6(c·2n−2)+2n
Solving for c, we find c=1
2.
Thus, the particular solution is a(p)
n=1
2·2n= 2n−1.
Therefore, the general solution is:
an=a(h)
n+a(p)
n=c1·2n+c2·3n+ 2n−1
Step 3: Applying initial conditions
Using the initial conditions a0= 1 and a1= 3: Substitute n= 0:
1 = c1+c2+ 1
Substitute n= 1:
3=2c1+ 3c2+ 2
Solving these equations simultaneously, we find c1=−5 and c2= 5.
Therefore, the closed-form expression for the sequence is:
an=−5·2n+ 5 ·3n+ 2n−1
27
Question 30
Question
Find a closed-form expression for the solution of the recurrence relation an=
6an−1−9an−2with initial conditions a0= 2 and a1= 5.
Solution
Step 1: Finding the characteristic equation by assuming the solution has the
form an=rn:
rn= 6rn−1−9rn−2
Step 2: Dividing everything by rn−2to simplify the equation:
r2= 6r−9
Step 3: Rewriting the equation in standard quadratic form by moving ev-
erything to one side:
r2−6r+ 9 = 0
(r−3)2= 0
Step 4: The characteristic equation has a repeated root r= 3. Thus, the
general form of the solution is:
an=c1·3n+c2·n·3n
Step 5: Applying the initial conditions a0= 2 and a1= 5:
a0=c1·30+c2·0·30= 2
⇒c1= 2
a1=c1·31+c2·1·31= 5
⇒2·3+3c2= 5
⇒3c2= 5 −6
⇒c2=−1
3
Step 6: Plugging c1= 2 and c2=−1
3back into the general form:
an= 2 ·3n−1
3·n·3n
an= 2 ·3n−n
3·3n
28
Question 31
Question
Let ansatisfy the recurrence relation an+2 −5an+1 + 6an= 3nfor n≥0 with
initial conditions a0= 2 and a1= 5. Find the explicit formula for an.
Solution
To find the explicit formula for an, we first need to solve the associated ho-
mogeneous recurrence relation. Then, we will find a particular solution for the
non-homogeneous part and combine the two solutions to get the general solu-
tion. Finally, we will use the initial conditions to determine the specific values
of the constants.
Step 1: Solve the associated homogeneous recurrence relation
an+2 −5an+1 + 6an= 0.
We seek a solution of the form an=rn. Substituting this into the recurrence
relation, we get
r2−5r+ 6 = 0.
The roots of this characteristic equation are r= 2 and r= 3. Therefore, the
general solution to the homogeneous part is
a(h)
n=A·2n+B·3n,
where Aand Bare constants to be determined.
Step 2: Find a particular solution for the non-homogeneous part. Since
3nis in the form of r= 3 for the homogeneous equation, a particular solution
can be taken as a constant times 3n, i.e., a(p)
n=C·3n. Substituting this into
the original recurrence relation, we get 27C−15C+ 6C= 3n, which implies
18C= 3n=⇒C=3n
18 =1
63n−2.
Step 3: The general solution is given by an=a(h)
n+a(p)
n=A·2n+B·3n+
1
63n−2.
Step 4: Apply the initial conditions a0= 2 and a1= 5 to determine the
values of Aand B. From a0= 2, we have A+B+1
63−2= 2. From a1= 5, we
have 2A+ 3B+1
63−1= 5. Solving these two equations simultaneously, we find
A=8
3and B=−2
3. Therefore, the explicit formula for anis
an=8
3·2n−2
3·3n+1
63n−2.
Question 32
Question
Let anbe a sequence defined recursively by the following recurrence relation:
an= 3an−1−2an−2+ 2n,for n≥2,
29
with initial conditions a0= 2 and a1= 4. Determine a closed-form expression
for an.
Solution
Step 1: Finding the homogeneous solution Let’s first consider the homo-
geneous part of the recurrence relation:
a(h)
n= 3an−1−2an−2.
The characteristic equation associated with this part is r2= 3r−2, which
simplifies to r2−3r+ 2 = 0. Factoring the quadratic gives us (r−1)(r−2) = 0,
so the roots are r1= 1 and r2= 2.
Therefore, the homogeneous solution is given by a(h)
n=C1·1n+C2·2n,
where C1and C2are constants to be determined.
Step 2: Finding the particular solution Now, we consider the particular
solution to the entire recurrence relation:
an= 3an−1−2an−2+ 2n.
Since the right-hand side term 2nis a geometric sequence, we try a particular
solution of the form a(p)
n=K·2n.
Substitute this into the original recurrence relation:
K·2n= 3(K·2n−1)−2(K·2n−2)+2n.
Simplifying this equation gives K=−2.
Therefore, the particular solution is a(p)
n=−2·2n.
Step 3: Combining solutions The general solution to the recurrence rela-
tion is the sum of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=C1·1n+C2·2n−2·2n.
Step 4: Solving for constants using initial conditions Using the initial
conditions a0= 2 and a1= 4, we have:
a0=C1+C2−2=2
a1=C1+ 2C2−4 = 4
Solving these equations simultaneously gives C1= 0 and C2= 3.
Step 5: Final closed-form expression Thus, the closed-form expression
for anis:
an= 3 ·2n−2·2n= 2 ·2n.
Question 33
Question
Consider a sequence defined by the recurrence relation an+2 = 5an+1 −6anfor
n≥0 with initial conditions a0= 2 and a1= 5. Find a closed-form expression
for an.
30
Solution
Step 1: First, we find the characteristic equation associated with the given
recurrence relation. The characteristic equation is obtained by setting an+2 =
5an+1 −6anto zero and replacing an+2 by r2,an+1 by r, and anby 1:
r2= 5r−6
Step 2: Simplifying the above equation gives us:
r2−5r+ 6 = 0
Step 3: Factoring the quadratic equation, we get:
(r−2)(r−3) = 0
Step 4: The roots of the characteristic equation are r= 2 and r= 3, so the
general solution to the recurrence relation is:
an=c1·2n+c2·3n
Step 5: Now, we use the initial conditions a0= 2 and a1= 5 to find the
values of c1and c2.
Step 6: Substituting n= 0 into the general solution gives us:
a0=c1·20+c2·30=c1+c2= 2
Step 7: Substituting n= 1 into the general solution gives us:
a1=c1·21+c2·31= 2c1+ 3c2= 5
Step 8: Solving the system of equations formed by Steps 6 and 7, we find
c1= 3 and c2=−1.
Step 9: Therefore, the closed-form expression for anis:
an= 3 ·2n−3n
Question 34
Question
Consider the non-homogeneous recurrence relation defined by an= 4an−1−
4an−2+ 2n, where a0= 1 and a1= 3. Find a closed-form expression for an.
31
Solution
Step 1: First, we find the general solution to the corresponding homogeneous
equation a(h)
n= 4a(h)
n−1−4a(h)
n−2.
The characteristic equation of the homogeneous equation is r2= 4r−4,
which simplifies to r2−4r+ 4 = 0. This equation factors as (r−2)2= 0, which
gives a repeated root of r= 2.
Therefore, the general solution to the homogeneous equation is a(h)
n= (c1+
c2n)2n, where c1and c2are constants to be determined.
Step 2: Next, we find a particular solution to the non-homogeneous equation
a(p)
n= 2n.
Since the non-homogeneous term 2nis of the same form as the non-homogeneous
term, we can guess a particular solution of the form a(p)
n=B2n, where Bis a
constant to be determined.
Substitute this particular form back into the original non-homogeneous equa-
tion: B2n= 4B2n−1−4B2n−2+ 2n.
Simplify to get 2B= 4B−4B+ 1, which implies 2B= 1 and thus B=1
2.
Therefore, a particular solution to the non-homogeneous equation is a(p)
n=
1
22n= 2n−1.
Step 3: The general solution to the non-homogeneous equation is the sum of
the general solution to the homogeneous equation and the particular solution:
an=a(h)
n+a(p)
n= (c1+c2n)2n+ 2n−1.
Step 4: Using the initial conditions a0= 1 and a1= 3, we find the values of
c1and c2.
Substitute the initial conditions into the general solution: 1 = c1and 3 =
2c1+ 2, which gives c1= 1 and c2= 1.
Therefore, the closed-form expression for anis an= 2n+n2n+ 2n−1.
Question 35
Question
Let {an}be a sequence defined by the recurrence relation an= 3an−1−2an−2
for n≥3, where a1= 1 and a2= 2. Find an explicit formula for an.
Solution
Step 1: Find the characteristic equation
The characteristic equation for the given recurrence relation an= 3an−1−2an−2
is given by:
r2= 3r−2
r2−3r+ 2 = 0
(r−1)(r−2) = 0
r= 1,2
32
Solving the system of equations gives c1= 3 and c2=−1. Therefore, the
formula for anis an= 3 ·1n−1·2n. Simplifying further, we get:
an= 3 −2n
Question 3
Question
Let ansatisfy the non-homogeneous recurrence relation an= 3an−1−2an−2+2n.
If a0= 1 and a1= 2, find a formula for anin terms of n.
Solution
Step 1: First, let’s find the general solution to the corresponding homogeneous
recurrence relation an= 3an−1−2an−2. The characteristic equation is r2=
3r−2, which simplifies to r2−3r+ 2 = 0. The roots of this equation are r1= 1
and r2= 2. Therefore, the general solution to the homogeneous part of the
recurrence relation is a(h)
n=c1·1n+c2·2n.
Step 2: Next, we need to find a particular solution for the non-homogeneous
part 2n. We assume the particular solution has the form a(p)
n=A·2n. Substi-
tuting this into the original non-homogeneous recurrence relation, we get:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
A·2n= 3A·2n−1−2A·2n−2+ 2n
A=2n
2= 2n−1
So, the particular solution is a(p)
n= 2n−1.
Step 3: Therefore, the general solution to the non-homogeneous recurrence
relation is the sum of the general solution to the homogeneous part and the
particular solution to the non-homogeneous part:
an=a(h)
n+a(p)
n=c1·1n+c2·2n+ 2n−1
Step 4: To find the values of c1and c2, we use the initial conditions a0= 1
and a1= 2:
a0=c1·10+c2·20+ 2−1=c1+c2+1
2= 1
a1=c1·11+c2·21+ 20=c1+ 2c2+ 1 = 2
Solving these equations, we find c1=1
2and c2=1
2. Therefore, the formula
for anin terms of nis:
an=1
2+1
2·2n+ 2n−1=1
2+ 2n+ 2n−1
3
Question 4
Question
Consider the following recurrence relation:
an= 6an−1−9an−2+ 4n
Given that the initial conditions are a0= 1 and a1= 3, find a closed-form
expression for an.
Solution
Step 1: Finding the homogeneous solution Let’s first consider the homogeneous
part of the recurrence relation:
an= 6an−1−9an−2
The characteristic equation associated with this homogeneous recurrence rela-
tion is:
r2= 6r−9
r2−6r+ 9 = 0
(r−3)2= 0
This gives us a repeated root r= 3.
Therefore, the homogeneous solution is of the form:
a(h)
n=c1·3n+c2·n·3n
Step 2: Finding the particular solution Now, let’s find a particular solution
for the non-homogeneous part. Since the non-homogeneous term is 4n, we
assume a particular solution of the form a(p)
n=A·4n.
Substitute an=A·4nback into the original recurrence relation:
A·4n= 6(A·4n−1)−9(A·4n−2)+4n
A=4n
7
Therefore, the particular solution is a(p)
n=4n
7.
Step 3: Finding the complete solution The complete solution is the sum of
the homogeneous and particular solutions:
an=a(h)
n+a(p)
n
an=c1·3n+c2·n·3n+4n
7
4
Step 4: Applying initial conditions Using the initial conditions a0= 1 and
a1= 3:
a0= 1 →c1+1
7= 1
a1= 3 →3c1+ 3c2+4
7= 3
Solving these two equations gives c1=6
7and c2=−2
7.
Thus, the closed-form expression for anis:
an=6
7·3n−2
7·n·3n+4n
7
Question 5
Question
Let anbe defined by the recurrence relation an= 6an−1−9an−2for all integers
n≥2 with initial conditions a0= 3 and a1= 6. Find a formula for an.
Solution
Step 1: Find the characteristic equation by assuming an=rnfor some constant
r.
rn= 6rn−1−9rn−2
Divide through by rn−2to get
r2= 6r−9
r2−6r+ 9 = 0
(r−3)2= 0
r= 3
Step 2: Since the characteristic equation has a repeated root, the general
form of the solution will be
an= (A+Bn)3n
for some constants Aand B.
Step 3: Use the initial conditions a0= 3 and a1= 6 to solve for Aand B.
a0= (A)30=A= 3
a1= (A+B)31= 3 + 3B= 6
B= 1
Step 4: Thus, the formula for anis
an= 3 + n·3n
5
Question 6
Question
Consider the non-homogeneous recurrence relation an= 2an−1−3an−2+ 2n
with initial conditions a0= 1 and a1= 2. Find the explicit formula for an.
Solution
Step 1: Find the homogeneous solution a(H)
nby solving the characteristic equa-
tion r2−2r+ 3 = 0. The characteristic equation has roots r= 1 ±i√2, so the
homogeneous solution is of the form
a(H)
n=c1·(1 + i√2)n+c2·(1 −i√2)n.
Step 2: Find a particular solution a(P)
nof the non-homogeneous equation.
We guess a particular solution of the form a(P)
n=A·2n. Substitute this into
the non-homogeneous equation to get
A·2n= 2(A·2n−1)−3(A·2n−2)+2n.
Step 3: Solve for A in the above equation. Solving the equation yields
A=−2
3.
Step 4: Write down the general solution. The general solution is given by
an=a(H)
n+a(P)
n=c1·(1 + i√2)n+c2·(1 −i√2)n−2
3·2n.
Step 5: Apply the initial conditions to find c1and c2. Using a0= 1 and
a1= 2, we can find c1and c2.
c1+c2−2
3= 1
c1·(1 + i√2) + c2·(1 −i√2) −4
3= 2.
Solving these simultaneous equations gives c1=5
6and c2=1
6.
Step 6: Plug in the values of c1and c2into the general solution. Therefore,
the explicit formula for anis
an=5
6·(1 + i√2)n+1
6·(1 −i√2)n−2
3·2n.
Question 7
Question
Consider the following non-homogeneous recurrence relation:
an+2 −8an+1 + 16an=n
Find the general solution to this non-homogeneous recurrence relation.
6
Solution
To find the general solution to the non-homogeneous recurrence relation, we
need to first find the general solution to the associated homogeneous recurrence
relation, then find a particular solution to the non-homogeneous part, and finally
add these two solutions together.
Step 1: Find the general solution to the associated homogeneous
recurrence relation.
The associated homogeneous recurrence relation is obtained by setting the
right-hand side to 0:
an+2 −8an+1 + 16an= 0
The characteristic equation is:
r2−8r+ 16 = 0
Solving this quadratic equation, we find that r= 4. Thus, the general
solution to the associated homogeneous recurrence relation is:
an=c1·4n+c2·n·4n
where c1and c2are constants to be determined.
Step 2: Find a particular solution to the non-homogeneous part.
To find a particular solution, we assume that anhas the form of the right-
hand side of the non-homogeneous relation, n. Since it is a linear function, we
assume an=An +B.
Substitute an=An +Bback into the original non-homogeneous recurrence
relation:
(A(n+ 2) + B)−8(A(n+ 1) + B) + 16(An +B) = n
Solving for Aand B, we get A=1
2and B=1
16 .
Therefore, the particular solution is an=1
2n+1
16 .
Step 3: Write out the general solution.
The general solution to the non-homogeneous recurrence relation is the sum
of the general solution to the associated homogeneous recurrence relation and
the particular solution to the non-homogeneous part:
an=c1·4n+c2·n·4n+1
2n+1
16
Question 8
Question
Let (an) be a sequence defined by the recurrence relation an+2 = 4an+1−4an+3n
for n≥0 with initial conditions a0= 1 and a1= 2. Find a closed-form
expression for an.
7
Solution
Step 1: Write down the characteristic equation associated with the homogeneous
part of the recurrence relation: an+2 = 4an+1 −4an. The characteristic equation
is r2= 4r−4, which simplifies to r2−4r+4 = 0. Factoring this gives (r−2)2= 0,
so we have a repeated root r= 2.
Step 2: Use the repeated root r= 2 to write down the solution to the
homogeneous part. The solution to the homogeneous part is then a(h)
n= (c1+
c2n)2n.
Step 3: Find a particular solution to the non-homogeneous part of the re-
currence relation. Since the non-homogeneous part is 3n, we try a particular
solution of the form a(p)
n=An3n. Substituting this into the original recurrence
relation gives:
An3n+2 = 4An3n+1 −4An3n+ 3n.
Step 4: Solve for Aby comparing coefficients of 3n. Solving An3n+2 =
4An3n+1 −4An3n+ 3nfor Agives:
9A= 12A−4A+ 1,
which simplifies to A=1
4.
Step 5: Write down the general solution to the non-homogeneous part. The
general solution to the non-homogeneous part is a(p)
n=1
4n3n.
Step 6: Combine the homogeneous and non-homogeneous solutions to get
the general solution. The general solution to the original recurrence relation is
then:
an=a(h)
n+a(p)
n= (c1+c2n)2n+1
4n3n.
Step 7: Use the initial conditions a0= 1 and a1= 2 to solve for c1and
c2. Substitute n= 0 and n= 1 into an= (c1+c2n)2n+1
4n3nand solve the
resulting system of equations to find c1and c2.
Thus, the closed-form expression for anis:
an=3
22n+1
4n3n−1
2.
Question 9
Question
Find a closed-form expression for the following non-homogeneous recurrence
relation:
an= 3an−1−2an−2+ 2nwith initial conditions a0= 1 and a1= 2.
8
Solution
To find a closed-form expression for the non-homogeneous recurrence relation,
we need to solve the homogeneous part an= 3an−1−2an−2and then find a
particular solution for the non-homogeneous part an= 2n.
Step 1: Solve the homogeneous part The characteristic equation of the
homogeneous part is given by r2= 3r−2 which simplifies to r2−3r+ 2 = 0.
The roots of this characteristic equation are r1= 1 and r2= 2.
Therefore, the general solution of the homogeneous part is a(h)
n=c1·1n+
c2·2n.
Step 2: Find a particular solution Since the non-homogeneous part is
2n, we can try a particular solution of the form a(p)
n=A·2n. Substituting this
into the original recurrence relation, we get:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
Solving this equation, we find A=2
3. Therefore, a particular solution is
a(p)
n=2
3·2n.
Step 3: Determine the complete solution The complete solution is the
sum of the general solution of the homogeneous part and the particular solution:
an=a(h)
n+a(p)
n=c1·1n+c2·2n+2
3·2n
Step 4: Apply initial conditions Using the initial conditions a0= 1 and
a1= 2, we can find c1and c2.
a0= 1 : c1+c2+2
3= 1
a1=2: c1+ 2c2+4
3= 2
Solving these equations, we find c1=1
3and c2=1
3.
Step 5: Final solution Therefore, the closed-form expression for anis:
an=1
3·1n+1
3·2n+2
3·2n
Question 10
Question
Let anbe a sequence defined by the recurrence relation an+2 = 3an+1 −2an+n2,
where a0= 1 and a1= 2. Find a closed-form expression for an.
9
Solution
Step 1: Find the homogeneous solution. We first consider the homogeneous part
of the recurrence relation, which is an+2 = 3an+1 −2an. Setting an=rn, we
get the characteristic equation r2= 3r−2, which simplifies to r2−3r+ 2 = 0.
Factoring, we find (r−2)(r−1) = 0, so the solutions are r= 1 and r= 2.
Therefore, the homogeneous solution is a(h)
n=A(1)n+B(2)nfor some constants
Aand B.
Step 2: Find a particular solution. Now, we need to find a particular solution
to the non-homogeneous part of the recurrence relation, n2. Since the non-
homogeneous term is a polynomial of degree 2, we guess a particular solution
of the form a(p)
n=cn2+dn +e. Substituting this into the original recurrence
relation, we get
c(n+ 2)2+d(n+ 2) + e= 3(c(n+ 1)2+d(n+ 1) + e)−2(cn2+dn +e) + n2.
This simplifies to c=1
2and d=−1. There is no contribution from the constant
term, so eis arbitrary. Thus, a particular solution is a(p)
n=1
2n2−n+e.
Step 3: Combine the solutions. The general solution is the sum of the
homogeneous and particular solutions, so
an=A(1)n+B(2)n+1
2n2−n+e.
Step 4: Solve for the constants. Using the initial conditions a0= 1 and
a1= 2, we get a system of equations to solve for A,B, and e:
A+B+e= 1
A(1) + B(2) + 1
2−1 + e= 2
Solving this system, we find A= 0, B=3
2, and e=1
2.
Therefore, the closed-form expression for anis an=3
2(2)n+1
2n2−n+1
2.
Question 11
Question
Let’s consider the recurrence relation defined as an= 2an−1−3an−2with initial
conditions a0= 1 and a1= 4. Solve this recurrence relation and find a formula
for an.
Solution
Step 1: Find the characteristic equation by assuming the solution is of the form
an=rn. The characteristic equation is given by r2= 2r−3, which simplifies
to r2−2r+ 3 = 0.
10
Step 2: Solve the characteristic equation to find the roots. Using the
quadratic formula, we have r=2±√(−2)2−4∗1∗3
2∗1. This simplifies to r= 1 ±i√2.
Step 3: Write the general solution using the roots. Since the roots are
complex conjugates, the general solution is an=c1(1 + i√2)n+c2(1 −i√2)n.
Step 4: Use the initial conditions to find the values of c1and c2. Substitute
a0= 1 and a1= 4 into the general solution: For a0= 1, we get c1+c2= 1. For
a1= 4, we get c1(1 + i√2) + c2(1 −i√2) = 4.
Step 5: Solve the system of equations from step 4 to find c1and c2. From
the first equation, we can write c1in terms of c2as c1= 1 −c2. Substitute c1
in the second equation and solve for c2.
Step 6: Once c2is found, substitute back to find c1.
Step 7: Finally, substitute the values of c1and c2into the general solution
to get the formula for an.
Question 12
Question
Let anbe the sequence defined by the recurrence relation an+2−5an+1+6an= 0,
with initial conditions a0= 1 and a1= 3. Find an explicit formula for an.
Solution
Step 1: First, we need to find the characteristic equation for the given recurrence
relation. Let’s assume an=rnand substitute it into the relation to get rn(r2−
5r+ 6) = 0. Therefore, the characteristic equation is r2−5r+ 6 = 0.
Step 2: We can factor the characteristic equation to get (r−2)(r−3) = 0.
Thus, the roots are r1= 2 and r2= 3.
Step 3: Since the roots are distinct, the general solution to the recurrence
relation is given by an=A·2n+B·3n.
Step 4: Using the initial conditions a0= 1 and a1= 3, we can set up a
system of equations to solve for Aand B. Substituting n= 0 and n= 1 into
the general solution, we get:
(A+B= 1
2A+ 3B= 3
Step 5: Solving the system of equations, we find A=3
2and B=−1
2.
Step 6: Therefore, the explicit formula for the sequence anis an=3
2·2n−
1
2·3n.
11
Question 13
Question
Let anbe defined by the recurrence relation an= 4an−1−4an−2for n≥2, with
initial conditions a0= 2 and a1= 3. Find a formula for an.
Solution
Step 1: Find the characteristic equation by assuming an=rnwhere ris a
constant.
rn= 4rn−1−4rn−2
Divide both sides by rn−2to simplify:
r2= 4r−4
r2−4r+ 4 = 0
(r−2)2= 0
This gives us a repeated root r= 2.
Step 2: The general solution to the homogeneous recurrence relation is of
the form an=c1·2n+c2·n·2n.
Step 3: Use the initial conditions to find the values of c1and c2.
a0=2=c1·20+c2·0·20=c1
a1=3=c1·21+c2·1·21= 2c1+ 2c2
Solving these equations give c1= 2 and c2=−1
2.
Step 4: The formula for anis thus an= 2 ·2n−1
2·n·2n.
Question 14
Question
Let ansatisfy the recurrence relation an= 2an−1−3an−2for n≥2, with initial
conditions a0= 2 and a1= 1. Find a closed-form expression for an.
Solution
Step 1: Find the characteristic equation by assuming a solution of the form
an=rn.
rn= 2rn−1−3rn−2
Divide by rn−2:
r2= 2r−3
r2−2r+ 3 = 0
12
Step 2: Solve the characteristic equation. We can solve the quadratic equa-
tion r2−2r+ 3 = 0 using the quadratic formula:
r=−(−2) ±p(−2)2−4∗1∗3
2∗1
r=2±√4−12
2
r= 1 ±i√2
Step 3: Write the general solution as a linear combination of the basis of
solutions. The general solution to the homogeneous equation is:
an=c1(1 + i√2)n+c2(1 −i√2)n
Step 4: Use the initial conditions to solve for c1and c2.
a0=2=c1+c2
a1= 1 = c1(1 + i√2) + c2(1 −i√2)
Step 5: Solve the equations to find c1and c2. We have a system of equations:
c1+c2= 2
c1(1 + i√2) + c2(1 −i√2) = 1
Solving this system, we find c1=2
3−1
3i√2 and c2=4
3+1
3i√2.
Therefore, the closed-form expression for anis:
an=2
3(1 + i√2)n+4
3(1 −i√2)n
Question 15
Question
Consider the following non-homogeneous recurrence relation:
an= 2an−1−an−2+ 2n
with initial conditions a0= 1 and a1= 2. Find the explicit formula for an.
Solution
To solve the non-homogeneous recurrence relation, we first need to find the
general solution to the associated homogeneous recurrence relation:
an= 2an−1−an−2
13
Step 1: Find the general solution to the homogeneous recurrence
relation Assume the solution to the homogeneous recurrence relation is in the
form an=rn. Substituting this into the homogeneous recurrence relation, we
get:
rn= 2rn−1−rn−2
r2= 2r−1
The characteristic equation is 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:
an=c1·1n+c2·n·1n=c1+c2n
Step 2: Find a particular solution to the non-homogeneous recur-
rence relation To find a particular solution to the non-homogeneous recurrence
relation, we make an educated guess based on the form of the non-homogeneous
term. Since 2nis an exponential function and the recurrence relation is linear,
we guess a particular solution of the form an=An2n, where Ais a constant to
be determined. Substituting this into the recurrence relation, we get:
An2n= 2(A(n−1)2n−1)−A(n−2)2n−2+ 2n
Simplify the equation above to find A.
Step 3: Determine the value of AWorking out the equation obtained
from Step 2, we get:
An2n= 2A(n−1)2n−1−A(n−2)2n−2+ 2n
Now, solve for A.
Step 4: Find the explicit formula for anThe explicit formula for anis
the sum of the general solution to the homogeneous recurrence relation and the
particular solution to the non-homogeneous recurrence relation:
an=c1+c2n+An2n
Using the initial conditions a0= 1 and a1= 2, we can solve for c1,c2, and
Ato find the explicit formula for an.
Question 16
Question
Consider the non-homogeneous recurrence relation an= 4an−1−4an−2+ 2n
with initial conditions a0= 1 and a1= 3. Find a closed-form expression for an.
14
Solution
Step 1: First, let’s find the corresponding homogeneous recurrence relation. We
do this by setting the non-homogeneous term to zero. Therefore, the homoge-
neous recurrence relation is a(h)
n= 4an−1−4an−2.
Step 2: Next, we seek for a particular solution of the non-homogeneous re-
currence relation. Since the non-homogeneous term 2nis a geometric sequence,
it is reasonable to assume a particular solution of the form a(p)
n=A2n, where
Ais a constant to be determined.
Step 3: Substituting a(p)
n=A2ninto the non-homogeneous recurrence rela-
tion, we get
A2n= 4(A2n−1)−4(A2n−2)+2n
Step 4: Simplifying the above equation, we have
A= 4A2−1−4A2−2+ 1
Step 5: Solving the above equation, we find A=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 recurrence relation is
given by the sum of the homogeneous solution and the particular solution, i.e.,
an=a(h)
n+a(p)
n.
Step 8: With the initial conditions a0= 1 and a1= 3, we find a(h)
0= 1 and
a(h)
1= 3.
Step 9: Therefore, a0=a(h)
0+a(p)
0, which implies 1 = 1 + A. Thus, A= 0.
Step 10: Similarly, a1=a(h)
1+a(p)
1gives 3 = 3 + A. This also yields A= 0.
Step 11: Hence, the closed-form expression for anis an=a(h)
n+a(p)
n=
a(h)
n= 2n−1.
Question 17
Question
Consider the following non-homogeneous recurrence relation:
an= 2an−1+ 3n
where a0= 1.
Find a closed-form expression for an.
Solution
To solve this non-homogeneous recurrence relation, we first find the complemen-
tary function CF by solving the corresponding homogeneous relation:
a(H)
n= 2an−1
15
Step 1: Find the homogeneous solution The characteristic equation is
given by:
r−2=0
r= 2
So the homogeneous solution is:
a(H)
n=c·2n
Step 2: Find the particular solution We guess that the particular solu-
tion is of the form a(P)
n=An ·3n.
Step 3: Substitute the particular solution into the original recur-
rence relation
An ·3n= 2(An −1·3n−1)+3n
An ·3n= 2A(n−1) ·3n+ 3n
Step 4: Solve for A Solving for A, we get:
An = 2A(n−1) + 1
An = 2An −2A+ 1
A=−1
Step 5: Write down the particular solution The particular solution is
a(P)
n=−n·3n
Step 6: Write down the general solution and solve for cusing the
initial condition The general solution is given by:
an=a(H)
n+a(P)
n
an=c·2n−n·3n
Using the initial condition a0= 1:
1 = c−0
c= 1
Step 7: Final solution Therefore, the closed-form expression for anis:
an= 2n−n·3n
Question 18
Question
Let anbe a sequence defined by the recurrence relation an= 2an−1−an−2+1 for
all integers n≥2, with initial conditions a0= 1 and a1= 3. Find a closed-form
expression for an.
16
Solution
Step 1: First, let’s find the characteristic polynomial of the recurrence relation.
The characteristic polynomial is obtained by setting an=xnand substituting
it into the recurrence relation an= 2an−1−an−2+ 1:
xn= 2xn−1−xn−2+ 1
Step 2: Rearrange the equation to obtain the characteristic polynomial:
xn−2xn−1+xn−2−1 = 0
xn−2(x2−2x+ 1) −1=0
xn−2(x−1)2−1=0
Step 3: The characteristic equation has a repeated root of 1. Therefore, the
general solution takes the form:
an=A·1n+B·n·1n
an=A+Bn
Step 4: Next, we use the initial conditions a0= 1 and a1= 3 to solve for A
and B. From a0= 1:
A= 1
Step 5: From a1= 3:
A+B(1) = 3
1 + B= 3
B= 2
Step 6: Therefore, the closed-form expression for anis:
an= 1 + 2n
Question 19
Question
Let anbe defined by the recurrence relation an= 2an−1−2an−2for n≥2 with
initial conditions a0= 1 and a1= 2. Find a closed-form expression for an.
17
Solution
To solve the given recurrence relation, we first need to find the characteristic
equation associated with it. The characteristic equation is given by r2= 2r−2,
which simplifies to r2−2r+ 2 = 0.
Step 1: Find the roots of the characteristic equation Using the
quadratic formula, we find that the roots of the characteristic equation are
r=2±√22−4·1·2
2= 1 ±i. Therefore, the general solution to the homogeneous
recurrence relation is of the form an=c1·(1 + i)n+c2·(1 −i)n.
Step 2: Use initial conditions to determine c1and c2Substitute the
initial conditions a0= 1 and a1= 2 into the general solution:
(a0=c1(1 + i)0+c2(1 −i)0=c1+c2= 1
a1=c1(1 + i)1+c2(1 −i)1=c1(1 + i) + c2(1 −i)=2
From the first equation, we have c2= 1 −c1. Substitute this into the second
equation:
c1(1 + i) + (1 −c1)(1 −i)=2
c1+ic1+ 1 −i−c1+ic1= 2
2ic1−i= 1
c1=1 + i
2i
c1=1
2−1
2i
Therefore, c2= 1 −c1=1
2+1
2i. Substituting back into the general solution,
we get:
an=1
2−1
2i(1 + i)n+1
2+1
2i(1 −i)n
Hence, the closed-form expression for anis an=1
22ncos(nπ/4)+ 1
22nsin(nπ/4)
or an= 2n−1cos(nπ/4) + 2n−1sin(nπ/4).
Question 20
Question
Consider the non-homogeneous recurrence relation an= 2an−1−an−2+2nwith
initial conditions a0= 1 and a1= 3. Find a closed-form expression for an.
18
Solution
Step 1: First, solve the associated homogeneous recurrence relation a(h)
n=
2a(h)
n−1−a(h)
n−2.
Characteristic equation: r2−2r+ 1 = 0
(r−1)2= 0
r= 1 (Repeated root)
So the general solution for the homogeneous part is a(h)
n=c1·1n+c2·n·1n=
c1+c2n.
Step 2: Now, find a particular solution for the non-homogeneous recurrence
relation. Let’s guess a particular solution of the form a(p)
n=A·2n. Substitute
into the non-homogeneous recurrence relation to get:
−A·2n−2= 2 ·(−A·2n−1)−(−A·2n−2)+2n
Solving this, we find A=1
3.
So the particular solution is a(p)
n=1
3·2n.
Step 3: The general solution for the non-homogeneous part is the sum of the
homogeneous and particular solutions.
an=a(h)
n+a(p)
n=c1+c2n+1
3·2n
Step 4: Using the initial conditions a0= 1 and a1= 3, we can find the
values of c1and c2.
a0=c1+c2·0 + 1
3·20= 1
c1+1
3= 1
c1=2
3
a1=c1+c2·1 + 1
3·21= 3
2
3+c2+2
3= 3
c2=5
3
Step 5: Thus, the closed-form expression for anis an=2
3+5
3n+1
3·2n.
Question 21
Question
Consider the non-homogeneous recurrence relation given by
19
an= 3an−1−2an−2+ 2n
with initial conditions a0= 1 and a1= 2. Find the explicit formula for an.
Solution
Step 1: First, find the homogeneous solution a(H)
nby setting the right-hand
side to zero and solving the characteristic equation rn= 3rn−1−2rn−2. The
characteristic equation is r2−3r+ 2 = 0, which factors as (r−1)(r−2) = 0.
So, the roots are r1= 1 and r2= 2, and the homogeneous solution is a(H)
n=
A·1n+B·2n, where Aand Bare constants to be determined.
Step 2: Next, find a particular solution a(P)
nby guessing that it has the form
a(P)
n=C·2n. Substitute an=C·2ninto the original recurrence relation to
find C:
C·2n= 3(C·2n−1)−2(C·2n−2)+2n
C·2n= 3C·2n−1−2C·2n−2+ 2n
C=2n
2= 2n−1
Therefore, a(P)
n= 2n−1.
Step 3: The general solution is the sum of the homogeneous and particular
solutions: an=a(H)
n+a(P)
n. Plugging in the initial conditions a0= 1 and
a1= 2, we can solve for Aand B: 1 = A+B(from a0= 1)
2 = A+ 2B(from a1= 2)
Solving these equations gives A=−1 and B= 2, so the explicit formula for
anis
an=−1·1n+ 2 ·2n= 2n+1 −1
Question 22
Question
Let anbe defined by the recurrence relation an= 2an−1−2an−2+ 3nfor n≥2,
where a0= 1 and a1= 3. Find a closed-form expression for an.
Solution
Step 1: Solve the homogeneous part of the recurrence relation.
The homogeneous part is an= 2an−1−2an−2. We can try a solution of the
form an=rnfor some r:
rn= 2rn−1−2rn−2
r2= 2r−2
r2−2r+ 2 = 0
20
This equation has complex roots r= 1 ±i. Therefore, the solution to the
homogeneous part is of the form:
a(h)
n=c1(1 + i)n+c2(1 −i)n
Step 2: Find a particular solution for the non-homogeneous part.
The non-homogeneous term is 3n, which is a geometric sequence. We can
make an educated guess that a particular solution is of the form a(p)
n=A·3n.
Substitute an=A·3ninto the original recurrence relation:
A·3n= 2(A·3n−1)−2(A·3n−2)+3n
A·3n= 2A·3n−2A·3n−1+ 3n
A=3n
3n−2·3n−1+ 2 ·3n−2
A=3n
3n−6·3n−2+ 6 ·3n−2
A=3n
3n−6·3n−1
A=1
1−2·3−1
A=1
1−2/3
A=3
1
A= 3
So, a particular solution for the non-homogeneous part is a(p)
n= 3·3n= 3n+1.
Step 3: Combine the homogeneous and particular solutions.
Therefore, the general solution to the recurrence relation is:
an=a(h)
n+a(p)
n=c1(1 + i)n+c2(1 −i)n+ 3n+1
Step 4: Use initial conditions to find c1and c2.
Using the initial conditions a0= 1 and a1= 3:
a0=c1(1 + i)0+c2(1 −i)0+ 31=c1+c2+ 3 = 1
a1=c1(1 + i)1+c2(1 −i)1+ 32=c1(1 + i) + c2(1 −i) + 9 = 3
Solving this system of equations, we find c1=3
2−3i
2and c2=3
2+3i
2.
Therefore, the closed-form expression for anis:
an= (3
2−3i
2)(1 + i)n+ (3
2+3i
2)(1 −i)n+ 3n+1
21
Question 23
Question
Let anbe a sequence defined recursively by the relation an+1 = 2an−2nfor
n≥0 with the initial condition a0= 4. Find a closed-form expression for an.
Solution
Step 1: Write the characteristic equation for the homogeneous version of the
recurrence relation.
The homogeneous version of the recurrence relation is an+1 = 2an. This
gives us the characteristic equation r= 2, with the solution a(h)
n=C·2n.
Step 2: Find a particular solution for the non-homogeneous part.
For the non-homogeneous part −2n, we try a particular solution of the form
a(p)
n=An ·2n. Substituting this into the original recurrence relation gives:
An ·2n+1 = 2(An ·2n)−2n
An ·2n+1 = 2An ·2n−2n
An ·2·2n= 2An ·2n−2n
2An ·2n= 2An ·2n−2n
2n= 0
This implies that A=−1/2.
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−1
2·n·2n
Step 4: Apply the initial condition to solve for C.
Given that a0= 4, we have:
4 = C·20−1
2·0·20
4 = C
Step 5: Write the closed-form expression for an.
Thus, the closed-form expression for anis:
an= 4 ·2n−1
2·n·2n
Question 24
Question
Let anbe a sequence defined by the recurrence relation an+2 −4an+1 +4an= 2n
for n≥0 with initial conditions a0= 1 and a1= 2. Find a closed-form
expression for an.
Solution
Step 1: First, let’s find the characteristic equation for the homogeneous part of
the recurrence relation. The characteristic equation is given by r2−4r+ 4 = 0.
22
This factors to (r−2)2= 0, so we have a repeated root r= 2.
Step 2: The solution to the homogeneous part is then given by a(h)
n=
c1·2n+c2·n·2n.
Step 3: Now, let’s find a particular solution to the non-homogeneous part
of the recurrence relation. Since the right-hand side is 2n, a good guess for a
particular solution is a(p)
n=A·2n.
Step 4: Substituting a(p)
n=A·2ninto the recurrence relation gives:
(A·2n+2)−4(A·2n+1) + 4(A·2n)=2n.
Step 5: This simplifies to 4A−4A+ 4A= 1, so 4A= 1 and A=1
4.
Step 6: Therefore, the particular solution is a(p)
n=1
4·2n.
Step 7: Combining the homogeneous and particular solutions, the general
solution is:
an=a(h)
n+a(p)
n=c1·2n+c2·n·2n+1
4·2n.
Step 8: Using the initial conditions a0= 1 and a1= 2, we can find the
values of c1and c2. Plugging in n= 0: c1+c2+1
4= 1. Plugging in n= 1:
2c1+ 2c2+1
2= 2.
Step 9: Solving the system of equations, we find c1=1
2and c2=−1
4.
Step 10: Therefore, the closed-form expression for anis an=1
2·2n−1
4·n·
2n+1
4·2n.
Question 25
Question
Let andenote the nth term of a sequence defined by the recurrence relation
an+2 −5an+1 + 6an= 0 for all integers n≥0, with initial conditions a0= 4
and a1= 6. Find a formula for anfor all non-negative integers n.
Solution
Step 1: Find the characteristic equation. Given the recurrence relation an+2 −
5an+1 + 6an= 0, we represent it as a characteristic equation r2−5r+ 6 = 0.
Simplifying, we get (r−2)(r−3) = 0, so the roots are r1= 2 and r2= 3.
Step 2: Find the general solution. Since the roots are distinct, the general
solution takes the form an=c1·2n+c2·3n.
Step 3: Determine the values of c1and c2. Using the initial conditions a0= 4
and a1= 6, we have the system of equations: c1+c2= 4, 2c1+ 3c2= 6.
Solving this system, we find c1= 3 and c2= 1.
Step 4: Write the formula for an. Therefore, the formula for anis an=
3·2n+ 1 ·3n.
23
Question 26
Question
Let andenote the nth term of a sequence defined by the recurrence relation
an+1 = 2an−an−1where a0= 1 and a1= 2. Find a closed-form expression for
an.
Solution
Step 1: Find the characteristic equation. The characteristic equation for the
given recurrence relation is r2= 2r−1.
Step 2: Solve for the roots of the characteristic equation. To find the roots
of the characteristic equation, we need to solve r2−2r+ 1 = 0. This factors as
(r−1)2= 0, so r= 1 with multiplicity 2.
Step 3: Write down the general form of the solution. Since r= 1 is a
repeated root, the general form of the solution is an= (c1+c2n)·1n.
Step 4: Use the initial conditions to find the values of c1and c2. Given that
a0= 1 and a1= 2, we have:
(c1= 1
c1+c2= 2
Step 5: Solve for c1and c2. From the first equation, we have c1= 1.
Substitute c1= 1 into the second equation to solve for c2: 1 + c2= 2, so c2= 1.
Step 6: Write the closed-form expression for an. Therefore, the closed-form
expression for anis an= (1 + n).
Question 27
Question
Consider a sequence defined by the recurrence relation:
an= 3an−1−2an−2+ 2n
with initial conditions a0= 1 and a1= 2. Determine the explicit formula for
an.
Solution
Step 1: First, we solve the homogeneous part of the recurrence relation. We set
an=a(h)
n:
a(h)
n= 3a(h)
n−1−2a(h)
n−2
Step 2: To solve a(h)
n, we assume the solution is of the form a(h)
n=rn, where
ris a constant.
24
Step 3: Substituting this into the homogeneous part of the equation gives
us:
rn= 3rn−1−2rn−2
Step 4: Dividing through by rn−2(assuming r= 0) gives us the characteristic
equation:
r2= 3r−2
Step 5: Solving the characteristic equation r2−3r+ 2 = 0 gives us the roots
r= 1 and r= 2.
Step 6: The solution to the homogeneous part of the recurrence relation is
then given by:
a(h)
n=c1·1n+c2·2n
a(h)
n=c1+c2·2n
Step 7: Now, we find a particular solution to the non-homogeneous part of
the recurrence relation. We will assume a(p)
n=A·2n.
Step 8: Substituting a(p)
ninto the original recurrence relation gives us:
A·2n= 3A·2n−1−2A·2n−2+ 2n
Step 9: After simplifying, we get A= 1.
Step 10: Therefore, the general solution to the non-homogeneous part is:
a(p)
n= 2n
Step 11: The general solution to the original recurrence relation is the sum
of the homogeneous and particular solutions:
an=c1+c2·2n+ 2n
Step 12: Using the initial conditions a0= 1 and a1= 2, we find c1=−1
and c2= 2.
Step 13: Therefore, the explicit formula for anis:
an=−1+2·2n+ 2n
Question 28
Question
Consider the homogeneous recurrence relation an= 3an−1−2an−2with initial
conditions a0= 1 and a1= 4. Determine a formula for anin terms of n.
25
Solution
Step 1: Find the characteristic equation by assuming an=rn. Setting an=rn
in the homogeneous recurrence relation gives:
rn= 3rn−1−2rn−2
Dividing by rn−2yields:
r2= 3r−2
r2−3r+ 2 = 0
Step 2: Solve the characteristic equation. Factoring the equation gives:
(r−1)(r−2) = 0
So, the roots are r1= 1 and r2= 2.
Step 3: Write the general solution. The general solution for the homogeneous
recurrence relation is:
an=c1(1)n+c2(2)n
an=c1+ 2nc2
Step 4: Apply the initial conditions to find c1and c2. Using the initial
conditions a0= 1 and a1= 4, we have:
a0=c1+ 20c2=c1+c2= 1
a1=c1+ 21c2=c1+ 2c2= 4
Step 5: Solve the system of equations to find c1and c2. Subtracting the first
equation from the second gives:
2c2= 3
c2=3
2
Substitute c2=3
2back into the first equation to find c1:
c1+3
2= 1
c1= 1 −3
2=−1
2
Step 6: Write the formula for an. Therefore, the formula for anin terms of
nis:
an=−1
2+3
2×2n
an=−1
2+ 3(2n)
26
Question 29
Question
Find a closed-form expression for the sequence defined by the recurrence relation
an= 5an−1−6an−2+ 2n, with initial conditions a0= 1 and a1= 3.
Solution
Step 1: Finding the homogeneous solution
Let’s first find the solution to the homogeneous part of the recurrence re-
lation by setting an=rn. Substituting this into the homogeneous part of the
recurrence relation, an= 5an−1−6an−2, we get:
rn= 5rn−1−6rn−2
Dividing by rn−2(assuming r= 0), we obtain the characteristic equation:
r2−5r+ 6 = 0
Factoring the quadratic equation, we get:
(r−2)(r−3) = 0
Thus, the homogeneous solution is:
a(h)
n=c1·2n+c2·3n
Step 2: Finding a particular solution
We now need to find a particular solution for the non-homogeneous part of
the recurrence relation, an= 2n. Since 2nis a term in the recurrence relation,
we try a particular solution of the form a(p)
n=c·2n.
Substitute this trial particular solution into the original recurrence relation:
c·2n= 5(c·2n−1)−6(c·2n−2)+2n
Solving for c, we find c=1
2.
Thus, the particular solution is a(p)
n=1
2·2n= 2n−1.
Therefore, the general solution is:
an=a(h)
n+a(p)
n=c1·2n+c2·3n+ 2n−1
Step 3: Applying initial conditions
Using the initial conditions a0= 1 and a1= 3: Substitute n= 0:
1 = c1+c2+ 1
Substitute n= 1:
3=2c1+ 3c2+ 2
Solving these equations simultaneously, we find c1=−5 and c2= 5.
Therefore, the closed-form expression for the sequence is:
an=−5·2n+ 5 ·3n+ 2n−1
27
Question 30
Question
Find a closed-form expression for the solution of the recurrence relation an=
6an−1−9an−2with initial conditions a0= 2 and a1= 5.
Solution
Step 1: Finding the characteristic equation by assuming the solution has the
form an=rn:
rn= 6rn−1−9rn−2
Step 2: Dividing everything by rn−2to simplify the equation:
r2= 6r−9
Step 3: Rewriting the equation in standard quadratic form by moving ev-
erything to one side:
r2−6r+ 9 = 0
(r−3)2= 0
Step 4: The characteristic equation has a repeated root r= 3. Thus, the
general form of the solution is:
an=c1·3n+c2·n·3n
Step 5: Applying the initial conditions a0= 2 and a1= 5:
a0=c1·30+c2·0·30= 2
⇒c1= 2
a1=c1·31+c2·1·31= 5
⇒2·3+3c2= 5
⇒3c2= 5 −6
⇒c2=−1
3
Step 6: Plugging c1= 2 and c2=−1
3back into the general form:
an= 2 ·3n−1
3·n·3n
an= 2 ·3n−n
3·3n
28
Question 31
Question
Let ansatisfy the recurrence relation an+2 −5an+1 + 6an= 3nfor n≥0 with
initial conditions a0= 2 and a1= 5. Find the explicit formula for an.
Solution
To find the explicit formula for an, we first need to solve the associated ho-
mogeneous recurrence relation. Then, we will find a particular solution for the
non-homogeneous part and combine the two solutions to get the general solu-
tion. Finally, we will use the initial conditions to determine the specific values
of the constants.
Step 1: Solve the associated homogeneous recurrence relation
an+2 −5an+1 + 6an= 0.
We seek a solution of the form an=rn. Substituting this into the recurrence
relation, we get
r2−5r+ 6 = 0.
The roots of this characteristic equation are r= 2 and r= 3. Therefore, the
general solution to the homogeneous part is
a(h)
n=A·2n+B·3n,
where Aand Bare constants to be determined.
Step 2: Find a particular solution for the non-homogeneous part. Since
3nis in the form of r= 3 for the homogeneous equation, a particular solution
can be taken as a constant times 3n, i.e., a(p)
n=C·3n. Substituting this into
the original recurrence relation, we get 27C−15C+ 6C= 3n, which implies
18C= 3n=⇒C=3n
18 =1
63n−2.
Step 3: The general solution is given by an=a(h)
n+a(p)
n=A·2n+B·3n+
1
63n−2.
Step 4: Apply the initial conditions a0= 2 and a1= 5 to determine the
values of Aand B. From a0= 2, we have A+B+1
63−2= 2. From a1= 5, we
have 2A+ 3B+1
63−1= 5. Solving these two equations simultaneously, we find
A=8
3and B=−2
3. Therefore, the explicit formula for anis
an=8
3·2n−2
3·3n+1
63n−2.
Question 32
Question
Let anbe a sequence defined recursively by the following recurrence relation:
an= 3an−1−2an−2+ 2n,for n≥2,
29
with initial conditions a0= 2 and a1= 4. Determine a closed-form expression
for an.
Solution
Step 1: Finding the homogeneous solution Let’s first consider the homo-
geneous part of the recurrence relation:
a(h)
n= 3an−1−2an−2.
The characteristic equation associated with this part is r2= 3r−2, which
simplifies to r2−3r+ 2 = 0. Factoring the quadratic gives us (r−1)(r−2) = 0,
so the roots are r1= 1 and r2= 2.
Therefore, the homogeneous solution is given by a(h)
n=C1·1n+C2·2n,
where C1and C2are constants to be determined.
Step 2: Finding the particular solution Now, we consider the particular
solution to the entire recurrence relation:
an= 3an−1−2an−2+ 2n.
Since the right-hand side term 2nis a geometric sequence, we try a particular
solution of the form a(p)
n=K·2n.
Substitute this into the original recurrence relation:
K·2n= 3(K·2n−1)−2(K·2n−2)+2n.
Simplifying this equation gives K=−2.
Therefore, the particular solution is a(p)
n=−2·2n.
Step 3: Combining solutions The general solution to the recurrence rela-
tion is the sum of the homogeneous and particular solutions:
an=a(h)
n+a(p)
n=C1·1n+C2·2n−2·2n.
Step 4: Solving for constants using initial conditions Using the initial
conditions a0= 2 and a1= 4, we have:
a0=C1+C2−2=2
a1=C1+ 2C2−4 = 4
Solving these equations simultaneously gives C1= 0 and C2= 3.
Step 5: Final closed-form expression Thus, the closed-form expression
for anis:
an= 3 ·2n−2·2n= 2 ·2n.
Question 33
Question
Consider a sequence defined by the recurrence relation an+2 = 5an+1 −6anfor
n≥0 with initial conditions a0= 2 and a1= 5. Find a closed-form expression
for an.
30
Solution
Step 1: First, we find the characteristic equation associated with the given
recurrence relation. The characteristic equation is obtained by setting an+2 =
5an+1 −6anto zero and replacing an+2 by r2,an+1 by r, and anby 1:
r2= 5r−6
Step 2: Simplifying the above equation gives us:
r2−5r+ 6 = 0
Step 3: Factoring the quadratic equation, we get:
(r−2)(r−3) = 0
Step 4: The roots of the characteristic equation are r= 2 and r= 3, so the
general solution to the recurrence relation is:
an=c1·2n+c2·3n
Step 5: Now, we use the initial conditions a0= 2 and a1= 5 to find the
values of c1and c2.
Step 6: Substituting n= 0 into the general solution gives us:
a0=c1·20+c2·30=c1+c2= 2
Step 7: Substituting n= 1 into the general solution gives us:
a1=c1·21+c2·31= 2c1+ 3c2= 5
Step 8: Solving the system of equations formed by Steps 6 and 7, we find
c1= 3 and c2=−1.
Step 9: Therefore, the closed-form expression for anis:
an= 3 ·2n−3n
Question 34
Question
Consider the non-homogeneous recurrence relation defined by an= 4an−1−
4an−2+ 2n, where a0= 1 and a1= 3. Find a closed-form expression for an.
31
Solution
Step 1: First, we find the general solution to the corresponding homogeneous
equation a(h)
n= 4a(h)
n−1−4a(h)
n−2.
The characteristic equation of the homogeneous equation is r2= 4r−4,
which simplifies to r2−4r+ 4 = 0. This equation factors as (r−2)2= 0, which
gives a repeated root of r= 2.
Therefore, the general solution to the homogeneous equation is a(h)
n= (c1+
c2n)2n, where c1and c2are constants to be determined.
Step 2: Next, we find a particular solution to the non-homogeneous equation
a(p)
n= 2n.
Since the non-homogeneous term 2nis of the same form as the non-homogeneous
term, we can guess a particular solution of the form a(p)
n=B2n, where Bis a
constant to be determined.
Substitute this particular form back into the original non-homogeneous equa-
tion: B2n= 4B2n−1−4B2n−2+ 2n.
Simplify to get 2B= 4B−4B+ 1, which implies 2B= 1 and thus B=1
2.
Therefore, a particular solution to the non-homogeneous equation is a(p)
n=
1
22n= 2n−1.
Step 3: The general solution to the non-homogeneous equation is the sum of
the general solution to the homogeneous equation and the particular solution:
an=a(h)
n+a(p)
n= (c1+c2n)2n+ 2n−1.
Step 4: Using the initial conditions a0= 1 and a1= 3, we find the values of
c1and c2.
Substitute the initial conditions into the general solution: 1 = c1and 3 =
2c1+ 2, which gives c1= 1 and c2= 1.
Therefore, the closed-form expression for anis an= 2n+n2n+ 2n−1.
Question 35
Question
Let {an}be a sequence defined by the recurrence relation an= 3an−1−2an−2
for n≥3, where a1= 1 and a2= 2. Find an explicit formula for an.
Solution
Step 1: Find the characteristic equation
The characteristic equation for the given recurrence relation an= 3an−1−2an−2
is given by:
r2= 3r−2
r2−3r+ 2 = 0
(r−1)(r−2) = 0
r= 1,2
32
Step 2: Write out the general form of the solution
Since the roots of the characteristic equation are distinct, the general solution
of the homogeneous recurrence relation is:
an=c1·1n+c2·2n
Step 3: Solve for c1and c2using initial conditions
Using the initial conditions a1= 1 and a2= 2:
a1=c1+ 2c2= 1
a2=c1+ 4c2= 2
Solving this system of equations, we find c1= 0 and c2=1
2.
Step 4: Write out the explicit formula for an
Therefore, the explicit formula for the sequence {an}is:
an=1
2·2n
So, the explicit formula for the sequence {an}is an= 2n−1.
33
