MATH 117 - ELEMENTS OF
MATHEMATICS - Homogeneous and
non-homogeneous recurrence relations
Question Bank - Set 2
Liberty University
Question 1
Question
Consider the following recurrence relation:
an+2 −4an+1 + 4an= 0, a0= 1, a1= 2.
Find the general solution to the recurrence relation.
Solution
Step 1: First, we find the characteristic equation by assuming the solution has
the form an=rn. Substituting this into the recurrence relation gives us:
r2−4r+ 4 = 0.
This equation simplifies to (r−2)2= 0, so we have a repeated root r= 2.
Step 2: Since we have a repeated root, the general solution is of the form:
an= (c1+c2n)·2n.
Step 3: Using the initial conditions a0= 1 and a1= 2, we can set up a
system of equations to solve for c1and c2:
(c1·20= 1
(c1+c2)·21= 2
Step 4: Solving the system of equations gives us c1= 1 and c2= 0. There-
fore, the general solution to the recurrence relation is:
an= 2n.
Question 2
Question
Let anbe a sequence defined by the recurrence relation an= 3an−1−2an−2
for n≥2 with initial conditions a0= 1 and a1= 2. Determine a closed-form
expression for anfor n≥0.
Solution
We first solve the characteristic equation associated with the homogeneous part
of the recurrence relation an= 3an−1−2an−2:
Step 1: Write down the characteristic equation The characteristic
equation is obtained by setting an=rn:
rn= 3rn−1−2rn−2
Dividing by rn−2:
r2= 3r−2
This gives us the characteristic equation r2−3r+ 2 = 0.
Step 2: Find the roots of the characteristic equation Factoring the
characteristic equation:
(r−1)(r−2) = 0
So, the roots are r= 1 and r= 2.
Step 3: Write down the general solution of the homogeneous part
The general solution of the homogeneous part is:
an=A·1n+B·2n
an=A+B·2n
Next, we find the particular solution to the non-homogeneous part. Given
the form of the non-homogeneous part, we guess a particular solution of the
form an=C.
Step 4: Solve for the particular solution Substitute an=Cback into
the original recurrence relation:
C= 3C−2C
Solving this, we find C= 0.
Now, we combine the solutions of the homogeneous and non-homogeneous
parts to get the general solution for an.
Step 5: Write down the general solution The general solution for an
is:
an=A+B·2n
2
Step 6: Use initial conditions to find the values of A and B Using
the initial conditions a0= 1 and a1= 2:
a0=A+B·20=A+B= 1
a1=A+B·21=A+ 2B= 2
Solving these equations simultaneously, we find A=2
3and B=1
3.
Step 7: Write down the closed-form expression for anTherefore, the
closed-form expression for anis:
an=2
3+1
3·2n
Question 3
Question
Consider the following recurrence relation:
an= 3an−1−2an−2+n, for n≥2
with initial conditions a0= 1 and a1= 3. Find the general solution for an.
Solution
To find the general solution for the given recurrence relation, we first need to
find the characteristic equation by assuming anhas the form an=rn.
Step 1: Find the characteristic equation Assume an=rn. Substitute
this into the recurrence relation to get:
rn= 3rn−1−2rn−2+n
Divide the whole equation by rn−2:
r2= 3r−2 + n
rn−2
Since rngrows faster than n, limn→∞ n
rn−2= 0, so we can neglect the last
term. This gives us the characteristic equation as:
r2−3r+ 2 = 0
The characteristic equation factors into:
(r−1)(r−2) = 0
So the roots are r1= 1 and r2= 2.
Step 2: Find the homogeneous solution The general solution of the
homogeneous equation is then:
a(h)
n=A(1)n+B(2)n
3
a(h)
n=A+ 2B
Step 3: Find a particular solution In this case, we can assume a par-
ticular solution of the form an=An +B. Substitute this into the original
recurrence relation:
An +B= 3(A(n−1) + B)−2(A(n−2) + B) + n
An +B= 3An −3A+ 3B−2An + 4A−2B+n
Equating coefficients, we have:
4A−2 = 1 =⇒A=3
2
−3A+ 3B= 0 =⇒B=3
2
Step 4: Find the general solution Therefore, the general solution for
the recurrence relation is:
an=A+ 2B+3n
2+3
2
an=3
2+3+3n
2+3
2
an= 3n+ 4
Question 4
Question
Consider the following recurrence relation involving both homogeneous and non-
homogeneous terms:
an= 3an−1−2an−2+ 2n, a0= 2, a1= 5
Find a formula for anin terms of nfor n≥2.
Solution
To solve this recurrence relation, we will first find the general solution to the
corresponding homogeneous relation an= 3an−1−2an−2, then find a particular
solution to the non-homogeneous part 2n, and combine the two to get the final
solution.
Step 1: Homogeneous Solution
The characteristic equation for the homogeneous part is r2−3r+ 2 = 0,
which factors as (r−1)(r−2) = 0. Thus, the roots are r1= 1 and r2= 2.
The general solution to the homogeneous part is an=A·1n+B·2n, where
Aand Bare constants to be determined.
4
Step 2: Particular Solution
To find a particular solution to the non-homogeneous part 2n, we assume
that an=C·2n, where Cis a constant to be determined.
Substitute an=C·2ninto the original recurrence relation:
C·2n= 3(C·2n−1)−2(C·2n−2)+2n
Simplify to get:
C=2n
2
Therefore, the particular solution is an=1
2·2n.
Step 3: Combining Solutions
The general solution to the recurrence relation is the sum of the homogeneous
and particular solutions:
an=A·1n+B·2n+1
2·2n
Applying the initial conditions a0= 2 and a1= 5:
a0=2: A+B+1
2= 2
a1=5: A+ 2B+1
2·2 = 5
Solving these two equations simultaneously gives A=5
2and B=−1
2.
Therefore, the formula for anfor n≥2 is:
an=5
2+−1
2·2n+1
2·2n
Question 5
Question
Consider the homogeneous recurrence relation defined by an= 2an−1−an−2,
with initial conditions a0= 0 and a1= 1. Determine a closed-form expression
for an.
Solution
To find a closed-form expression for an, we first need to find the characteris-
tic equation associated with the given homogeneous recurrence relation. Step
1: Write down the characteristic equation The characteristic equation for the
recurrence relation an= 2an−1−an−2is given by
r2= 2r−1
5
Step 2: Solve the characteristic equation To solve the characteristic equa-
tion r2= 2r−1, we rearrange it to the standard form r2−2r+ 1 = 0,
(r−1)2= 0
r= 1
Step 3: Form the general solution Since we have a repeated root at r= 1,
the general solution will have the form
an=c1·1n+c2·n·1n
an=c1+c2n
Step 4: Apply initial conditions Using the initial conditions a0= 0 and
a1= 1, we can solve for c1and c2. Substitute n= 0 into the general solution:
a0=c1+c2·0=0
c1= 0
Substitute n= 1 into the general solution:
a1= 0 + c2·1=1
c2= 1
Step 5: Final expression Therefore, the closed-form expression for anis
an=n
Question 6
Question
Consider the non-homogeneous linear recurrence relation:
an+2 −5an+1 + 6an= 3
with initial conditions a0= 1 and a1= 2. Find a closed-form expression for
anfor n≥0.
Solution
Step 1: First, we find the characteristic equation for the corresponding homo-
geneous recurrence relation:
r2−5r+ 6 = 0
This factors as (r−2)(r−3) = 0, so the characteristic roots are r1= 2 and
r2= 3.
6
Step 2: The solution to the homogeneous recurrence relation is:
a(h)
n=A(2)n+B(3)n
where Aand Bare constants to be determined.
Step 3: Next, we find a particular solution for the non-homogeneous equation
by guessing a solution of the form a(p)
n=C. Plugging this into the equation,
we get:
C−5C+ 6C= 3
2C= 3
C=3
2
So, a particular solution is a(p)
n=3
2.
Step 4: 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
an=A(2)n+B(3)n+3
2
Step 5: Using the initial conditions a0= 1 and a1= 2, we can solve for A
and B.
From a0= 1, we have:
A+B+3
2= 1
A+B=−1
2
From a1= 2, we have:
2A+ 3B+3
2= 2
2A+ 3B=1
2
Solving these equations simultaneously, we find A=1
2and B=−1.
Step 6: Therefore, the closed-form expression for anis:
an=1
2(2)n−(3)n+3
2
7
Question 7
Question
Find a closed-form expression for the solution of the non-homogeneous recur-
rence relation given by:
an= 3an−1−2an−2+ 2n
with initial conditions a0= 1 and a1= 2.
Solution
To solve the non-homogeneous recurrence relation, we will first find the general
solution to the corresponding homogeneous recurrence relation an= 3an−1−
2an−2, and then find a particular solution to the non-homogeneous recurrence
relation. Finally, we will combine these two solutions to find the closed-form
expression for an.
Step 1: Find the homogeneous solution Let’s assume the homogeneous
solution is of the form a(h)
n=rn. Substituting this into the homogeneous
recurrence relation, we get:
rn= 3rn−1−2rn−2
Dividing by rn−2, we get the characteristic equation r2= 3r−2. Solving
this equation, we find r= 2 and r= 1. Therefore, the general solution to the
homogeneous recurrence relation is:
a(h)
n=Arn+Brm
where Aand Bare constants to be determined.
Since we have initial conditions a0= 1 and a1= 2, we can solve for Aand B
by substituting these into the general form of the homogeneous solution. This
gives us the equations:
A+B= 1
2A+ 2B= 2
Solving these equations simultaneously, we find A= 1 and B= 0, so the
homogeneous solution is a(h)
n= 2n.
Step 2: Find a particular solution To find a particular solution to the
non-homogeneous recurrence relation an= 3an−1−2an−2+2n, we will guess that
the particular solution has a form similar to the non-homogeneous term, which
is 2n. Let’s assume a(p)
n=C·2n. Substituting this into the non-homogeneous
recurrence relation, we get:
C·2n= 3(C·2n−1)−2(C·2n−2)+2n
Simplifying this equation, we find C= 1. Therefore, the particular solution
is a(p)
n= 2n.
8
Step 3: Find the final solution The general solution to the non-homogeneous
recurrence relation is given by the sum of the homogeneous and particular so-
lutions:
an=a(h)
n+a(p)
n= 2n+ 2n= 2n+1
Thus, the closed-form expression for the solution of the non-homogeneous
recurrence relation is an= 2n+1 for n≥0.
Question 8
Question
Let anbe defined recursively by the relation an+1 = 3an−2n+1 for n≥0, with
initial condition a0= 4. Find a closed-form expression for an.
Solution
Step 1: Find the characteristic equation by assuming a solution of the form
an=rn.
an+1 = 3an−2n+1
rn+1 = 3rn−2n+1
r−3 = −2
r
r2−3r+ 2 = 0
(r−1)(r−2) = 0
Step 2: The characteristic equation has repeated roots r= 1,2, so the
general solution is given by an=c1(1n) + c2(2n).
Step 3: Use the initial condition a0= 4 to solve for c1and c2.
a0=c1(10) + c2(20)
4 = c1+c2
Step 4: Differentiate the general solution to get an expression for an+1.
an+1 =c1(1) + c2(2nln 2)
Step 5: Use an+1 = 3an−2n+1 to find c1and c2.
c1+ 2c2ln 2 = 3(c1+c2)−2n+1
c1+ 2c2ln 2 = 3c1+ 3c2−2n+1
−2c1−c2(1 −2 ln 2) = −2n+1
Step 6: Solve the system of equations to find c1and c2.
c1+c2= 4
−2c1−c2(1 −2 ln 2) = −2
Solving this system will give the values of c1and c2, resulting in the closed-form
expression for an.
9
Question 9
Question
Consider the non-homogeneous recurrence relation given by an= 3an−1−
2an−2+ 2nwith initial conditions a0= 1 and a1= 2. Find the explicit formula
for an.
Solution
Step 1: For the homogeneous part, we first solve the characteristic equation
rn= 3rn−1−2rn−2. This simplifies to r2−3r+ 2 = 0, which factors as
(r−1)(r−2) = 0. So, the characteristic roots are r1= 1 and r2= 2.
Step 2: The general solution for the homogeneous part is given by a(h)
n=
c1(1)n+c2(2)n, where c1and c2are constants to be determined.
Step 3: Next, we consider the particular solution. Since the non-homogeneous
part is 2n, a good guess is a(p)
n=A·2n. Substitute a(p)
ninto the original recur-
rence relation to find A:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n.
Step 4: Simplify the above equation to get A= 1. Therefore, the particular
solution is a(p)
n= 2n.
Step 5: The general solution for the non-homogeneous part is then given by
an=a(h)
n+a(p)
n=c1(1)n+c2(2)n+ 2n.
Step 6: Apply the initial conditions a0= 1 and a1= 2 to solve for c1and
c2. Substitute n= 0 into the general solution: c1+c2+ 1 = 1. Substitute n= 1
into the general solution: c1+ 2c2+ 2 = 2.
Step 7: Solving the above system of equations, we find c1= 0 and c2= 1.
Therefore, the explicit formula for anis: an= 2n.
Question 10
Question
Consider the following non-homogeneous recurrence relation:
an= 3an−1−2an−2+ 2n
where a0= 1 and a1= 2. Find the formula for anin terms of n.
10
Solution
To solve the non-homogeneous recurrence relation, we first find the general
solution to the corresponding homogeneous relation.
an−3an−1+ 2an−2= 0 (homogeneous part)
r2−3r+ 2 = 0
(r−1)(r−2) = 0
r= 1,2.
So the general solution is an=c1·1n+c2·2n, where c1and c2are constants to
be determined.
Next, we find a particular solution to the non-homogeneous part. Since 2n
is of the form c·dnwhere d= 2 and c= 1, a particular solution is of the form
A·2n.
Substitute an=A·2ninto the original relation:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
Let’s simplify this equation:
A·2n= 3A·2n−1−2A·2n−2+ 2n
A·2n= 3A·2n−6A·2n+ 2n
A=1
2.
Therefore, a particular solution is an=1
2·2n= 2n−1.
Combining the general solution and the particular solution, we find the for-
mula for an:
an=c1·1n+c2·2n+ 2n−1
Using the initial conditions a0= 1 and a1= 2, we can find the values of c1
and c2:(c1+c2+ 1 = 1
c1·1 + c2·2 + 1
2= 2
Solving these equations gives c1=−1
2and c2= 1. Therefore, the formula
for anis:
an=−1
2+ 2n+ 2n−1.
Question 11
Question
Given the non-homogeneous recurrence relation:
an= 2an−1+ 3 ·2n
with initial condition a0= 1, find the explicit formula for an.
11
Solution
Step 1: Begin by finding the general solution to the associated homogeneous
recurrence relation an= 2an−1. The characteristic equation is r−2 = 0, which
has a root r= 2. So, the general solution to the homogeneous recurrence
relation is a(h)
n=c·2nfor some constant c.
Step 2: Next, find a particular solution to the non-homogeneous recurrence
relation. Since the non-homogeneous term is of the form 3 ·2n, let’s try a
particular solution of the form a(p)
n=An ·2nand substitute it into the original
recurrence relation.
An ·2n= 2(An −1·2n−1)+3·2n
An ·2n= 2An ·2n−2A·2n−1+ 3 ·2n
Step 3: Solve for Aby comparing coefficients of like terms.
An = 2An + 3 ⇒A=−3
Step 4: Now, the particular solution is a(p)
n=−3n·2n.
Step 5: The general solution to the non-homogeneous recurrence relation is
the sum of the general solution to the homogeneous recurrence relation and the
particular solution:
an=a(h)
n+a(p)
n=c·2n−3n·2n
Step 6: Finally, use the initial condition a0= 1 to solve for c:
a0=c−0=1⇒c= 1
Therefore, the explicit formula for anis:
an= 2n−3n·2n
Question 12
Question
Consider the following recurrence relation: an= 3an−1−3an−2+ 2n. Given
that a0= 1 and a1= 2, find an explicit formula for an.
Solution
Step 1: Find the homogeneous solution to the recurrence relation.
The characteristic equation is r2= 3r−3, which simplifies to r2−3r+ 3 = 0.
Solving this quadratic equation, we find that the roots are r1=3+i√3
2and
r2=3−i√3
2. Therefore, the homogeneous solution is of the form
a(h)
n=c1 3 + i√3
2!n
+c2 3−i√3
2!n
.
12
Step 2: Find the particular solution to the non-homogeneous part of the
recurrence relation.
We look for a particular solution of the form a(p)
n=An2n. Substituting this
into the original recurrence relation, we get
An2n= 3An2n−1−3An2n−2+ 2n.
By comparing coefficients, we find that A=−1
2. Thus, the particular solution
is a(p)
n=−1
2n2n.
Step 3: Find the full solution to the recurrence relation.
Therefore, the general solution is
an=a(h)
n+a(p)
n=c1 3 + i√3
2!n
+c2 3−i√3
2!n
−1
2n2n.
Step 4: Use the initial conditions to solve for the constants.
Given that a0= 1 and a1= 2, we can substitute these values into the general
solution: (c1+c2= 1
3+i√3
2c1+3−i√3
2c2−2 = −1
Solving these equations, we find c1=1
3and c2=2
3.
Step 5: Write down the explicit formula for an.
Substitute the values of c1and c2back into the general solution to get
an=1
3 3 + i√3
2!n
+2
3 3−i√3
2!n
−1
2n2n.
Question 13
Question
Let (an) be 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
To find a closed-form expression for the sequence (an), we first need to find
the characteristic equation of the given homogeneous linear recurrence relation.
The characteristic equation is given by r2−2r−3 = 0.
Step 1: Find the roots of the characteristic equation Solving r2−
2r−3 = 0 gives us r= 3 and r=−1.
Therefore, the general solution to the homogeneous recurrence relation is
an=c1·3n+c2·(−1)nfor constants c1and c2.
13
Step 2: Find particular solution for the non-homogeneous part
Since the non-homogeneous part 3an−2has the form of Krnwith K= 3 and
r= 3, we look for a particular solution of the form an=B·3n. Substituting
this into the recurrence relation, we get:
B·3n= 2(B·3n−1) + 3(B·3n−2)
B= 2B+ 1
B= 1
So, a particular solution is an= 3n.
Step 3: Write down the general solution Putting the general solution
to the homogeneous part and the particular solution together, we have:
an=c1·3n+c2·(−1)n+ 3n
Step 4: Use initial conditions to evaluate constants Using the initial
conditions: a0= 1 and a1= 2, we get the equations: c1+c2+ 1 = 1 and
3c1−c2+ 3 = 2
Solving these equations gives c1=1
2and c2=−1
2.
Therefore, the closed-form expression for the sequence (an) is given by:
an=1
2·3n−1
2·(−1)n+ 3n
Question 14
Question
Let anbe the sequence defined recursively by the recurrence relation an=
3an−1−2an−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 of the homogeneous recurrence relation
an= 3an−1−2an−2.
The characteristic equation is given by r2−3r+ 2 = 0. Factoring this
equation, we get (r−1)(r−2) = 0. Therefore, the characteristic roots are
r1= 1 and r2= 2.
Step 2: Write the general solution of the homogeneous recurrence relation.
The general solution is given by an=A·1n+B·2n, where Aand Bare
constants to be determined.
Step 3: Use the initial conditions to solve for the constants Aand B.
Substitute n= 0 into the general solution and the initial condition a0= 1,
we get: 1 = A·10+B·20=A+B
Substitute n= 1 into the general solution and the initial condition a1= 2,
we get: 2 = A·11+B·21=A+ 2B
14
Solving the system of equations A+B= 1 and A+ 2B= 2, we find A= 2
and B=−1.
Step 4: Write the final formula for an.
Therefore, the formula for anis an= 2 ·1n−1·2n= 2 −2nfor n≥0.
Question 15
Question
Consider the following recurrence relation:
an= 3an−1−2an−2+ 2n
with initial conditions a0= 1 and a1= 3. Find a closed-form expression for an.
Solution
Step 1: Find the homogeneous solution to the recurrence relation by setting
an=rn:
rn= 3rn−1−2rn−2
Dividing by rn−2gives the characteristic equation:
r2= 3r−2
r2−3r+ 2 = 0
(r−1)(r−2) = 0
Which gives the roots r= 1 and r= 2. Therefore, the homogeneous solution is:
a(h)
n=A(1)n+B(2)n
a(h)
n=A+ 2B
Step 2: Find a particular solution due to the non-homogeneous term 2n.
Since 2nis a geometric progression, we guess a particular solution of the form
a(p)
n=C·2n. Substitute this back into the original recurrence relation:
C·2n= 3(C·2n−1)−2(C·2n−2)+2n
C·2n= 3C·2n−1−2C·2n−2+ 2n
C=1
2
Therefore, the particular solution is a(p)
n=1
2·2n= 2n−1.
Step 3: Combine the homogeneous and particular solutions to find the gen-
eral solution:
an=a(h)
n+a(p)
n
15
an=A+ 2B+ 2n−1
Step 4: Apply the initial conditions a0= 1 and a1= 3: From a0= 1:
A+ 2B+1
2= 1
A+ 2B=1
2
From a1= 3:
A+ 2B+ 2 = 3
A+ 2B= 1
Subtracting these equations gives:
1
2−1 = 1
2
This implies that the initial conditions are inconsistent, and the closed-form
expression cannot be uniquely determined.
Question 16
Question
Consider the non-homogeneous recurrence relation defined by an= 3an−1−
2an−2+ 2nfor all integers n≥2 with initial conditions a0= 1 and a1=−1.
Determine the closed form expression for anin terms of n.
Solution
Step 1: Find the characteristic equation associated with the homogeneous part
of the recurrence relation.
The characteristic equation is given by r2= 3r−2, which simplifies to
r2−3r+ 2 = 0. Factoring the quadratic gives (r−1)(r−2) = 0, so the roots
are r1= 1 and r2= 2.
Therefore, the homogeneous solution is of the form a(h)
n=C1·1n+C2·2n=
C1+C2·2n.
Step 2: Find a particular solution for the non-homogeneous part of the
recurrence relation.
Guessing a form for the particular solution based on the non-homogeneous
term gives a(p)
n=An ·2n, where Ais a constant to be determined.
Substitute the guess into the original recurrence relation:
An ·2n= 3(An −1·2n−1)−2(An −2·2n−2)+2n
Step 3: Solve for the constant Aby comparing coefficients of powers of 2.
16
First, divide both sides by 2nto simplify the equation:
An = 3(A(n−1) −2(A(n−2)) + 1
Expanding and simplifying gives:
An = 3An −3A−2An + 4A+ 1
An =An +A+ 1
A= 1
Therefore, the particular solution is a(p)
n=n·2n.
Step 4: Combine the homogeneous and particular solutions to find the gen-
eral solution.
The general solution is given by an=a(h)
n+a(p)
n:
an=C1+C2·2n+n·2n
Step 5: Apply the initial conditions to find the values of C1and C2.
Using the initial conditions a0= 1 and a1=−1:
1 = C1+C2
−1 = C1+ 2C2
Solving this system of equations gives C1= 2 and C2=−1.
Therefore, the closed form expression for anis:
an= 2 −2n+n·2n
Question 17
Question
Let anbe a sequence defined recursively by the following recurrence relation:
an= 2an−1−2an−2+n, n ≥2
with initial conditions a0= 1 and a1= 3. Find a closed-form expression for an.
Solution
Step 1: First, we solve the homogeneous part an= 2an−1−2an−2. Assume
an=rn, then the characteristic equation is rn= 2rn−1−2rn−2. Dividing
by rn−2, we get r2= 2r−2, which simplifies to r2−2r+ 2 = 0. The roots
of this quadratic equation are r= 1 ±i, giving us the homogeneous solution:
a(h)
n=c1(1 + i)n+c2(1 −i)n.
17
Step 2: Next, we find a particular solution for the non-homogeneous part
an=n. Since this is a linear function, assume a(p)
n=An +B. Plugging this
into the original recurrence relation, we get:
An +B= 2(A(n−1) + B)−2(A(n−2) + B) + n
Solving for Aand B, we get A=1
2and B=−1
4. Therefore, the particular
solution is a(p)
n=1
2n−1
4.
Step 3: The general solution is the sum of the homogeneous and particular
solutions:
an=a(h)
n+a(p)
n=c1(1 + i)n+c2(1 −i)n+1
2n−1
4
Step 4: Using the initial conditions a0= 1 and a1= 3 to find c1and c2:
a0=c1(1 + i)0+c2(1 −i)0+1
2·0−1
4=c1+c2−1
4= 1
a1=c1(1 + i)1+c2(1 −i)1+1
2·1−1
4=c1(1 + i) + c2(1 −i) + 1
4= 3
Step 5: Solving the system of equations, we find c1=3
2and c2=1
2. There-
fore, the closed-form expression for anis:
an=3
2(1 + i)n+1
2(1 −i)n+1
2n−1
4
Question 18
Question
Let ansatisfy the recurrence relation an+2 −5an+1 + 6an= 2nfor 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 by assuming an=rn:
r2−5r+ 6 = 0
Solving the quadratic equation gives us r= 2 and r= 3, so the general solution
to the homogeneous part of the recurrence relation is
an=A·2n+B·3n
Step 2: To find a particular solution to the non-homogeneous part of the
recurrence relation, assume an=C·2n. Plugging this into the recurrence
relation gives us 4C−5(2C)+6C= 2n, which simplifies to −3C= 2n. Therefore,
C=−1
3.
18
Step 3: The general solution to the non-homogeneous part is then an=
A·2n+B·3n−1
3·2n. Applying the initial conditions a0= 1 and a1= 2 gives
the system of equations:
A+B−1
3= 1
2A+ 3B−2
3= 2
Step 4: Solving the system of equations gives A=5
3and B=−2
3. Therefore,
the closed-form expression for anis
an=5
3·2n−2
3·3n−1
3·2n
Question 19
Question
Let anbe the sequence defined recursively by a0= 2, a1= 3, and an+1 =
3an−2an−1for n≥1. Determine a formula for an.
Solution
Step 1: First, let’s find the first few values of the sequence to look for a pattern:
a0= 2
a1= 3
a2= 3a1−2a0= 3(3) −2(2) = 7
a3= 3a2−2a1= 3(7) −2(3) = 15
a4= 3a3−2a2= 3(15) −2(7) = 29
Step 2: Now, we can see a pattern emerging. It seems that an= 2n+ 1 for
all n≥0. We will prove this by mathematical induction.
Step 3: Basis step: Verify the formula for the base cases. For n= 0,
a0= 20+ 1 = 1 + 1 = 2, which is correct. For n= 1, a1= 21+ 1 = 2 + 1 = 3,
which is correct.
Step 4: Inductive step: Assume that ak= 2k+ 1 for some arbitrary k≥1.
Now, we will prove that ak+1 = 2k+1 + 1.
ak+1 = 3ak−2ak−1
= 3(2k+ 1) −2(2k−1+ 1)
= 3 ·2k+ 3 −2·2k−1−2
= 3 ·2k+ 1 −2k−2
= 2(2k)+1
= 2k+1 + 1
19
Thus, the formula an= 2n+ 1 holds for all n≥0 by mathematical induction.
Question 20
Question
Consider the non-homogeneous recurrence relation defined by an= 4an−1−
4an−2+ 2nwith initial conditions a0= 2 and a1= 7. Find a closed-form
expression for an.
Solution
To solve the non-homogeneous recurrence relation, we first need to find the
general solution to the corresponding homogeneous recurrence relation an=
4an−1−4an−2.
Step 1: Find the characteristic equation Let an=rn. Then, substi-
tuting an=rninto the homogeneous recurrence relation, we get:
rn= 4rn−1−4rn−2
Dividing by rn−2, we obtain:
r2= 4r−4
This simplifies to the characteristic equation:
r2−4r+ 4 = 0
(r−2)2= 0
r= 2
So, the characteristic roots are r1=r2= 2.
Step 2: Find the general solution to the homogeneous recurrence
relation The general solution to the homogeneous recurrence relation is given
by:
a(h)
n=A·2n+B·n·2n
where Aand Bare constants to be determined.
Step 3: Find a particular solution to the non-homogeneous recur-
rence relation The non-homogeneous term 2nis a geometric sequence, so we
try a particular solution of the form a(p)
n=C·2n.
Substitute a(p)
n=C·2ninto the non-homogeneous recurrence relation:
C·2n= 4(C·2n−1)−4(C·2n−2)+2n
C= 2
Thus, a particular solution is a(p)
n= 2 ·2n= 2n+1.
Step 4: Find the general solution to the non-homogeneous re-
currence relation The general solution to the non-homogeneous recurrence
20
relation is the sum of the general solution to the homogeneous relation and the
particular solution to the non-homogeneous relation:
an=a(h)
n+a(p)
n=A·2n+B·n·2n+ 2n+1
Step 5: Apply initial conditions Using the initial conditions a0= 2 and
a1= 7, we can find the values of Aand B:
a0=A·20+B·0·20+ 21= 2
A+ 2 = 2 =⇒A= 0
a1=A·21+B·1·21+ 22= 7
2B+ 4 = 7 =⇒B=3
2
Step 6: Final solution Therefore, the closed-form expression for anis:
an=3
2·n·2n+ 2n+1
Question 21
Question
Let anbe the sequence defined by the recurrence relation an+2 = 3an+1 −2an
where a0= 1 and a1= 2. Find a closed-form expression for an.
Solution
Step 1: Write the characteristic equation associated with the given recurrence
relation. The characteristic equation is obtained by setting an=rnin the
relation an+2 = 3an+1 −2an.
Step 2: Substitute an=rninto the recurrence relation to get the character-
istic equation.
r2= 3r−2
Step 3: Rearrange the characteristic equation to get it in the form r2−3r+
2 = 0.
Step 4: Solve the characteristic equation to find the roots r1and r2.
(r−1)(r−2) = 0
r1= 1, r2= 2
Step 5: The solution to the homogeneous recurrence relation is then
an=c1(1)n+c2(2)n
21
an=c1+ 2c2
Step 6: Use the initial conditions a0= 1 and a1= 2 to solve for c1and c2.
a0=c1+ 2c2= 1
a1=c1+ 2c2= 2
Step 7: Solve the system of equations to find c1and c2. Substitute c1=
1−2c2into a1= 2.
1−2c2+ 2c2= 2
−c2= 1
c2=−1
Step 8: Substitute c2=−1 back into c1= 1 −2c2.
c1= 1 −2(−1) = 3
Step 9: Therefore, the closed-form expression for the sequence anis
an= 3 −2n
Question 22
Question
Consider the recurrence relation defined by an+2 = 5an+1 −6an+2nwith initial
conditions a0= 0 and a1= 1. Find a closed-form expression for an.
Solution
Step 1: Finding the characteristic equation To find a closed-form expression for
an, we first need to find the characteristic equation by assuming a solution of
the form an=rn. Substitute an=rninto the recurrence relation:
rn+2 = 5rn+1 −6rn+ 2n
Divide by rn:
r2= 5r−6 + 2
rn
The characteristic equation is then:
r2−5r+ 6 = 0
Factor the characteristic equation:
(r−2)(r−3) = 0
22
So, the characteristic roots are r1= 2 and r2= 3.
Step 2: Finding the homogeneous solution The homogeneous solution is
given by ahom
n=A(2n)+B(3n), where Aand Bare constants to be determined.
Step 3: Finding the particular solution Now, we need to find a particular
solution for the non-homogeneous term 2n. We assume that the particular
solution is of the form apar
n=C(2n).
Substitute apar
n=C(2n) into the recurrence relation:
C(2n+2) = 5C(2n+1)−6C(2n)+2n
4C(2n) = 5C(2n)−6C(2n)+2n
4C=−C+1
2n
5C=1
2n
C=1
5·2n
Step 4: Writing the general form of the solution The general solution of the
recurrence relation is:
an=ahom
n+apar
n=A(2n) + B(3n) + 1
5·2n
Step 5: Using initial conditions to find constants Using the initial conditions
a0= 0 and a1= 1 to solve for Aand B:
a0=A+B+1
5= 0
a1= 2A+ 3B+1
10 = 1
Solving these equations gives A=−2
5and B=9
10 .
Step 6: Final closed-form expression Therefore, the closed-form expression
for anis:
an=−2
5(2n) + 9
10(3n) + 1
5·2n
Question 23
Question
Consider the non-homogeneous recurrence relation defined by an= 2an−1+n3,
where a0= 3. Find an explicit formula for an, where n≥1.
23
Solution
Step 1: Find the homogeneous solution by setting an= 2an−1.
an−2an−1= 0
an= 2an−1
Step 2: Write the characteristic equation for the homogeneous relation.
r−2=0
r= 2
Step 3: Write down the solution to the homogeneous relation.
an=C·2n
Step 4: Find the particular solution for the non-homogeneous part. Assume
anis of the form an3+bn2+cn +d.
an= 2an−1+n3
an3+bn2+cn +d= 2(a(n−1)3+b(n−1)2+c(n−1) + d) + n3
Step 5: Expand the terms and match coefficients to solve for a,b,c, and d.
an3+bn2+cn +d= 2(an3−3an2+ 3an −a+bn2−2bn +b+cn −c+d) + n3
an3+bn2+cn +d= 2an3−6an2+ 6an −2a+ 2bn2−4bn + 2b+ 2cn −2c+ 2d+n3
an3+bn2+cn +d= 2an3+ 2bn2+ 2cn + (6a−6b+ 2)n−2a−4b−2c+ 2d
Step 6: Equate coefficients to solve for a,b,c, and d.
a= 2, b =−2, c = 3, d =−1
Step 7: Write down the particular solution for the non-homogeneous part.
an= 2n3−2n2+ 3n−1
Step 8: Combine the homogeneous and non-homogeneous solutions to get
the explicit formula for an.
an=C·2n+ 2n3−2n2+ 3n−1
Step 9: Use the initial condition a0= 3 to solve for C.
3 = C·20+ 2(0)3−2(0)2+ 3(0) −1
C= 4
Step 10: Write down the final explicit formula for an.
an= 4 ·2n+ 2n3−2n2+ 3n−1
24
Question 24
Question
Determine a closed-form expression for the sequence defined by the recurrence
relation an= 3an−1−an−2+ 2nwith initial conditions a0= 1 and a1= 3.
Solution
Step 1: Finding the homogeneous solution
We first solve the homogeneous recurrence relation an= 3an−1−an−2.
Assume the solution has the form an=rn. Substitute this form into the
relation to get rn= 3rn−1−rn−2. This simplifies to r2= 3r−1, which gives
the characteristic equation r2−3r+ 1 = 0. Solve this quadratic equation to
find r1and r2.
Step 2: Finding the particular solution
Next, we look for a particular solution to the non-homogeneous part 2n.
Since 2nis an exponential function, we try a similar form, an=A·2n. Substitute
an=A·2ninto the original recurrence relation to get A·2n= 3A·2n−1−A·
2n−2+ 2n. Simplify this to find the value of A.
Step 3: Combining solutions
The general solution is the sum of the homogeneous and particular solutions:
an=C1rn
1+C2rn
2+A·2n. Use the initial conditions a0= 1 and a1= 3 to find
C1,C2, and A.
Step 4: Final closed-form expression
Substitute the values of C1,C2, and Aback into the general solution to
obtain the closed-form expression for an.
Question 25
Question
Consider the homogeneous recurrence relation: an+2 −5an+1 + 6an= 0 where
a0= 2 and a1= 3. Determine the closed-form expression for anusing the
characteristic equation method.
Solution
To find the closed-form expression for an, we need to solve the characteristic
equation associated with the homogeneous recurrence relation.
Step 1: Write the characteristic equation The characteristic equation
for the given homogeneous recurrence relation is:
r2−5r+ 6 = 0
25
Step 2: Solve the characteristic equation To solve the characteristic
equation, we can factorize it as:
r2−5r+ 6 = (r−2)(r−3) = 0
This gives us the roots:
r1= 2 and r2= 3
Step 3: Write the general solution The general solution for the recur-
rence relation is:
an=A·2n+B·3n
Step 4: Find the values of A and B using initial conditions Given
that a0= 2 and a1= 3, we can substitute these values into the general solution:
a0=A·20+B·30=A+B= 2
a1=A·21+B·31= 2A+ 3B= 3
Solving these equations simultaneously, we find that A= 1 and B= 1.
Step 5: Final closed-form expression Therefore, the closed-form ex-
pression for the given recurrence relation is:
an= 1 ·2n+ 1 ·3n= 2n+ 3n
Question 26
Question
Let anbe the sequence defined by the recurrence relation an= 2an−1−2an−2+n
for n≥2, with initial conditions a0= 1 and a1= 2. Find a closed-form
expression for an.
Solution
Step 1: Find the homogeneous solution to the recurrence relation. Assume an
has the form an=rn.
rn= 2rn−1−2rn−2
r2= 2r−2
r2−2r+ 2 = 0
Step 2: Solve the characteristic equation r2−2r+ 2 = 0 using the quadratic
26
formula.
r=2±p(−2)2−4·1·2
2·1
r=2±√4−8
2
r=2±√−4
2
r=2±2i
2
r= 1 ±i
Step 3: The general solution to the homogeneous recurrence relation is an=
c1(1 + i)n+c2(1 −i)n, where c1and c2are constants to be determined.
Step 4: Apply initial conditions a0= 1 and a1= 2 to find the particular
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
Step 5: Solve the equations c1+c2= 1 and c1(1 + i) + c2(1 −i)=2
simultaneously to find c1and c2.
c1+c2= 1
c1(1 + i) + c2(1 −i)=2
Solving these equations, we get c1=1
2and c2=1
2.
Step 6: Substitute the values of c1and c2back into the general solution to
get the closed-form expression for an.
an=1
2(1 + i)n+1
2(1 −i)n
Question 27
Question
Let anbe defined recursively by a0= 1, a1= 2, and an+2 = 2an+1 −2anfor
n≥0. Find a closed-form expression for an.
Solution
Step 1: First, let’s find the characteristic equation of the homogeneous recur-
rence relation an+2 = 2an+1 −2an. Let an=rn. Substitute an=rninto
the homogeneous recurrence relation: rn+2 = 2rn+1 −2rnThis simplifies to:
r2= 2r−2r2−2r+ 2 = 0
27
Step 2: Next, solve the characteristic equation r2−2r+ 2 = 0 to find the
roots. Using the quadratic formula: r=−(−2)±√(−2)2−4(1)(2)
2(1) r=2±√4−8
2
r=2±√−4
2r=2±2i
2r= 1 ±i
Step 3: Since the roots are complex (1 ±i), the general solution takes
the form: an=c1(1 + i)n+c2(1 −i)nan=c1cos n·π
2+isin n·π
2+
c2cos n·π
2−isin n·π
2an=c12ncos n·π
2+c22nsin n·π
2
Step 4: To find the values of c1and c2, we use the initial conditions a0= 1
and a1= 2. From a0= 1: 1 = c120cos 0·π
2+c220sin 0·π
21 = c1From
a1= 2: 2 = c121cos π
2+c221sin π
22=2c2c2= 1
Step 5: Therefore, the closed-form expression for anis: an= cos nπ
2+
2nsin nπ
2
Question 28
Question
Consider the following non-homogeneous recurrence relation:
an= 2an−1−an−2+ 2n
where a0= 1 and a1= 3. Find a general formula for anin terms of n.
Solution
Step 1: First, we will find the general solution to the associated homogeneous
recurrence relation.
The associated homogeneous recurrence relation is given by:
an= 2an−1−an−2
Let’s assume a solution of the form an=rn. Substituting this into the
homogeneous recurrence relation, we get:
rn= 2rn−1−rn−2
Dividing by rn−2(assuming r= 0), we get:
r2= 2r−1
This gives us the characteristic equation r2−2r+ 1 = (r−1)2= 0. Thus,
we have a repeated root r= 1.
Therefore, the general solution to the homogeneous recurrence relation is
given by an=c1·1n+c2·n·1n=c1+c2n.
Step 2: Now, we will find a particular solution to the non-homogeneous
recurrence relation.
28
Since the non-homogeneous term is 2n, let’s assume a particular solution of
the form ap
n=k·2n. Substituting this into the non-homogeneous recurrence
relation, we get:
k·2n= 2(k·2n−1)−(k·2n−2)+2n
Simplifying, we find that k=−1.
Therefore, a particular solution to the non-homogeneous recurrence relation
is ap
n=−2n.
Step 3: Combining the general solution to the homogeneous recurrence re-
lation and the particular solution to the non-homogeneous recurrence relation,
we get the general formula for an:
an=ah
n+ap
n=c1+c2n−2n
Step 4: Using the initial conditions a0= 1 and a1= 3, we can solve for c1
and c2.
From a0= 1, we have c1+c2·0−20= 1, which gives c1−1 = 0 or c1= 1.
From a1= 3, we have c1+c2·1−21= 3, substituting c1= 1, we have
1 + c2−2 = 3 or c2= 4.
Therefore, the general formula for anin terms of nis:
an= 1 + 4n−2n
Question 29
Question
Consider the following recurrence relation:
an+2 = 3an+1 −2an+ 2n
Find the general solution to this non-homogeneous recurrence relation.
Solution
To solve this non-homogeneous recurrence relation, we will first find the general
solution to the corresponding homogeneous relation, and then we will find a
particular solution to the non-homogeneous relation. The general solution to the
non-homogeneous relation will be the sum of the solutions to the homogeneous
and particular solutions.
Step 1: Find the general solution to the homogeneous part
The homogeneous part of the recurrence relation is given by
an+2 = 3an+1 −2an
Let’s assume a solution of the form an=rn. Substituting this into the
homogeneous part gives
29
rn+2 = 3rn+1 −2rn
Dividing by rn, we obtain the characteristic equation
r2= 3r−2
r2−3r+ 2 = 0
Solving the quadratic equation gives us r= 1 and r= 2. Therefore, the
general solution to the homogeneous part is
an=A·1n+B·2n=A+B·2n
where Aand Bare constants to be determined.
Step 2: Find a particular solution to the non-homogeneous part
To find a particular solution, we guess that anhas the form P·2n, where P is
a constant. Substituting this into the non-homogeneous part of the recurrence
relation gives
P·2n+2 = 3P·2n+1 −2P·2n+ 2n
This simplifies to
4P= 6P−2P+ 1
4P= 4P+ 1
This has no solution, so we try a different guess. Let’s try an=Q·2n+R.
Substituting this into the non-homogeneous recurrence relation gives
Q·2n+2 +R= 3(Q·2n+1 +R)−2(Q·2n+R)+2n
This simplifies to
4Q·2n+R= 6Q·2n+ 3R−2Q·2n−2R+ 2n
2Q·2n+ 2R= 2n
Comparing coefficients, we get 2Q= 1 and 2R= 0, so Q=1
2and R= 0.
Therefore, a particular solution is an=1
2·2n.
Step 3: General solution
The general solution to the non-homogeneous recurrence relation is the sum
of the homogeneous and particular solutions:
an=A+B·2n+1
2·2n=A+B+1
2·2n
where A and B are constants determined by the initial conditions.
30
Question 30
Question
Consider the non-homogeneous recurrence relation an= 2an−1−an−2+ 3 ·2n
with initial conditions a0= 0 and a1= 1. Find a closed-form expression for an.
Solution
Step 1: Find the homogeneous solution to the recurrence relation. We first
consider the associated homogeneous recurrence relation a(h)
n= 2a(h)
n−1−a(h)
n−2.
The characteristic equation is r2= 2r−1, which simplifies to r2−2r+ 1 = 0.
This gives us a repeated root r= 1, so the homogeneous solution is a(h)
n=
c1·1n+c2·n·1n=c1+c2n.
Step 2: Find a particular solution to the non-homogeneous recurrence rela-
tion. We look for a particular solution of the form a(p)
n=A·2n. Substituting
this into the original recurrence relation, we get:
A·2n= 2(A·2n−1)−(A·2n−2)+3·2n
A·2n= 2A·2n−1−A·2n−2+ 3 ·2n
A= 2A−A
2+ 3
A=4
3
Thus, the particular solution is a(p)
n=4
3·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=c1+c2n+4
3·2n
Step 4: Use initial conditions to find the values of c1and c2. Using a0= 0
and a1= 1, we have:
c1+4
3= 0
c1+c2+8
3= 1
Solving these equations, we find c1=−4
3and c2= 5.
Step 5: Write the closed-form expression for an. Therefore, the closed-form
expression for anis:
an=−4
3+ 5n+4
3·2n
31
Question 31
Question
Let anbe defined by the recurrence relation an= 3an−1−2an−2for n≥2 with
initial conditions a0= 1 and a1= 2. Find a closed-form expression for an.
Solution
Step 1: Find the characteristic equation by assuming an=rn.
rn= 3rn−1−2rn−2
r2= 3r−2
r2−3r+ 2 = 0
(r−1)(r−2) = 0
So the roots of the characteristic equation are r1= 1 and r2= 2.
Step 2: Write the general solution based on the roots r1and r2.
an=c1·1n+c2·2n
an=c1+c2·2n
Step 3: Use the initial conditions to solve for c1and c2.
a0=c1+c2= 1
a1=c1+ 2c2= 2
Solving for c1and c2, we get c1= 2 and c2=−1.
Step 4: Substitute the values of c1and c2into the general solution to find
the closed-form expression.
an= 2 −2n
Therefore, the closed-form expression for anis an= 2 −2n.
Question 32
Question
Consider the non-homogeneous recurrence relation given by an= 3an−1−
2an−2+ 2n. If the initial conditions are a0= 2 and a1= 5, find a closed-
form expression for an.
32
Solution
Step 1: First, we solve the corresponding homogeneous recurrence relation
a(h)
n= 3a(h)
n−1−2a(h)
n−2. The characteristic equation is r2= 3r−2, which sim-
plifies to r2−3r+ 2 = 0. Factoring, we get (r−1)(r−2) = 0, so the roots are
r= 1 and r= 2. Therefore, the general solution to the homogeneous equation
is a(h)
n=A(1)n+B(2)n, where Aand Bare constants to be determined.
Step 2: Next, we find a particular solution to the non-homogeneous equation.
Since the non-homogeneous term is 2n, we try a particular solution of the form
a(p)
n=C·2n, where Cis a constant to be determined. Substituting this into
the original equation gives:
C·2n= 3(C·2n−1)−2(C·2n−2)+2n
C·2n= 3C·2n−1−2C·2n−2+ 2n
C=1
2
Step 3: Combining the general solution to the homogeneous equation and the
particular solution gives the general solution to the non-homogeneous equation:
an=a(h)
n+a(p)
n=A(1)n+B(2)n+1
2·2n
Step 4: Using the initial conditions a0= 2 and a1= 5, we get the following
two equations:
A+B+1
2= 2
A(1) + B(2) + 1
2·2=5
Solving these equations, we find A= 1 and B=3
2.
Step 5: Therefore, the closed-form expression for anis:
an= 1 + 3
2·2n+1
2·2n
Question 33
Question
Consider the non-homogeneous recurrence relation:
an= 2an−1−an−2+ 2n
where the initial conditions are a0= 1 and a1= 3. Find the explicit formula
for an.
33
Solution
Step 1: Find the complementary solution to the homogeneous equation an=
2an−1−an−2. We first solve the characteristic equation r2= 2r−1 by setting
r2−2r+ 1 = 0:
(r−1)2= 0
This gives us a repeated root of r= 1, so the complementary solution is:
a(c)
n= (An +B)·1n=An +B
Step 2: Find a particular solution to the non-homogeneous equation an=
2an−1−an−2+ 2n. Since the non-homogeneous term is 2n, a good guess for a
particular solution is c·2n. Plugging this into the equation, we get:
c·2n= 2(c·2n−1)−(c·2n−2)+2n
c·2n= 2c·2n−1−c·2n−2+ 2n
c= 2c−c
2+ 1
Solving for c, we find c=−2
3.
Therefore, the particular solution is a(p)
n=−2
3·2n.
Step 3: The general form of the solution is the sum of the complementary
and particular solutions:
an=a(c)
n+a(p)
n=An +B−2
3·2n
Step 4: Apply initial conditions a0= 1 and a1= 3. Substitute n= 0 into
the equation:
a0=A·0 + B−2
3·1=1
B−2
3= 1
B=5
3
Substitute n= 1 into the equation:
a1=A·1 + 5
3−2
3·2=3
A+5
3−4
3= 3
A= 2
Therefore, the explicit formula for anis:
an= 2n+5
3−2
3·2n
34
Question 34
Question
Consider the following non-homogeneous recurrence relation:
an+1 = 2an+ 3 ·2n,where a0= 4.
Find a closed-form expression for an.
Solution
Step 1: First, we’ll find the closed-form expression of the corresponding homo-
geneous recurrence relation, which is an+1 = 2an. The characteristic equation
is r−2 = 0, which gives us r= 2. Therefore, the homogeneous solution is
a(h)
n=A·2n, where Ais a constant to be determined.
Step 2: Next, we find a particular solution a(p)
nof the non-homogeneous
recurrence relation an+1 = 2an+3·2n. Since the right-hand side is a polynomial
of degree 1 (a constant times 2n), we guess that a(p)
nis also a constant times 2n,
say b·2n. Substituting this into the recurrence relation, we have:
b·2n+1 = 2(b·2n)+3·2n
Step 3: Simplifying the above equation gives b·2 = 2b+ 3, which implies
2b= 2b+ 3 and then 3 = 0. This is a contradiction, so our guess was incorrect.
Let’s try with a linear function instead: a(p)
n=cn +d. Substituting this into
the recurrence relation gives:
c(n+ 1) + d= 2(cn +d)+3·2n
Step 4: By simplifying the above equation and equating coefficients, we find
that c= 3 and d=−3. Therefore, a(p)
n= 3n−3.
Step 5: Finally, 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=A·2n+ 3n−3.
Step 6: To find the value of the constant A, we use the initial condition
a0= 4. Substituting n= 0 into the general solution gives:
4 = A·20+ 3 ·0−3
4 = A−3
A= 7
Therefore, the closed-form expression for anis:
an= 7 ·2n+ 3n−3
35
Question 35
Question
Consider the following recurrence relation:
an=−2an−1+ 3an−2+ 2n
If the initial conditions are a0= 1 and a1= 3, find the explicit formula for
an.
Solution
To find the explicit formula for the recurrence relation, we first need to solve
the associated characteristic equation and then find a particular solution for the
non-homogeneous term 2n.
Step 1: Solve the homogeneous part of the recurrence relation by setting
an=rn:
Substitute an=rninto the homogeneous part of the recurrence relation:
rn=−2rn−1+ 3rn−2
r2=−2r+ 3
Solving the characteristic equation r2+ 2r−3 = 0 gives us roots r=−3
and r= 1. Therefore, the general solution to the homogeneous part is:
a(h)
n=c1(−3)n+c2(1)n
Step 2: Find a particular solution for the non-homogeneous term 2n:
Guess a particular solution of the form a(p)
n=Arn, where Ais a constant to
be determined. Substitute this into the original recurrence relation:
Arn=−2Arn−1+ 3Arn−2+ 2n
Arn=−2Arn−1+ 3Arn−2+ 2n
Solving for A, we get A=−2
3. Therefore, the particular solution is a(p)
n=
−2
32n.
Step 3: Combine the general solution and the particular solution:
The explicit formula for the overall solution is:
an=a(h)
n+a(p)
n=c1(−3)n+c2(1)n−2
32n
Step 4: Find the values of c1and c2using the initial conditions:
Given a0= 1 and a1= 3, we have:
c1+c2−2
3= 1
36
Question 2
Question
Let anbe a sequence defined by the recurrence relation an= 3an−1−2an−2
for n≥2 with initial conditions a0= 1 and a1= 2. Determine a closed-form
expression for anfor n≥0.
Solution
We first solve the characteristic equation associated with the homogeneous part
of the recurrence relation an= 3an−1−2an−2:
Step 1: Write down the characteristic equation The characteristic
equation is obtained by setting an=rn:
rn= 3rn−1−2rn−2
Dividing by rn−2:
r2= 3r−2
This gives us the characteristic equation r2−3r+ 2 = 0.
Step 2: Find the roots of the characteristic equation Factoring the
characteristic equation:
(r−1)(r−2) = 0
So, the roots are r= 1 and r= 2.
Step 3: Write down the general solution of the homogeneous part
The general solution of the homogeneous part is:
an=A·1n+B·2n
an=A+B·2n
Next, we find the particular solution to the non-homogeneous part. Given
the form of the non-homogeneous part, we guess a particular solution of the
form an=C.
Step 4: Solve for the particular solution Substitute an=Cback into
the original recurrence relation:
C= 3C−2C
Solving this, we find C= 0.
Now, we combine the solutions of the homogeneous and non-homogeneous
parts to get the general solution for an.
Step 5: Write down the general solution The general solution for an
is:
an=A+B·2n
2
Step 6: Use initial conditions to find the values of A and B Using
the initial conditions a0= 1 and a1= 2:
a0=A+B·20=A+B= 1
a1=A+B·21=A+ 2B= 2
Solving these equations simultaneously, we find A=2
3and B=1
3.
Step 7: Write down the closed-form expression for anTherefore, the
closed-form expression for anis:
an=2
3+1
3·2n
Question 3
Question
Consider the following recurrence relation:
an= 3an−1−2an−2+n, for n≥2
with initial conditions a0= 1 and a1= 3. Find the general solution for an.
Solution
To find the general solution for the given recurrence relation, we first need to
find the characteristic equation by assuming anhas the form an=rn.
Step 1: Find the characteristic equation Assume an=rn. Substitute
this into the recurrence relation to get:
rn= 3rn−1−2rn−2+n
Divide the whole equation by rn−2:
r2= 3r−2 + n
rn−2
Since rngrows faster than n, limn→∞ n
rn−2= 0, so we can neglect the last
term. This gives us the characteristic equation as:
r2−3r+ 2 = 0
The characteristic equation factors into:
(r−1)(r−2) = 0
So the roots are r1= 1 and r2= 2.
Step 2: Find the homogeneous solution The general solution of the
homogeneous equation is then:
a(h)
n=A(1)n+B(2)n
3
a(h)
n=A+ 2B
Step 3: Find a particular solution In this case, we can assume a par-
ticular solution of the form an=An +B. Substitute this into the original
recurrence relation:
An +B= 3(A(n−1) + B)−2(A(n−2) + B) + n
An +B= 3An −3A+ 3B−2An + 4A−2B+n
Equating coefficients, we have:
4A−2 = 1 =⇒A=3
2
−3A+ 3B= 0 =⇒B=3
2
Step 4: Find the general solution Therefore, the general solution for
the recurrence relation is:
an=A+ 2B+3n
2+3
2
an=3
2+3+3n
2+3
2
an= 3n+ 4
Question 4
Question
Consider the following recurrence relation involving both homogeneous and non-
homogeneous terms:
an= 3an−1−2an−2+ 2n, a0= 2, a1= 5
Find a formula for anin terms of nfor n≥2.
Solution
To solve this recurrence relation, we will first find the general solution to the
corresponding homogeneous relation an= 3an−1−2an−2, then find a particular
solution to the non-homogeneous part 2n, and combine the two to get the final
solution.
Step 1: Homogeneous Solution
The characteristic equation for the homogeneous part is r2−3r+ 2 = 0,
which factors as (r−1)(r−2) = 0. Thus, the roots are r1= 1 and r2= 2.
The general solution to the homogeneous part is an=A·1n+B·2n, where
Aand Bare constants to be determined.
4
Step 2: Particular Solution
To find a particular solution to the non-homogeneous part 2n, we assume
that an=C·2n, where Cis a constant to be determined.
Substitute an=C·2ninto the original recurrence relation:
C·2n= 3(C·2n−1)−2(C·2n−2)+2n
Simplify to get:
C=2n
2
Therefore, the particular solution is an=1
2·2n.
Step 3: Combining Solutions
The general solution to the recurrence relation is the sum of the homogeneous
and particular solutions:
an=A·1n+B·2n+1
2·2n
Applying the initial conditions a0= 2 and a1= 5:
a0=2: A+B+1
2= 2
a1=5: A+ 2B+1
2·2 = 5
Solving these two equations simultaneously gives A=5
2and B=−1
2.
Therefore, the formula for anfor n≥2 is:
an=5
2+−1
2·2n+1
2·2n
Question 5
Question
Consider the homogeneous recurrence relation defined by an= 2an−1−an−2,
with initial conditions a0= 0 and a1= 1. Determine a closed-form expression
for an.
Solution
To find a closed-form expression for an, we first need to find the characteris-
tic equation associated with the given homogeneous recurrence relation. Step
1: Write down the characteristic equation The characteristic equation for the
recurrence relation an= 2an−1−an−2is given by
r2= 2r−1
5
Step 2: Solve the characteristic equation To solve the characteristic equa-
tion r2= 2r−1, we rearrange it to the standard form r2−2r+ 1 = 0,
(r−1)2= 0
r= 1
Step 3: Form the general solution Since we have a repeated root at r= 1,
the general solution will have the form
an=c1·1n+c2·n·1n
an=c1+c2n
Step 4: Apply initial conditions Using the initial conditions a0= 0 and
a1= 1, we can solve for c1and c2. Substitute n= 0 into the general solution:
a0=c1+c2·0=0
c1= 0
Substitute n= 1 into the general solution:
a1= 0 + c2·1=1
c2= 1
Step 5: Final expression Therefore, the closed-form expression for anis
an=n
Question 6
Question
Consider the non-homogeneous linear recurrence relation:
an+2 −5an+1 + 6an= 3
with initial conditions a0= 1 and a1= 2. Find a closed-form expression for
anfor n≥0.
Solution
Step 1: First, we find the characteristic equation for the corresponding homo-
geneous recurrence relation:
r2−5r+ 6 = 0
This factors as (r−2)(r−3) = 0, so the characteristic roots are r1= 2 and
r2= 3.
6
Step 2: The solution to the homogeneous recurrence relation is:
a(h)
n=A(2)n+B(3)n
where Aand Bare constants to be determined.
Step 3: Next, we find a particular solution for the non-homogeneous equation
by guessing a solution of the form a(p)
n=C. Plugging this into the equation,
we get:
C−5C+ 6C= 3
2C= 3
C=3
2
So, a particular solution is a(p)
n=3
2.
Step 4: 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
an=A(2)n+B(3)n+3
2
Step 5: Using the initial conditions a0= 1 and a1= 2, we can solve for A
and B.
From a0= 1, we have:
A+B+3
2= 1
A+B=−1
2
From a1= 2, we have:
2A+ 3B+3
2= 2
2A+ 3B=1
2
Solving these equations simultaneously, we find A=1
2and B=−1.
Step 6: Therefore, the closed-form expression for anis:
an=1
2(2)n−(3)n+3
2
7
Question 7
Question
Find a closed-form expression for the solution of the non-homogeneous recur-
rence relation given by:
an= 3an−1−2an−2+ 2n
with initial conditions a0= 1 and a1= 2.
Solution
To solve the non-homogeneous recurrence relation, we will first find the general
solution to the corresponding homogeneous recurrence relation an= 3an−1−
2an−2, and then find a particular solution to the non-homogeneous recurrence
relation. Finally, we will combine these two solutions to find the closed-form
expression for an.
Step 1: Find the homogeneous solution Let’s assume the homogeneous
solution is of the form a(h)
n=rn. Substituting this into the homogeneous
recurrence relation, we get:
rn= 3rn−1−2rn−2
Dividing by rn−2, we get the characteristic equation r2= 3r−2. Solving
this equation, we find r= 2 and r= 1. Therefore, the general solution to the
homogeneous recurrence relation is:
a(h)
n=Arn+Brm
where Aand Bare constants to be determined.
Since we have initial conditions a0= 1 and a1= 2, we can solve for Aand B
by substituting these into the general form of the homogeneous solution. This
gives us the equations:
A+B= 1
2A+ 2B= 2
Solving these equations simultaneously, we find A= 1 and B= 0, so the
homogeneous solution is a(h)
n= 2n.
Step 2: Find a particular solution To find a particular solution to the
non-homogeneous recurrence relation an= 3an−1−2an−2+2n, we will guess that
the particular solution has a form similar to the non-homogeneous term, which
is 2n. Let’s assume a(p)
n=C·2n. Substituting this into the non-homogeneous
recurrence relation, we get:
C·2n= 3(C·2n−1)−2(C·2n−2)+2n
Simplifying this equation, we find C= 1. Therefore, the particular solution
is a(p)
n= 2n.
8
Step 3: Find the final solution The general solution to the non-homogeneous
recurrence relation is given by the sum of the homogeneous and particular so-
lutions:
an=a(h)
n+a(p)
n= 2n+ 2n= 2n+1
Thus, the closed-form expression for the solution of the non-homogeneous
recurrence relation is an= 2n+1 for n≥0.
Question 8
Question
Let anbe defined recursively by the relation an+1 = 3an−2n+1 for n≥0, with
initial condition a0= 4. Find a closed-form expression for an.
Solution
Step 1: Find the characteristic equation by assuming a solution of the form
an=rn.
an+1 = 3an−2n+1
rn+1 = 3rn−2n+1
r−3 = −2
r
r2−3r+ 2 = 0
(r−1)(r−2) = 0
Step 2: The characteristic equation has repeated roots r= 1,2, so the
general solution is given by an=c1(1n) + c2(2n).
Step 3: Use the initial condition a0= 4 to solve for c1and c2.
a0=c1(10) + c2(20)
4 = c1+c2
Step 4: Differentiate the general solution to get an expression for an+1.
an+1 =c1(1) + c2(2nln 2)
Step 5: Use an+1 = 3an−2n+1 to find c1and c2.
c1+ 2c2ln 2 = 3(c1+c2)−2n+1
c1+ 2c2ln 2 = 3c1+ 3c2−2n+1
−2c1−c2(1 −2 ln 2) = −2n+1
Step 6: Solve the system of equations to find c1and c2.
c1+c2= 4
−2c1−c2(1 −2 ln 2) = −2
Solving this system will give the values of c1and c2, resulting in the closed-form
expression for an.
9
Question 9
Question
Consider the non-homogeneous recurrence relation given by an= 3an−1−
2an−2+ 2nwith initial conditions a0= 1 and a1= 2. Find the explicit formula
for an.
Solution
Step 1: For the homogeneous part, we first solve the characteristic equation
rn= 3rn−1−2rn−2. This simplifies to r2−3r+ 2 = 0, which factors as
(r−1)(r−2) = 0. So, the characteristic roots are r1= 1 and r2= 2.
Step 2: The general solution for the homogeneous part is given by a(h)
n=
c1(1)n+c2(2)n, where c1and c2are constants to be determined.
Step 3: Next, we consider the particular solution. Since the non-homogeneous
part is 2n, a good guess is a(p)
n=A·2n. Substitute a(p)
ninto the original recur-
rence relation to find A:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n.
Step 4: Simplify the above equation to get A= 1. Therefore, the particular
solution is a(p)
n= 2n.
Step 5: The general solution for the non-homogeneous part is then given by
an=a(h)
n+a(p)
n=c1(1)n+c2(2)n+ 2n.
Step 6: Apply the initial conditions a0= 1 and a1= 2 to solve for c1and
c2. Substitute n= 0 into the general solution: c1+c2+ 1 = 1. Substitute n= 1
into the general solution: c1+ 2c2+ 2 = 2.
Step 7: Solving the above system of equations, we find c1= 0 and c2= 1.
Therefore, the explicit formula for anis: an= 2n.
Question 10
Question
Consider the following non-homogeneous recurrence relation:
an= 3an−1−2an−2+ 2n
where a0= 1 and a1= 2. Find the formula for anin terms of n.
10
Solution
To solve the non-homogeneous recurrence relation, we first find the general
solution to the corresponding homogeneous relation.
an−3an−1+ 2an−2= 0 (homogeneous part)
r2−3r+ 2 = 0
(r−1)(r−2) = 0
r= 1,2.
So the general solution is an=c1·1n+c2·2n, where c1and c2are constants to
be determined.
Next, we find a particular solution to the non-homogeneous part. Since 2n
is of the form c·dnwhere d= 2 and c= 1, a particular solution is of the form
A·2n.
Substitute an=A·2ninto the original relation:
A·2n= 3(A·2n−1)−2(A·2n−2)+2n
Let’s simplify this equation:
A·2n= 3A·2n−1−2A·2n−2+ 2n
A·2n= 3A·2n−6A·2n+ 2n
A=1
2.
Therefore, a particular solution is an=1
2·2n= 2n−1.
Combining the general solution and the particular solution, we find the for-
mula for an:
an=c1·1n+c2·2n+ 2n−1
Using the initial conditions a0= 1 and a1= 2, we can find the values of c1
and c2:(c1+c2+ 1 = 1
c1·1 + c2·2 + 1
2= 2
Solving these equations gives c1=−1
2and c2= 1. Therefore, the formula
for anis:
an=−1
2+ 2n+ 2n−1.
Question 11
Question
Given the non-homogeneous recurrence relation:
an= 2an−1+ 3 ·2n
with initial condition a0= 1, find the explicit formula for an.
11
Solution
Step 1: Begin by finding the general solution to the associated homogeneous
recurrence relation an= 2an−1. The characteristic equation is r−2 = 0, which
has a root r= 2. So, the general solution to the homogeneous recurrence
relation is a(h)
n=c·2nfor some constant c.
Step 2: Next, find a particular solution to the non-homogeneous recurrence
relation. Since the non-homogeneous term is of the form 3 ·2n, let’s try a
particular solution of the form a(p)
n=An ·2nand substitute it into the original
recurrence relation.
An ·2n= 2(An −1·2n−1)+3·2n
An ·2n= 2An ·2n−2A·2n−1+ 3 ·2n
Step 3: Solve for Aby comparing coefficients of like terms.
An = 2An + 3 ⇒A=−3
Step 4: Now, the particular solution is a(p)
n=−3n·2n.
Step 5: The general solution to the non-homogeneous recurrence relation is
the sum of the general solution to the homogeneous recurrence relation and the
particular solution:
an=a(h)
n+a(p)
n=c·2n−3n·2n
Step 6: Finally, use the initial condition a0= 1 to solve for c:
a0=c−0=1⇒c= 1
Therefore, the explicit formula for anis:
an= 2n−3n·2n
Question 12
Question
Consider the following recurrence relation: an= 3an−1−3an−2+ 2n. Given
that a0= 1 and a1= 2, find an explicit formula for an.
Solution
Step 1: Find the homogeneous solution to the recurrence relation.
The characteristic equation is r2= 3r−3, which simplifies to r2−3r+ 3 = 0.
Solving this quadratic equation, we find that the roots are r1=3+i√3
2and
r2=3−i√3
2. Therefore, the homogeneous solution is of the form
a(h)
n=c1 3 + i√3
2!n
+c2 3−i√3
2!n
.
12
Step 2: Find the particular solution to the non-homogeneous part of the
recurrence relation.
We look for a particular solution of the form a(p)
n=An2n. Substituting this
into the original recurrence relation, we get
An2n= 3An2n−1−3An2n−2+ 2n.
By comparing coefficients, we find that A=−1
2. Thus, the particular solution
is a(p)
n=−1
2n2n.
Step 3: Find the full solution to the recurrence relation.
Therefore, the general solution is
an=a(h)
n+a(p)
n=c1 3 + i√3
2!n
+c2 3−i√3
2!n
−1
2n2n.
Step 4: Use the initial conditions to solve for the constants.
Given that a0= 1 and a1= 2, we can substitute these values into the general
solution: (c1+c2= 1
3+i√3
2c1+3−i√3
2c2−2 = −1
Solving these equations, we find c1=1
3and c2=2
3.
Step 5: Write down the explicit formula for an.
Substitute the values of c1and c2back into the general solution to get
an=1
3 3 + i√3
2!n
+2
3 3−i√3
2!n
−1
2n2n.
Question 13
Question
Let (an) be 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
To find a closed-form expression for the sequence (an), we first need to find
the characteristic equation of the given homogeneous linear recurrence relation.
The characteristic equation is given by r2−2r−3 = 0.
Step 1: Find the roots of the characteristic equation Solving r2−
2r−3 = 0 gives us r= 3 and r=−1.
Therefore, the general solution to the homogeneous recurrence relation is
an=c1·3n+c2·(−1)nfor constants c1and c2.
13
Step 2: Find particular solution for the non-homogeneous part
Since the non-homogeneous part 3an−2has the form of Krnwith K= 3 and
r= 3, we look for a particular solution of the form an=B·3n. Substituting
this into the recurrence relation, we get:
B·3n= 2(B·3n−1) + 3(B·3n−2)
B= 2B+ 1
B= 1
So, a particular solution is an= 3n.
Step 3: Write down the general solution Putting the general solution
to the homogeneous part and the particular solution together, we have:
an=c1·3n+c2·(−1)n+ 3n
Step 4: Use initial conditions to evaluate constants Using the initial
conditions: a0= 1 and a1= 2, we get the equations: c1+c2+ 1 = 1 and
3c1−c2+ 3 = 2
Solving these equations gives c1=1
2and c2=−1
2.
Therefore, the closed-form expression for the sequence (an) is given by:
an=1
2·3n−1
2·(−1)n+ 3n
Question 14
Question
Let anbe the sequence defined recursively by the recurrence relation an=
3an−1−2an−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 of the homogeneous recurrence relation
an= 3an−1−2an−2.
The characteristic equation is given by r2−3r+ 2 = 0. Factoring this
equation, we get (r−1)(r−2) = 0. Therefore, the characteristic roots are
r1= 1 and r2= 2.
Step 2: Write the general solution of the homogeneous recurrence relation.
The general solution is given by an=A·1n+B·2n, where Aand Bare
constants to be determined.
Step 3: Use the initial conditions to solve for the constants Aand B.
Substitute n= 0 into the general solution and the initial condition a0= 1,
we get: 1 = A·10+B·20=A+B
Substitute n= 1 into the general solution and the initial condition a1= 2,
we get: 2 = A·11+B·21=A+ 2B
14
Solving the system of equations A+B= 1 and A+ 2B= 2, we find A= 2
and B=−1.
Step 4: Write the final formula for an.
Therefore, the formula for anis an= 2 ·1n−1·2n= 2 −2nfor n≥0.
Question 15
Question
Consider the following recurrence relation:
an= 3an−1−2an−2+ 2n
with initial conditions a0= 1 and a1= 3. Find a closed-form expression for an.
Solution
Step 1: Find the homogeneous solution to the recurrence relation by setting
an=rn:
rn= 3rn−1−2rn−2
Dividing by rn−2gives the characteristic equation:
r2= 3r−2
r2−3r+ 2 = 0
(r−1)(r−2) = 0
Which gives the roots r= 1 and r= 2. Therefore, the homogeneous solution is:
a(h)
n=A(1)n+B(2)n
a(h)
n=A+ 2B
Step 2: Find a particular solution due to the non-homogeneous term 2n.
Since 2nis a geometric progression, we guess a particular solution of the form
a(p)
n=C·2n. Substitute this back into the original recurrence relation:
C·2n= 3(C·2n−1)−2(C·2n−2)+2n
C·2n= 3C·2n−1−2C·2n−2+ 2n
C=1
2
Therefore, the particular solution is a(p)
n=1
2·2n= 2n−1.
Step 3: Combine the homogeneous and particular solutions to find the gen-
eral solution:
an=a(h)
n+a(p)
n
15
an=A+ 2B+ 2n−1
Step 4: Apply the initial conditions a0= 1 and a1= 3: From a0= 1:
A+ 2B+1
2= 1
A+ 2B=1
2
From a1= 3:
A+ 2B+ 2 = 3
A+ 2B= 1
Subtracting these equations gives:
1
2−1 = 1
2
This implies that the initial conditions are inconsistent, and the closed-form
expression cannot be uniquely determined.
Question 16
Question
Consider the non-homogeneous recurrence relation defined by an= 3an−1−
2an−2+ 2nfor all integers n≥2 with initial conditions a0= 1 and a1=−1.
Determine the closed form expression for anin terms of n.
Solution
Step 1: Find the characteristic equation associated with the homogeneous part
of the recurrence relation.
The characteristic equation is given by r2= 3r−2, which simplifies to
r2−3r+ 2 = 0. Factoring the quadratic gives (r−1)(r−2) = 0, so the roots
are r1= 1 and r2= 2.
Therefore, the homogeneous solution is of the form a(h)
n=C1·1n+C2·2n=
C1+C2·2n.
Step 2: Find a particular solution for the non-homogeneous part of the
recurrence relation.
Guessing a form for the particular solution based on the non-homogeneous
term gives a(p)
n=An ·2n, where Ais a constant to be determined.
Substitute the guess into the original recurrence relation:
An ·2n= 3(An −1·2n−1)−2(An −2·2n−2)+2n
Step 3: Solve for the constant Aby comparing coefficients of powers of 2.
16
First, divide both sides by 2nto simplify the equation:
An = 3(A(n−1) −2(A(n−2)) + 1
Expanding and simplifying gives:
An = 3An −3A−2An + 4A+ 1
An =An +A+ 1
A= 1
Therefore, the particular solution is a(p)
n=n·2n.
Step 4: Combine the homogeneous and particular solutions to find the gen-
eral solution.
The general solution is given by an=a(h)
n+a(p)
n:
an=C1+C2·2n+n·2n
Step 5: Apply the initial conditions to find the values of C1and C2.
Using the initial conditions a0= 1 and a1=−1:
1 = C1+C2
−1 = C1+ 2C2
Solving this system of equations gives C1= 2 and C2=−1.
Therefore, the closed form expression for anis:
an= 2 −2n+n·2n
Question 17
Question
Let anbe a sequence defined recursively by the following recurrence relation:
an= 2an−1−2an−2+n, n ≥2
with initial conditions a0= 1 and a1= 3. Find a closed-form expression for an.
Solution
Step 1: First, we solve the homogeneous part an= 2an−1−2an−2. Assume
an=rn, then the characteristic equation is rn= 2rn−1−2rn−2. Dividing
by rn−2, we get r2= 2r−2, which simplifies to r2−2r+ 2 = 0. The roots
of this quadratic equation are r= 1 ±i, giving us the homogeneous solution:
a(h)
n=c1(1 + i)n+c2(1 −i)n.
17
Step 2: Next, we find a particular solution for the non-homogeneous part
an=n. Since this is a linear function, assume a(p)
n=An +B. Plugging this
into the original recurrence relation, we get:
An +B= 2(A(n−1) + B)−2(A(n−2) + B) + n
Solving for Aand B, we get A=1
2and B=−1
4. Therefore, the particular
solution is a(p)
n=1
2n−1
4.
Step 3: The general solution is the sum of the homogeneous and particular
solutions:
an=a(h)
n+a(p)
n=c1(1 + i)n+c2(1 −i)n+1
2n−1
4
Step 4: Using the initial conditions a0= 1 and a1= 3 to find c1and c2:
a0=c1(1 + i)0+c2(1 −i)0+1
2·0−1
4=c1+c2−1
4= 1
a1=c1(1 + i)1+c2(1 −i)1+1
2·1−1
4=c1(1 + i) + c2(1 −i) + 1
4= 3
Step 5: Solving the system of equations, we find c1=3
2and c2=1
2. There-
fore, the closed-form expression for anis:
an=3
2(1 + i)n+1
2(1 −i)n+1
2n−1
4
Question 18
Question
Let ansatisfy the recurrence relation an+2 −5an+1 + 6an= 2nfor 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 by assuming an=rn:
r2−5r+ 6 = 0
Solving the quadratic equation gives us r= 2 and r= 3, so the general solution
to the homogeneous part of the recurrence relation is
an=A·2n+B·3n
Step 2: To find a particular solution to the non-homogeneous part of the
recurrence relation, assume an=C·2n. Plugging this into the recurrence
relation gives us 4C−5(2C)+6C= 2n, which simplifies to −3C= 2n. Therefore,
C=−1
3.
18
Step 3: The general solution to the non-homogeneous part is then an=
A·2n+B·3n−1
3·2n. Applying the initial conditions a0= 1 and a1= 2 gives
the system of equations:
A+B−1
3= 1
2A+ 3B−2
3= 2
Step 4: Solving the system of equations gives A=5
3and B=−2
3. Therefore,
the closed-form expression for anis
an=5
3·2n−2
3·3n−1
3·2n
Question 19
Question
Let anbe the sequence defined recursively by a0= 2, a1= 3, and an+1 =
3an−2an−1for n≥1. Determine a formula for an.
Solution
Step 1: First, let’s find the first few values of the sequence to look for a pattern:
a0= 2
a1= 3
a2= 3a1−2a0= 3(3) −2(2) = 7
a3= 3a2−2a1= 3(7) −2(3) = 15
a4= 3a3−2a2= 3(15) −2(7) = 29
Step 2: Now, we can see a pattern emerging. It seems that an= 2n+ 1 for
all n≥0. We will prove this by mathematical induction.
Step 3: Basis step: Verify the formula for the base cases. For n= 0,
a0= 20+ 1 = 1 + 1 = 2, which is correct. For n= 1, a1= 21+ 1 = 2 + 1 = 3,
which is correct.
Step 4: Inductive step: Assume that ak= 2k+ 1 for some arbitrary k≥1.
Now, we will prove that ak+1 = 2k+1 + 1.
ak+1 = 3ak−2ak−1
= 3(2k+ 1) −2(2k−1+ 1)
= 3 ·2k+ 3 −2·2k−1−2
= 3 ·2k+ 1 −2k−2
= 2(2k)+1
= 2k+1 + 1
19
Thus, the formula an= 2n+ 1 holds for all n≥0 by mathematical induction.
Question 20
Question
Consider the non-homogeneous recurrence relation defined by an= 4an−1−
4an−2+ 2nwith initial conditions a0= 2 and a1= 7. Find a closed-form
expression for an.
Solution
To solve the non-homogeneous recurrence relation, we first need to find the
general solution to the corresponding homogeneous recurrence relation an=
4an−1−4an−2.
Step 1: Find the characteristic equation Let an=rn. Then, substi-
tuting an=rninto the homogeneous recurrence relation, we get:
rn= 4rn−1−4rn−2
Dividing by rn−2, we obtain:
r2= 4r−4
This simplifies to the characteristic equation:
r2−4r+ 4 = 0
(r−2)2= 0
r= 2
So, the characteristic roots are r1=r2= 2.
Step 2: Find the general solution to the homogeneous recurrence
relation The general solution to the homogeneous recurrence relation is given
by:
a(h)
n=A·2n+B·n·2n
where Aand Bare constants to be determined.
Step 3: Find a particular solution to the non-homogeneous recur-
rence relation The non-homogeneous term 2nis a geometric sequence, so we
try a particular solution of the form a(p)
n=C·2n.
Substitute a(p)
n=C·2ninto the non-homogeneous recurrence relation:
C·2n= 4(C·2n−1)−4(C·2n−2)+2n
C= 2
Thus, a particular solution is a(p)
n= 2 ·2n= 2n+1.
Step 4: Find the general solution to the non-homogeneous re-
currence relation The general solution to the non-homogeneous recurrence
20
relation is the sum of the general solution to the homogeneous relation and the
particular solution to the non-homogeneous relation:
an=a(h)
n+a(p)
n=A·2n+B·n·2n+ 2n+1
Step 5: Apply initial conditions Using the initial conditions a0= 2 and
a1= 7, we can find the values of Aand B:
a0=A·20+B·0·20+ 21= 2
A+ 2 = 2 =⇒A= 0
a1=A·21+B·1·21+ 22= 7
2B+ 4 = 7 =⇒B=3
2
Step 6: Final solution Therefore, the closed-form expression for anis:
an=3
2·n·2n+ 2n+1
Question 21
Question
Let anbe the sequence defined by the recurrence relation an+2 = 3an+1 −2an
where a0= 1 and a1= 2. Find a closed-form expression for an.
Solution
Step 1: Write the characteristic equation associated with the given recurrence
relation. The characteristic equation is obtained by setting an=rnin the
relation an+2 = 3an+1 −2an.
Step 2: Substitute an=rninto the recurrence relation to get the character-
istic equation.
r2= 3r−2
Step 3: Rearrange the characteristic equation to get it in the form r2−3r+
2 = 0.
Step 4: Solve the characteristic equation to find the roots r1and r2.
(r−1)(r−2) = 0
r1= 1, r2= 2
Step 5: The solution to the homogeneous recurrence relation is then
an=c1(1)n+c2(2)n
21
an=c1+ 2c2
Step 6: Use the initial conditions a0= 1 and a1= 2 to solve for c1and c2.
a0=c1+ 2c2= 1
a1=c1+ 2c2= 2
Step 7: Solve the system of equations to find c1and c2. Substitute c1=
1−2c2into a1= 2.
1−2c2+ 2c2= 2
−c2= 1
c2=−1
Step 8: Substitute c2=−1 back into c1= 1 −2c2.
c1= 1 −2(−1) = 3
Step 9: Therefore, the closed-form expression for the sequence anis
an= 3 −2n
Question 22
Question
Consider the recurrence relation defined by an+2 = 5an+1 −6an+2nwith initial
conditions a0= 0 and a1= 1. Find a closed-form expression for an.
Solution
Step 1: Finding the characteristic equation To find a closed-form expression for
an, we first need to find the characteristic equation by assuming a solution of
the form an=rn. Substitute an=rninto the recurrence relation:
rn+2 = 5rn+1 −6rn+ 2n
Divide by rn:
r2= 5r−6 + 2
rn
The characteristic equation is then:
r2−5r+ 6 = 0
Factor the characteristic equation:
(r−2)(r−3) = 0
22
So, the characteristic roots are r1= 2 and r2= 3.
Step 2: Finding the homogeneous solution The homogeneous solution is
given by ahom
n=A(2n)+B(3n), where Aand Bare constants to be determined.
Step 3: Finding the particular solution Now, we need to find a particular
solution for the non-homogeneous term 2n. We assume that the particular
solution is of the form apar
n=C(2n).
Substitute apar
n=C(2n) into the recurrence relation:
C(2n+2) = 5C(2n+1)−6C(2n)+2n
4C(2n) = 5C(2n)−6C(2n)+2n
4C=−C+1
2n
5C=1
2n
C=1
5·2n
Step 4: Writing the general form of the solution The general solution of the
recurrence relation is:
an=ahom
n+apar
n=A(2n) + B(3n) + 1
5·2n
Step 5: Using initial conditions to find constants Using the initial conditions
a0= 0 and a1= 1 to solve for Aand B:
a0=A+B+1
5= 0
a1= 2A+ 3B+1
10 = 1
Solving these equations gives A=−2
5and B=9
10 .
Step 6: Final closed-form expression Therefore, the closed-form expression
for anis:
an=−2
5(2n) + 9
10(3n) + 1
5·2n
Question 23
Question
Consider the non-homogeneous recurrence relation defined by an= 2an−1+n3,
where a0= 3. Find an explicit formula for an, where n≥1.
23
Solution
Step 1: Find the homogeneous solution by setting an= 2an−1.
an−2an−1= 0
an= 2an−1
Step 2: Write the characteristic equation for the homogeneous relation.
r−2=0
r= 2
Step 3: Write down the solution to the homogeneous relation.
an=C·2n
Step 4: Find the particular solution for the non-homogeneous part. Assume
anis of the form an3+bn2+cn +d.
an= 2an−1+n3
an3+bn2+cn +d= 2(a(n−1)3+b(n−1)2+c(n−1) + d) + n3
Step 5: Expand the terms and match coefficients to solve for a,b,c, and d.
an3+bn2+cn +d= 2(an3−3an2+ 3an −a+bn2−2bn +b+cn −c+d) + n3
an3+bn2+cn +d= 2an3−6an2+ 6an −2a+ 2bn2−4bn + 2b+ 2cn −2c+ 2d+n3
an3+bn2+cn +d= 2an3+ 2bn2+ 2cn + (6a−6b+ 2)n−2a−4b−2c+ 2d
Step 6: Equate coefficients to solve for a,b,c, and d.
a= 2, b =−2, c = 3, d =−1
Step 7: Write down the particular solution for the non-homogeneous part.
an= 2n3−2n2+ 3n−1
Step 8: Combine the homogeneous and non-homogeneous solutions to get
the explicit formula for an.
an=C·2n+ 2n3−2n2+ 3n−1
Step 9: Use the initial condition a0= 3 to solve for C.
3 = C·20+ 2(0)3−2(0)2+ 3(0) −1
C= 4
Step 10: Write down the final explicit formula for an.
an= 4 ·2n+ 2n3−2n2+ 3n−1
24
Question 24
Question
Determine a closed-form expression for the sequence defined by the recurrence
relation an= 3an−1−an−2+ 2nwith initial conditions a0= 1 and a1= 3.
Solution
Step 1: Finding the homogeneous solution
We first solve the homogeneous recurrence relation an= 3an−1−an−2.
Assume the solution has the form an=rn. Substitute this form into the
relation to get rn= 3rn−1−rn−2. This simplifies to r2= 3r−1, which gives
the characteristic equation r2−3r+ 1 = 0. Solve this quadratic equation to
find r1and r2.
Step 2: Finding the particular solution
Next, we look for a particular solution to the non-homogeneous part 2n.
Since 2nis an exponential function, we try a similar form, an=A·2n. Substitute
an=A·2ninto the original recurrence relation to get A·2n= 3A·2n−1−A·
2n−2+ 2n. Simplify this to find the value of A.
Step 3: Combining solutions
The general solution is the sum of the homogeneous and particular solutions:
an=C1rn
1+C2rn
2+A·2n. Use the initial conditions a0= 1 and a1= 3 to find
C1,C2, and A.
Step 4: Final closed-form expression
Substitute the values of C1,C2, and Aback into the general solution to
obtain the closed-form expression for an.
Question 25
Question
Consider the homogeneous recurrence relation: an+2 −5an+1 + 6an= 0 where
a0= 2 and a1= 3. Determine the closed-form expression for anusing the
characteristic equation method.
Solution
To find the closed-form expression for an, we need to solve the characteristic
equation associated with the homogeneous recurrence relation.
Step 1: Write the characteristic equation The characteristic equation
for the given homogeneous recurrence relation is:
r2−5r+ 6 = 0
25
Step 2: Solve the characteristic equation To solve the characteristic
equation, we can factorize it as:
r2−5r+ 6 = (r−2)(r−3) = 0
This gives us the roots:
r1= 2 and r2= 3
Step 3: Write the general solution The general solution for the recur-
rence relation is:
an=A·2n+B·3n
Step 4: Find the values of A and B using initial conditions Given
that a0= 2 and a1= 3, we can substitute these values into the general solution:
a0=A·20+B·30=A+B= 2
a1=A·21+B·31= 2A+ 3B= 3
Solving these equations simultaneously, we find that A= 1 and B= 1.
Step 5: Final closed-form expression Therefore, the closed-form ex-
pression for the given recurrence relation is:
an= 1 ·2n+ 1 ·3n= 2n+ 3n
Question 26
Question
Let anbe the sequence defined by the recurrence relation an= 2an−1−2an−2+n
for n≥2, with initial conditions a0= 1 and a1= 2. Find a closed-form
expression for an.
Solution
Step 1: Find the homogeneous solution to the recurrence relation. Assume an
has the form an=rn.
rn= 2rn−1−2rn−2
r2= 2r−2
r2−2r+ 2 = 0
Step 2: Solve the characteristic equation r2−2r+ 2 = 0 using the quadratic
26
formula.
r=2±p(−2)2−4·1·2
2·1
r=2±√4−8
2
r=2±√−4
2
r=2±2i
2
r= 1 ±i
Step 3: The general solution to the homogeneous recurrence relation is an=
c1(1 + i)n+c2(1 −i)n, where c1and c2are constants to be determined.
Step 4: Apply initial conditions a0= 1 and a1= 2 to find the particular
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
Step 5: Solve the equations c1+c2= 1 and c1(1 + i) + c2(1 −i)=2
simultaneously to find c1and c2.
c1+c2= 1
c1(1 + i) + c2(1 −i)=2
Solving these equations, we get c1=1
2and c2=1
2.
Step 6: Substitute the values of c1and c2back into the general solution to
get the closed-form expression for an.
an=1
2(1 + i)n+1
2(1 −i)n
Question 27
Question
Let anbe defined recursively by a0= 1, a1= 2, and an+2 = 2an+1 −2anfor
n≥0. Find a closed-form expression for an.
Solution
Step 1: First, let’s find the characteristic equation of the homogeneous recur-
rence relation an+2 = 2an+1 −2an. Let an=rn. Substitute an=rninto
the homogeneous recurrence relation: rn+2 = 2rn+1 −2rnThis simplifies to:
r2= 2r−2r2−2r+ 2 = 0
27
Step 2: Next, solve the characteristic equation r2−2r+ 2 = 0 to find the
roots. Using the quadratic formula: r=−(−2)±√(−2)2−4(1)(2)
2(1) r=2±√4−8
2
r=2±√−4
2r=2±2i
2r= 1 ±i
Step 3: Since the roots are complex (1 ±i), the general solution takes
the form: an=c1(1 + i)n+c2(1 −i)nan=c1cos n·π
2+isin n·π
2+
c2cos n·π
2−isin n·π
2an=c12ncos n·π
2+c22nsin n·π
2
Step 4: To find the values of c1and c2, we use the initial conditions a0= 1
and a1= 2. From a0= 1: 1 = c120cos 0·π
2+c220sin 0·π
21 = c1From
a1= 2: 2 = c121cos π
2+c221sin π
22=2c2c2= 1
Step 5: Therefore, the closed-form expression for anis: an= cos nπ
2+
2nsin nπ
2
Question 28
Question
Consider the following non-homogeneous recurrence relation:
an= 2an−1−an−2+ 2n
where a0= 1 and a1= 3. Find a general formula for anin terms of n.
Solution
Step 1: First, we will find the general solution to the associated homogeneous
recurrence relation.
The associated homogeneous recurrence relation is given by:
an= 2an−1−an−2
Let’s assume a solution of the form an=rn. Substituting this into the
homogeneous recurrence relation, we get:
rn= 2rn−1−rn−2
Dividing by rn−2(assuming r= 0), we get:
r2= 2r−1
This gives us the characteristic equation r2−2r+ 1 = (r−1)2= 0. Thus,
we have a repeated root r= 1.
Therefore, the general solution to the homogeneous recurrence relation is
given by an=c1·1n+c2·n·1n=c1+c2n.
Step 2: Now, we will find a particular solution to the non-homogeneous
recurrence relation.
28
Since the non-homogeneous term is 2n, let’s assume a particular solution of
the form ap
n=k·2n. Substituting this into the non-homogeneous recurrence
relation, we get:
k·2n= 2(k·2n−1)−(k·2n−2)+2n
Simplifying, we find that k=−1.
Therefore, a particular solution to the non-homogeneous recurrence relation
is ap
n=−2n.
Step 3: Combining the general solution to the homogeneous recurrence re-
lation and the particular solution to the non-homogeneous recurrence relation,
we get the general formula for an:
an=ah
n+ap
n=c1+c2n−2n
Step 4: Using the initial conditions a0= 1 and a1= 3, we can solve for c1
and c2.
From a0= 1, we have c1+c2·0−20= 1, which gives c1−1 = 0 or c1= 1.
From a1= 3, we have c1+c2·1−21= 3, substituting c1= 1, we have
1 + c2−2 = 3 or c2= 4.
Therefore, the general formula for anin terms of nis:
an= 1 + 4n−2n
Question 29
Question
Consider the following recurrence relation:
an+2 = 3an+1 −2an+ 2n
Find the general solution to this non-homogeneous recurrence relation.
Solution
To solve this non-homogeneous recurrence relation, we will first find the general
solution to the corresponding homogeneous relation, and then we will find a
particular solution to the non-homogeneous relation. The general solution to the
non-homogeneous relation will be the sum of the solutions to the homogeneous
and particular solutions.
Step 1: Find the general solution to the homogeneous part
The homogeneous part of the recurrence relation is given by
an+2 = 3an+1 −2an
Let’s assume a solution of the form an=rn. Substituting this into the
homogeneous part gives
29
rn+2 = 3rn+1 −2rn
Dividing by rn, we obtain the characteristic equation
r2= 3r−2
r2−3r+ 2 = 0
Solving the quadratic equation gives us r= 1 and r= 2. Therefore, the
general solution to the homogeneous part is
an=A·1n+B·2n=A+B·2n
where Aand Bare constants to be determined.
Step 2: Find a particular solution to the non-homogeneous part
To find a particular solution, we guess that anhas the form P·2n, where P is
a constant. Substituting this into the non-homogeneous part of the recurrence
relation gives
P·2n+2 = 3P·2n+1 −2P·2n+ 2n
This simplifies to
4P= 6P−2P+ 1
4P= 4P+ 1
This has no solution, so we try a different guess. Let’s try an=Q·2n+R.
Substituting this into the non-homogeneous recurrence relation gives
Q·2n+2 +R= 3(Q·2n+1 +R)−2(Q·2n+R)+2n
This simplifies to
4Q·2n+R= 6Q·2n+ 3R−2Q·2n−2R+ 2n
2Q·2n+ 2R= 2n
Comparing coefficients, we get 2Q= 1 and 2R= 0, so Q=1
2and R= 0.
Therefore, a particular solution is an=1
2·2n.
Step 3: General solution
The general solution to the non-homogeneous recurrence relation is the sum
of the homogeneous and particular solutions:
an=A+B·2n+1
2·2n=A+B+1
2·2n
where A and B are constants determined by the initial conditions.
30
Question 30
Question
Consider the non-homogeneous recurrence relation an= 2an−1−an−2+ 3 ·2n
with initial conditions a0= 0 and a1= 1. Find a closed-form expression for an.
Solution
Step 1: Find the homogeneous solution to the recurrence relation. We first
consider the associated homogeneous recurrence relation a(h)
n= 2a(h)
n−1−a(h)
n−2.
The characteristic equation is r2= 2r−1, which simplifies to r2−2r+ 1 = 0.
This gives us a repeated root r= 1, so the homogeneous solution is a(h)
n=
c1·1n+c2·n·1n=c1+c2n.
Step 2: Find a particular solution to the non-homogeneous recurrence rela-
tion. We look for a particular solution of the form a(p)
n=A·2n. Substituting
this into the original recurrence relation, we get:
A·2n= 2(A·2n−1)−(A·2n−2)+3·2n
A·2n= 2A·2n−1−A·2n−2+ 3 ·2n
A= 2A−A
2+ 3
A=4
3
Thus, the particular solution is a(p)
n=4
3·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=c1+c2n+4
3·2n
Step 4: Use initial conditions to find the values of c1and c2. Using a0= 0
and a1= 1, we have:
c1+4
3= 0
c1+c2+8
3= 1
Solving these equations, we find c1=−4
3and c2= 5.
Step 5: Write the closed-form expression for an. Therefore, the closed-form
expression for anis:
an=−4
3+ 5n+4
3·2n
31
Question 31
Question
Let anbe defined by the recurrence relation an= 3an−1−2an−2for n≥2 with
initial conditions a0= 1 and a1= 2. Find a closed-form expression for an.
Solution
Step 1: Find the characteristic equation by assuming an=rn.
rn= 3rn−1−2rn−2
r2= 3r−2
r2−3r+ 2 = 0
(r−1)(r−2) = 0
So the roots of the characteristic equation are r1= 1 and r2= 2.
Step 2: Write the general solution based on the roots r1and r2.
an=c1·1n+c2·2n
an=c1+c2·2n
Step 3: Use the initial conditions to solve for c1and c2.
a0=c1+c2= 1
a1=c1+ 2c2= 2
Solving for c1and c2, we get c1= 2 and c2=−1.
Step 4: Substitute the values of c1and c2into the general solution to find
the closed-form expression.
an= 2 −2n
Therefore, the closed-form expression for anis an= 2 −2n.
Question 32
Question
Consider the non-homogeneous recurrence relation given by an= 3an−1−
2an−2+ 2n. If the initial conditions are a0= 2 and a1= 5, find a closed-
form expression for an.
32
Solution
Step 1: First, we solve the corresponding homogeneous recurrence relation
a(h)
n= 3a(h)
n−1−2a(h)
n−2. The characteristic equation is r2= 3r−2, which sim-
plifies to r2−3r+ 2 = 0. Factoring, we get (r−1)(r−2) = 0, so the roots are
r= 1 and r= 2. Therefore, the general solution to the homogeneous equation
is a(h)
n=A(1)n+B(2)n, where Aand Bare constants to be determined.
Step 2: Next, we find a particular solution to the non-homogeneous equation.
Since the non-homogeneous term is 2n, we try a particular solution of the form
a(p)
n=C·2n, where Cis a constant to be determined. Substituting this into
the original equation gives:
C·2n= 3(C·2n−1)−2(C·2n−2)+2n
C·2n= 3C·2n−1−2C·2n−2+ 2n
C=1
2
Step 3: Combining the general solution to the homogeneous equation and the
particular solution gives the general solution to the non-homogeneous equation:
an=a(h)
n+a(p)
n=A(1)n+B(2)n+1
2·2n
Step 4: Using the initial conditions a0= 2 and a1= 5, we get the following
two equations:
A+B+1
2= 2
A(1) + B(2) + 1
2·2=5
Solving these equations, we find A= 1 and B=3
2.
Step 5: Therefore, the closed-form expression for anis:
an= 1 + 3
2·2n+1
2·2n
Question 33
Question
Consider the non-homogeneous recurrence relation:
an= 2an−1−an−2+ 2n
where the initial conditions are a0= 1 and a1= 3. Find the explicit formula
for an.
33
Solution
Step 1: Find the complementary solution to the homogeneous equation an=
2an−1−an−2. We first solve the characteristic equation r2= 2r−1 by setting
r2−2r+ 1 = 0:
(r−1)2= 0
This gives us a repeated root of r= 1, so the complementary solution is:
a(c)
n= (An +B)·1n=An +B
Step 2: Find a particular solution to the non-homogeneous equation an=
2an−1−an−2+ 2n. Since the non-homogeneous term is 2n, a good guess for a
particular solution is c·2n. Plugging this into the equation, we get:
c·2n= 2(c·2n−1)−(c·2n−2)+2n
c·2n= 2c·2n−1−c·2n−2+ 2n
c= 2c−c
2+ 1
Solving for c, we find c=−2
3.
Therefore, the particular solution is a(p)
n=−2
3·2n.
Step 3: The general form of the solution is the sum of the complementary
and particular solutions:
an=a(c)
n+a(p)
n=An +B−2
3·2n
Step 4: Apply initial conditions a0= 1 and a1= 3. Substitute n= 0 into
the equation:
a0=A·0 + B−2
3·1=1
B−2
3= 1
B=5
3
Substitute n= 1 into the equation:
a1=A·1 + 5
3−2
3·2=3
A+5
3−4
3= 3
A= 2
Therefore, the explicit formula for anis:
an= 2n+5
3−2
3·2n
34
Question 34
Question
Consider the following non-homogeneous recurrence relation:
an+1 = 2an+ 3 ·2n,where a0= 4.
Find a closed-form expression for an.
Solution
Step 1: First, we’ll find the closed-form expression of the corresponding homo-
geneous recurrence relation, which is an+1 = 2an. The characteristic equation
is r−2 = 0, which gives us r= 2. Therefore, the homogeneous solution is
a(h)
n=A·2n, where Ais a constant to be determined.
Step 2: Next, we find a particular solution a(p)
nof the non-homogeneous
recurrence relation an+1 = 2an+3·2n. Since the right-hand side is a polynomial
of degree 1 (a constant times 2n), we guess that a(p)
nis also a constant times 2n,
say b·2n. Substituting this into the recurrence relation, we have:
b·2n+1 = 2(b·2n)+3·2n
Step 3: Simplifying the above equation gives b·2 = 2b+ 3, which implies
2b= 2b+ 3 and then 3 = 0. This is a contradiction, so our guess was incorrect.
Let’s try with a linear function instead: a(p)
n=cn +d. Substituting this into
the recurrence relation gives:
c(n+ 1) + d= 2(cn +d)+3·2n
Step 4: By simplifying the above equation and equating coefficients, we find
that c= 3 and d=−3. Therefore, a(p)
n= 3n−3.
Step 5: Finally, 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=A·2n+ 3n−3.
Step 6: To find the value of the constant A, we use the initial condition
a0= 4. Substituting n= 0 into the general solution gives:
4 = A·20+ 3 ·0−3
4 = A−3
A= 7
Therefore, the closed-form expression for anis:
an= 7 ·2n+ 3n−3
35
Question 35
Question
Consider the following recurrence relation:
an=−2an−1+ 3an−2+ 2n
If the initial conditions are a0= 1 and a1= 3, find the explicit formula for
an.
Solution
To find the explicit formula for the recurrence relation, we first need to solve
the associated characteristic equation and then find a particular solution for the
non-homogeneous term 2n.
Step 1: Solve the homogeneous part of the recurrence relation by setting
an=rn:
Substitute an=rninto the homogeneous part of the recurrence relation:
rn=−2rn−1+ 3rn−2
r2=−2r+ 3
Solving the characteristic equation r2+ 2r−3 = 0 gives us roots r=−3
and r= 1. Therefore, the general solution to the homogeneous part is:
a(h)
n=c1(−3)n+c2(1)n
Step 2: Find a particular solution for the non-homogeneous term 2n:
Guess a particular solution of the form a(p)
n=Arn, where Ais a constant to
be determined. Substitute this into the original recurrence relation:
Arn=−2Arn−1+ 3Arn−2+ 2n
Arn=−2Arn−1+ 3Arn−2+ 2n
Solving for A, we get A=−2
3. Therefore, the particular solution is a(p)
n=
−2
32n.
Step 3: Combine the general solution and the particular solution:
The explicit formula for the overall solution is:
an=a(h)
n+a(p)
n=c1(−3)n+c2(1)n−2
32n
Step 4: Find the values of c1and c2using the initial conditions:
Given a0= 1 and a1= 3, we have:
c1+c2−2
3= 1
36
−3c1+c2−4
3= 3
Solving these equations simultaneously gives c1=5
9and c2=4
9.
Step 5: Final explicit formula for an:
Therefore, the explicit formula for anis:
an=5
9(−3)n+4
9+2
32n
37
