MATH 117 - ELEMENTS OF MATHEMATICS Homogeneous and non-homogeneous recurrence relations Question Bank Set 3

MATH 117 - ELEMENTS OF

MATHEMATICS - Homogeneous and

non-homogeneous recurrence relations

Question Bank - Set 3

Liberty University

Question 1

Question

Consider the non-homogeneous recurrence relation given by:

an= 4an−1−4an−2+ 2n

with initial conditions a0= 2 and a1= 4. Find the explicit formula for an.

Solution

To solve the non-homogeneous recurrence relation, we first need to find the

explicit formula for the homogeneous part and one particular solution for the

non-homogeneous part. Then, we will sum the two solutions together to get the

general solution.

Step 1: Find the solution to the homogeneous recurrence relation

The characteristic equation for the homogeneous part is obtained by setting

an=rn:

rn= 4rn−1−4rn−2.

Dividing by rn−2gives:

r2= 4r−4.

Solving the quadratic equation r2−4r+ 4 = 0 gives the repeated root r= 2.

Therefore, the solution to the homogeneous part is given by a(h)

n=c1·2n+c2·

n·2n, where c1and c2are constants to be determined.

Step 2: Find a particular solution to the non-homogeneous recur-

rence relation Assume a particular solution of the form a(p)

n=k·2n, where

kis a constant to be determined. Substitute this into the non-homogeneous

recurrence relation to get:

k·2n= 4(k·2n−1)−4(k·2n−2)+2n.

Simplifying this equation gives k=1

2. Therefore, a particular solution is a(p)

2·2n= 2n−1.

Step 3: Find the general solution The general solution is given by the

sum of the homogeneous and particular solutions:

an=a(h)

n+a(p)

n=c1·2n+c2·n·2n+ 2n−1.

Step 4: Use initial conditions to find the constants Using the initial

conditions provided:

a0= 2 ⇒c1=3

a1= 4 ⇒2 = 3 + 2c2⇒c2=−1

Therefore, the explicit formula for anis:

an=3

2·2n−1

2·n·2n+ 2n−1.

Question 2

Question

Consider the non-homogeneous recurrence relation given by an= 2an−1−an−2+

3·2nwith initial conditions a0= 1 and a1=−2. Find the explicit formula for

an.

Solution

To solve the non-homogeneous recurrence relation, we first find the general

solution to the associated homogeneous relation, and then determine a particular

solution to the non-homogeneous part.

Step 1: Find the general solution to the homogeneous relation

We start by considering the associated homogeneous recurrence relation: an=

2an−1−an−2.

The characteristic equation is r2= 2r−1, which simplifies to r2−2r+ 1 =

(r−1)2= 0. Thus, the characteristic equation has a repeated root of r= 1.

The general solution to the homogeneous relation is then a(h)

n=c1·1n+c2·

n·1n=c1+c2n.

Step 2: Find a particular solution to the non-homogeneous relation

Next, we look for a particular solution to the non-homogeneous part 3 ·2n.

Since 3 ·2nis a geometric sequence, we can try a particular solution of the form

a(p)

n=An ·2n.

Substitute a(p)

n=An ·2ninto the non-homogeneous relation:

An ·2n= 2(An −1·2n−1)−(An −2·2n−2)+3·2n

Simplify and equate coefficients to find A:

An ·2n= 2An ·2n−2A·2n+An ·2n+ 3 ·2n

An = 2An −2A+An + 3

3A= 3 =⇒A= 1

Therefore, a particular solution is a(p)

n=n·2n.

Step 3: Find the overall solution The overall solution is the sum of the

general and particular solutions:

an=a(h)

n+a(p)

n=c1+c2n+n·2n

Step 4: Use initial conditions to find c1and c2Use the initial conditions

a0= 1 and a1=−2 to solve for c1and c2:

c1= 1 c2+ 2 = −2 =⇒c2=−4

Step 5: Write the explicit formula for anTherefore, the explicit formula

for anis:

an= 1 −4n+n·2n

Question 3

Question

Consider the following recurrence relation:

an= 2an−1−3an−2+ 2 ·4n

with initial conditions a0= 2 and a1= 5. 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

r2= 2r−3

r2−2r+ 3 = 0

Step 2: Solve for the roots of the characteristic equation. Using the quadratic

formula r=−(−2)±√(−2)2−4(1)(3)

2(1) , we get r= 1 ±i√2.

Step 3: Form the general solution involving the roots found in step 2. Thus,

the general solution is of the form:

an=c1(1 + i√2)n+c2(1 −i√2)n+ (−1)nD·4n

Step 4: Use the initial conditions to solve for c1,c2, and D. Given a0= 2

and a1= 5, we have:

(c1+c2+D= 2

(1 + i√2)c1+ (1 −i√2)c2+ 4D= 5

Step 5: Solve the system of equations from step 4. Solving the above system

of equations would give us the values of c1,c2, and D.

Step 6: Substitute the values of c1,c2, and Dback into the general solution

found in step 3 to obtain the closed-form expression for an.

Question 4

Question

Let’s consider the following recurrence relation:

an= 3an−1−2an−2+ 2n

If a0= 1 and a1= 2, find a closed-form expression for an.

Solution

Step 1: First, let’s find the homogeneous solution by solving the characteristic

equation r2= 3r−2. This gives us r2−3r+2 = 0 which factors to (r−1)(r−2) =

0. So, the roots are r1= 1 and r2= 2.

Step 2: Therefore, the homogeneous solution is a(h)

n=A(1)n+B(2)n, where

Aand Bare constants.

Step 3: Now, let’s find a particular solution for the non-homogeneous part

2n. Since 2nis a geometric progression, we assume a solution of the form

a(p)

n=c·2n, where cis a constant to be determined.

Step 4: Substitute the assumed form of the particular solution into the

original recurrence relation to find c.

c·2n= 3(c·2n−1)−2(c·2n−2)+2n

c= 3c·1

2−2c·1

4+ 1

c=3

2c−1

2c+ 1

c=c+ 1

0=1

Step 5: Since we obtained 0 = 1, there is no solution for the particular part

2n.

Step 6: Therefore, the general solution is an=A(1)n+B(2)n+ 0.

Step 7: Using the initial conditions a0= 1 and a1= 2, we can find Aand

a0= 1 ⇒A(1)0+B(2)0= 1 ⇒A+B= 1

a1= 2 ⇒A(1)1+B(2)1= 2 ⇒A+ 2B= 2

Step 8: Solve the system of equations:

A+B= 1

A+ 2B= 2

Subtracting the first equation from the second, we get B= 1. Substituting

B= 1 into A+B= 1, we find A= 0.

Step 9: Therefore, the closed-form expression for anis an= 1 ·2nor simply

an= 2n.

Question 5

Question

Find a closed-form expression for the solution to the homogeneous recurrence

relation defined as an+2 = 3an+1 −2an, with initial conditions a0= 1 and

a1= 2.

Solution

To find a closed-form expression for the solution, we first need to find the char-

acteristic equation of the recurrence relation.

Step 1: Find the characteristic equation The characteristic equation

for the given homogeneous recurrence relation an+2 = 3an+1 −2anis given by:

r2= 3r−2

r2−3r+ 2 = 0

(r−1)(r−2) = 0

This gives us the roots r1= 1 and r2= 2.

Step 2: Write the general solution The general solution to the homo-

geneous recurrence relation is given by:

an=c1·1n+c2·2n

an=c1+c2·2n

Step 3: Find the values of constants Using the initial conditions a0= 1

and a1= 2:

a0=c1+c2·20=c1+c2= 1

a1=c1+c2·21=c1+ 2c2= 2

Solving these equations simultaneously, we find c1= 0 and c2= 1.

Step 4: Write the closed-form expression Substitute the values of c1

and c2back into the general solution:

an= 0 + 1 ·2n

an= 2n

Therefore, the closed-form expression for the solution to the given homoge-

neous recurrence relation is an= 2n.

Question 6

Question

Let anbe a sequence defined by the recurrence relation an= 3an−1−2an−2

with initial conditions a0= 1 and a1= 2. Find a formula for an.

Solution

Step 1: Find the characteristic equation by assuming an=rn:

rn= 3rn−1−2rn−2

Dividing by rn−2gives:

r2= 3r−2 =⇒r2−3r+ 2 = 0

Step 2: Solve the characteristic equation to find the roots r1and r2:

(r−2)(r−1) = 0 =⇒r1= 2, r2= 1

Step 3: The general solution is then given by an=c1(2)n+c2(1)n.

Step 4: Use the initial conditions a0= 1 and a1= 2 to find c1and c2:

a0=c1+c2= 1

a1= 2c1+c2= 2

Step 5: Solving this system of equations gives c1= 1 and c2= 0.

Step 6: Substituting these coefficients back into the general solution gives

the formula for an:

an= 1(2)n+ 0(1)n= 2n

Therefore, the formula for anis an= 2n.

Question 7

Question

Consider the recurrence relation: an= 2an−1+ 3an−2where a0= 1 and a1= 2.

Find the explicit formula for the nth term of the sequence.

Solution

To find the explicit formula for the nth term of the sequence, we first need to find

the characteristic equation for the given recurrence relation. The characteristic

equation for a homogeneous linear recurrence relation of the form an=c1an−1+

c2an−2is given by r2−c1r−c2= 0.

Step 1: Find the characteristic equation The recurrence relation is

an= 2an−1+ 3an−2. Therefore, the characteristic equation is r2−2r−3 = 0.

Step 2: Solve the characteristic equation To solve the characteristic

equation r2−2r−3 = 0, we factor it as (r−3)(r+ 1) = 0. Thus, the roots are

r= 3 and r=−1.

Step 3: Write the general solution The general solution for the homoge-

neous recurrence relation an= 2an−1+3an−2is given by an=c1(3)n+c2(−1)n,

where c1and c2are constants to be determined using the initial conditions.

Step 4: Use initial conditions to find c1and c2Given initial conditions

a0= 1 and a1= 2, we have the following system of equations:

c1+c2= 1

3c1−c2= 2

Solving this system, we find c1=1

2and c2=1

Step 5: Write the explicit formula Substitute c1=1

2and c2=1

2into the

general solution to obtain the explicit formula for the nth term of the sequence:

an=1

2(3)n+1

2(−1)n

Question 8

Question

Consider the following recurrence relation:

an= 2an−1−2an−2+ 2n

Find the general solution to the given recurrence relation.

Solution

Step 1: Find the characteristic equation by assuming the solution has the form

an=rn:

rn= 2rn−1−2rn−2

Step 2: Divide the equation by rn−2:

r2= 2r−2

Step 3: Rewrite the equation as a quadratic equation:

r2−2r+ 2 = 0

Step 4: Solve the quadratic equation for rusing the quadratic formula:

r=2±p(−2)2−4(1)(2)

2(1) =2±√4−8

2=2±2i

2= 1 ±i

So the general solution to the homogeneous part of the recurrence relation

is:

an=c1(1 + i)n+c2(1 −i)n

Step 5: Find a particular solution to the non-homogeneous part of the recur-

rence relation: Let’s guess a particular solution of the form an=An2n, where

Ais a constant to be determined.

Substitute an=An2ninto the original recurrence relation:

An2n= 2(A(n−1)2n−1)−2(A(n−2)2n−2)+2n

Step 6: Simplify the equation:

An2n= 2An2n−2An2n+ 2n

An2n= 2n

Step 7: Solve for A:

A=2n

2n= 1

Step 8: So the particular solution is an=n2n.

Step 9: The general solution to the entire recurrence relation is the sum of

the homogeneous and particular solutions:

an=c1(1 + i)n+c2(1 −i)n+n2n

Question 9

Question

Consider the non-homogeneous recurrence relation given by an= 3an−1−

2an−2+ 2n. If a0= 1 and a1= 4, find a formula for anfor n≥2.

Solution

To solve the non-homogeneous recurrence relation, we will first find the general

solution to the associated homogeneous recurrence relation, and then determine

a particular solution for the non-homogeneous part.

Step 1: Find the general solution The associated homogeneous recur-

rence relation is an= 3an−1−2an−2. Let’s start by finding the characteristic

equation:

r2= 3r−2

r2−3r+ 2 = 0

(r−1)(r−2) = 0

r= 1,2

Therefore, the general solution to the homogeneous part is:

an=c1(1)n+c2(2)n

Step 2: Find a particular solution To find a particular solution to the

non-homogeneous part, let’s try a solution of the form an=k(2)n. Substitute

this into the original relation:

k(2)n= 3k(2)n−1−2k(2)n−2+ 2n

k= 3k(1/2) −2k(1/4) + 2

k=3

2k−1

2k+ 2

2k−1

2k= 2

k= 4

Therefore, a particular solution is an= 4(2)n.

Step 3: Find the full solution Combining the general solution and the

particular solution, we have:

an=c1+ 2c2+ 4(2)n

Step 4: Find the values of c1and c2Using the initial conditions a0= 1

and a1= 4, we can find c1and c2:

c1+ 2c2+ 4 = 1

c1+ 4c2+ 8 = 4

Solving these equations simultaneously, we find c1= 5 and c2=−4.

Step 5: Write the final formula Therefore, the formula for anfor n≥2

is:

an= 5 + (−4)(2)n+ 4(2)n

Question 10

Question

Consider the non-homogeneous recurrence relation:

an= 2an−1−an−2+ 3n.

Given that a0= 1 and a1= 3, find an expression for anin terms of n.

Solution

We first solve the corresponding homogeneous recurrence relation: an= 2an−1−

an−2.Step 1: Find the characteristic equation by assuming an=rn:

rn= 2rn−1−rn−2

r2= 2r−1

r2−2r+ 1 = 0

(r−1)2= 0

r= 1 (double root)

Step 2: The general solution to the homogeneous part is given by:

a(h)

n=c1·1n+c2·n·1n=c1+c2n.

Now, we find a particular solution a(p)

nto the non-homogeneous part of the

recurrence relation: an= 2an−1−an−2+ 3n.Since the non-homogeneity is 3n,

we try a particular solution of the form A·3n.Step 3: Substitute a(p)

n=A·3n

into the recurrence relation:

A·3n= 2(A·3n−1)−(A·3n−2)+3n

A·3n= 2A·3n−2A·3n−1+ 3n

0 = −A·3n+ 2A·3n−1

0 = −A+ 2A·3−1=⇒A=1

Therefore, a(p)

n=1

2·3nis a particular solution.

Step 4: The general solution to the entire recurrence relation is the sum of

the solutions to the homogeneous and non-homogeneous parts:

an=a(h)

n+a(p)

n=c1+c2n+1

2·3n.

Step 5: Using the initial conditions a0= 1 and a1= 3, we can find c1and

c2:

a0=c1+1

2= 1 =⇒c1=1

a1=c1+c2+3

2= 3 =⇒c2=5

Step 6: Finally, the expression for anin terms of nis:

an=1

2+5

2n+1

2·3n.

Question 11

Question

Consider the non-homogeneous recurrence relation given by an= 2an−1−an−2+

2nwith initial conditions a0= 0 and a1= 1. Find a closed-form expression for

an.

Solution

To solve the non-homogeneous recurrence relation, we need to find both the

particular solution and the complementary function.

Step 1: Find the complementary function

First, we solve the associated homogeneous recurrence relation ah

n= 2ah

n−1−

n−2. Assume ah

n=rn:

rn= 2rn−1−rn−2=⇒r2−2r+ 1 = 0 =⇒(r−1)2= 0

Thus, r= 1 is a repeated root. The complementary function is then given by

n=c1·1n+c2·n·1n=c1+c2n, where c1and c2are constants.

Step 2: Find the particular solution

Next, we find a particular solution for the non-homogeneous recurrence relation.

Since the term on the right-hand side is of the form 2n, we assume ap

n=A·2n:

A·2n= 2(A·2n−1)−(A·2n−2)+2n

Solving for A, we get A=−1. Therefore, the particular solution is ap

n=−2n.

Step 3: Combine the solutions

The general solution is the sum of the complementary function and the partic-

ular solution:

an=ah

n+ap

n=c1+c2n−2n

Step 4: Use initial conditions to determine c1and c2

Using the initial conditions a0= 0 and a1= 1:

(c1−1 = 0

c1+c2−2=1

Solving this system of equations, we find c1= 1 and c2= 2.

Step 5: Final closed-form solution

Therefore, the explicit formula for anis:

an= 1 + 2n−2n

Question 12

Question

Let (an) be the sequence defined by the recurrence relation an= 2an−1−

2an−2+ 2nfor n≥2 with initial conditions a0= 0 and a1= 4. Find a

closed-form expression for an.

Solution

Step 1: Characteristic equation. We first solve the characteristic equation r2−

2r+ 2 = 0 to find the homogeneous solution. The roots of the characteristic

equation are given by

r=2±p(−2)2−4·1·2

2·1= 1 ±i,

where iis the imaginary unit. Thus, the general solution to the homogeneous

recurrence relation is

a(h)

n=c1·1n·cos(n·ln(2)) + c2·1n·sin(n·ln(2)),

where c1and c2are constants to be determined.

Step 2: Particular solution. We now find a particular solution to the non-

homogeneous recurrence relation. Since 2nis a polynomial of degree 1, we try

a particular solution of the form a(p)

n=An ·2n. Substituting this form into the

original recurrence relation, we get

An ·2n= 2(An −1·2n−1)−2(An −2·2n−2)+2n.

This simplifies to A=1

2. Therefore, a particular solution is a(p)

n=n

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(h)

n+a(p)

n=c1·1n·cos(n·ln(2)) + c2·1n·sin(n·ln(2)) + n

2·2n.

Step 4: Applying initial conditions. Using the initial conditions a0= 0 and

a1= 4, we find c1=−3

2and c2= 0. Therefore, the closed-form expression for

anis

an=−3

2·cos(n·ln(2)) + n

2·2n.

Question 13

Question

Consider the non-homogeneous recurrence relation given by an= 2an−1−an−2+

2n+ 1, with initial conditions a0= 1 and a1= 2. Find the explicit formula for

an.

Solution

Step 1: First, find the homogeneous solution by solving the characteristic equa-

tion x2= 2x−1.

x2−2x+ 1 = 0

(x−1)2= 0

x= 1 (double root)

Step 2: Therefore, the homogeneous solution is given by a(h)

n=c1·1n+c2·

n·1n=c1+c2n.

Step 3: Next, find a particular solution a(p)

nby assuming it has the form

a(p)

n=An2+Bn +C. Substitute this into the original non-homogeneous recur-

rence relation.

Step 4: Substituting a(p)

n=An2+Bn+Cinto the original non-homogeneous

relation, we get:

An2+Bn +C= 2(An2+B(n−1) + C)−(An(n−1) + B(n−2) + C) + 2n+ 1

Step 5: Simplifying the above equation, we get:

An2+Bn +C= 2An2+ 2Bn + 2C−An2+An −Bn +B+ 2n+ 1

Step 6: Matching coefficients for n2:A= 2A−A, so A=−1.

Step 7: Matching coefficients for n:B= 2B+A−B=B−1, so B= 1.

Step 8: Matching constants: C= 2C+ 1, so C=−1.

Step 9: Therefore, the particular solution is a(p)

n=−n2+n−1.

Step 10: The general solution is given by an=a(h)

n+a(p)

n=c1+c2n−n2+

n−1.

Step 11: Using the initial conditions a0= 1 and a1= 2 to solve for c1and

c2:

a0=c1−1 = 1 =⇒c1= 2

a1=c1+c2−1 = 2 =⇒2 + c2−1 = 2 =⇒c2= 1

Step 12: Thus, the explicit formula for anis an= 2 + n−n2.

Question 14

Question

Let anbe defined recursively by the recurrence relation:

an= 3an−1−2an−2+ 2n

with initial conditions a0= 1 and a1= 2. Find a closed-form expression for an.

Solution

Step 1: Finding the homogeneous solution We start by setting the right-hand

side of the given recurrence relation to 0 to find the homogeneous solution:

an= 3an−1−2an−2

Step 2: Characteristic equation To find the characteristic polynomial, we

substitute an=rninto the homogeneous equation:

rn= 3rn−1−2rn−2

r2−3r+ 2 = 0

(r−1)(r−2) = 0

So, the roots of the characteristic equation are r1= 1 and r2= 2.

Step 3: General homogeneous solution The general solution of the homoge-

neous recurrence relation is given by:

an=c1(1n) + c2(2n)

an=c1+c2(2n)

Step 4: Finding the particular solution Since the non-homogeneous term is

2n, we assume a particular solution of the form A(2n):

A(2n)=3A(2n−1)−2A(2n−2)+2n

Step 5: Solving for A Substitute 2ninto the above equation and simplify:

A(2n)=3A(2n−1)−2A(2n−2)+2n

A= 3A−2A+ 2

A= 2

Step 6: Complete solution The complete solution is the sum of the homoge-

neous and particular solutions:

an=c1+c2(2n)+2n

Step 7: Using initial conditions We use the initial conditions a0= 1 and

a1= 2 to find c1and c2:

a0=c1+c2= 1

a1=c1+ 2c2+ 2 = 2

Solving the above system of equations, we find c1= 0 and c2= 1.

Step 8: Final closed-form expression Therefore, the closed-form expression

for anis:

an= 2n+ 2(2n) = 3(2n)

an= 3 ×2n

Question 15

Question

Consider the non-homogeneous recurrence relation defined by an= 3an−1−

2an−2+ 2nwith initial conditions a0= 4 and a1= 6. Find a closed-form

expression for an.

Solution

Step 1: 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 factors as r2−3r+ 2 =

(r−1)(r−2) = 0. Therefore, the characteristic roots are r1= 1 and r2= 2,

and the general solution to the homogeneous recurrence relation is

a(h)

n=c1·1n+c2·2n=c1+c2·2n.

Step 2: To find a particular solution a(p)

nto the non-homogeneous recurrence

relation, we try the form a(p)

n=A·2n, where Ais a constant to be determined.

Substituting this into the recurrence relation gives

A·2n= 3(A·2n−1)−2(A·2n−2)+2n.

Step 3: Simplifying, we get

A·2n= 3A·2n−1−2A·2n−2+ 2n.

Step 4: Divide both sides by 2nto obtain

A=3A

2−2A

4+ 1.

Step 5: Solving for Ayields A= 4. Thus, the particular solution is a(p)

4·2n.

Step 6: The general solution to the non-homogeneous recurrence relation

is the sum of the general solution to the homogeneous part and the particular

solution:

an=a(h)

n+a(p)

n=c1+c2·2n+ 4 ·2n.

Step 7: Applying the initial conditions a0= 4 and a1= 6 yields the equations

c1+4 = 4 and c1+2c2+8 = 6. Solving these equations gives c1= 0 and c2=−2.

Step 8: Therefore, the closed-form expression for anis

an=−2·2n+ 4 ·2n= 2n+2.

Question 16

Question

Consider the following recurrence relation:

an= 2an−1−an−2+ 2n

where a0= 1 and a1= 2. Determine a closed-form expression for an.

Solution

Step 1: First, let’s find the characteristic equation of the homogeneous part of

the recurrence relation:

a(h)

n= 2an−1−an−2

The characteristic equation is given by r2= 2r−1, which simplifies to r2−2r+

1=(r−1)2= 0. Thus, the characteristic root is r= 1.

Step 2: Therefore, the general solution to the homogeneous part is a(h)

c1·1n+c2·n·1n=c1+c2n.

Step 3: Now, we need to find a particular solution for the non-homogeneous

part of the recurrence relation:

a(p)

n= 2n

Since the non-homogeneous part is a constant times 2n, we can assume a par-

ticular solution of the form a(p)

n=An2n. Let’s substitute this into the original

recurrence relation:

An2n= 2(An2(n−1))−(An2(n−2))+2n

An2n= 2An2n−1−An2n−2+ 2n

An = 2An −An + 1

An =An + 1

0=1

This leads to a contradiction. Therefore, we need to multiply by n:

a(p)

n=An2·2n

A(n2−n)2n= 2(A(n−1)2·2n−1)−A(n−2)2·2n−2+ 2n

A(n2−n)=2A(n−1)2−A(n−2)2+ 1

By comparing coefficients, we find A= 1.

Step 4: Thus, the particular solution is a(p)

n=n2·2n.

Step 5: Finally, the general solution is the sum of the homogeneous and

particular solutions:

an=a(h)

n+a(p)

n=c1+c2n+n2·2n

Step 6: Using the initial conditions a0= 1 and a1= 2, we can solve for c1

and c2. Substituting these values into the general solution gives the closed-form

expression for an.

Question 17

Question

Find a closed-form expression for the solution to the following non-homogeneous

recurrence relation:

an= 3an−1−an−2+ 2n

given that a0= 1 and a1= 2.

Solution

To solve this non-homogeneous recurrence relation, we first find the general

solution to the associated homogeneous recurrence relation. Then, we find a

particular solution for the non-homogeneous term, and combine both solutions

to form the general solution.

Step 1: Find the general solution to the homogeneous recurrence

relation Consider the homogeneous part of the recurrence relation:

an= 3an−1−an−2

Assume a solution of the form an=rn. Substituting this into the equation

gives us:

rn= 3rn−1−rn−2

Dividing by rn−2, we get the characteristic equation:

r2= 3r−1

r2−3r+ 1 = 0

Solving this quadratic equation gives us the roots r1and r2.

Step 2: Find the particular solution for the non-homogeneous term

To find the particular solution, we guess a solution of the form an=Arn, where

Ais a constant to be determined.

Substitute an=Arninto the non-homogeneous part of the recurrence rela-

tion:

Arn= 3Arn−1−Arn−2+ 2n

Dividing by rn−2, we get:

r2−3r+ 1 = 2n

Determine Aby matching the terms.

Step 3: Combine the solutions The general solution anis the sum of

the general solution to the homogeneous part and the particular solution:

an=a(h)

n+a(p)

Substitute the initial conditions a0= 1 and a1= 2 to find the values of A

and any constants from the homogeneous part if necessary. Now, combine the

two solutions to find the closed-form expression for an.

Question 18

Question

Consider the non-homogeneous recurrence relation defined by an= 2an−1−

2an−2+ 2nfor n≥2, with initial conditions a0= 1 and a1= 3. Find a

closed-form expression for an.

Solution

We will first find the general solution to the associated homogeneous recurrence

relation an= 2an−1−2an−2before finding a particular solution for the non-

homogeneous term 2n.

Step 1: Find the characteristic equation For the homogeneous recur-

rence relation an= 2an−1−2an−2, we assume a solution of the form an=rn.

Substituting, we get

rn= 2rn−1−2rn−2.

Dividing by rn−2gives the characteristic equation r2= 2r−2. Simplifying, we

get r2−2r+ 2 = 0.

Step 2: Find the roots of the characteristic equation Solving the

characteristic equation r2−2r+ 2 = 0, we get

r=2±p(−2)2−4·1·2

2·1= 1 ±i.

Step 3: Find the general solution to the homogeneous part The

general solution to the associated homogeneous recurrence relation is

a(h)

n=c1(1 + i)n+c2(1 −i)n,

where c1and c2are constants determined by the initial conditions.

Step 4: Find a particular solution to the non-homogeneous term

Since 2nis a geometric series, we guess that a particular solution is of the form

a(p)

n=Crn, where Cis a constant to be determined. Substitute this into the

non-homogeneous recurrence relation to solve for C:

Crn= 2(Crn−1)−2(Crn−2)+2n.

This simplifies to C=−22, so a(p)

n=−2n+2.

Step 5: Find the general solution to the overall equation The general

solution to the non-homogeneous recurrence relation is the sum of the general

solution of the homogeneous part and the particular solution:

an=a(h)

n+a(p)

n=c1(1 + i)n+c2(1 −i)n−2n+2.

Step 6: Apply initial conditions to solve for constants Using the

initial conditions a0= 1 and a1= 3, we can solve for c1and c2.

a0= 1 = c1+c2−16,

a1= 3 = (1 + i)c1+ (1 −i)c2−32.

Solving these equations gives c1=7

2and c2=17

Step 7: Final expression for anSubstitute the values of c1and c2back

into the general solution to get the closed-form expression for an:

an=7

2(1 + i)n+17

2(1 −i)n−2n+2.

Question 19

Question

Let {an}be a sequence defined by the recurrence relation

an= 2an−1−3an−2+ 2n,

with initial conditions a0= 1 and a1=−1. Find a closed-form formula for an.

Solution

To find a closed-form formula for an, we first need to find the characteristic

equation associated with the homogeneous part of the recurrence relation. This

equation is given by xn= 2xn−1−3xn−2. Dividing by xn−2gives x2= 2x−3,

which simplifies to x2−2x+ 3 = 0.

Step 1: Find the roots of the characteristic equation The roots of

the characteristic equation x2−2x+ 3 = 0 can be found using the quadratic

formula:

x=−(−2) ±p(−2)2−4·1·3

2·1=2±√4−12

2= 1 ±i√2.

Therefore, the roots are complex: r1= 1 + i√2 and r2= 1 −i√2.

Step 2: Write the general solution for the homogeneous part The

general solution for the homogeneous part of the recurrence relation is given by

a(h)

n=c1(1 + i√2)n+c2(1 −i√2)n.

Step 3: Find a particular solution for the non-homogeneous part

Let’s assume a particular solution of the form a(p)

n=A2n, where Ais a constant

to be determined. Substitute this into the original recurrence relation:

A2n= 2(A2n−1)−3(A2n−2)+2n.

Simplifying this equation yields A=−1. Thus, a particular solution is

a(p)

n=−2n.

Step 4: Write the general solution for the entire recurrence rela-

tion The general solution for the entire recurrence relation is the sum of the

solutions of the homogeneous and non-homogeneous parts:

an=a(h)

n+a(p)

n=c1(1 + i√2)n+c2(1 −i√2)n−2n.

Step 5: Apply the initial conditions to find the values of c1and

c2Using the initial conditions a0= 1 and a1=−1, we can solve for c1and

c2. Substituting n= 0 and n= 1 into the general solution gives the system of

equations:

(c1+c2−1=0

c1(1 + i√2) + c2(1 −i√2) −2 = −1.

Solving this system of equations leads to c1=9

8−3

8i√2 and c2=9

8+3

8i√2.

Step 6: Write the closed-form formula for anFinally, substituting the

values of c1and c2into the general solution gives the closed-form formula for

an:

an=9

8−3

8i√2(1 + i√2)n+9

8+3

8i√2(1 −i√2)n−2n.

Question 20

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

Dividing by rn−2, we get:

r2= 3r−2 =⇒r2−3r+ 2 = 0

This gives us the characteristic equation r2−3r+ 2 = 0, which factors to

(r−1)(r−2) = 0. Therefore, the roots are r1= 1 and r2= 2.

Step 2: Write the general solution based on the roots:

an=c1·1n+c2·2n

Simplify to get:

an=c1+c2·2n

Step 3: Use the initial conditions to solve for c1and c2: Given a0= 1, we

have:

1 = c1+c2·20=c1+c2

Given a1= 2, we have:

2 = c1+c2·21=c1+ 2c2

Solving these two equations simultaneously, we find c1=−2 and c2= 3.

Therefore, the closed-form expression for anis:

an=−2+3·2n

Question 21

Question

Let anbe a sequence defined by the recurrence relation an+2 = 5an+1 −6anfor

all integers n≥0 with 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

associated with the given recurrence relation an+2 = 5an+1 −6an.

Step 1: Write down the characteristic equation The characteristic

equation corresponding to an+2 = 5an+1 −6anis r2= 5r−6.

Step 2: Solve the characteristic equation We can rewrite the charac-

teristic equation as r2−5r+ 6 = 0. This factors as (r−2)(r−3) = 0, so the

roots are r1= 2 and r2= 3.

Step 3: Find the general solution Since the roots are distinct, the

general solution to the recurrence relation is of the form an=c1·2n+c2·3n.

Step 4: Use initial conditions to find c1and c2Given a0= 2 and

a1= 5, we can substitute these values into the general solution:

a0=c1·20+c2·30=c1+c2= 2

a1=c1·21+c2·31= 2c1+ 3c2= 5

Solving this system of equations, we get c1= 1 and c2= 1.

Step 5: Write the final formula for anTherefore, the formula for anis

an= 2n+ 3nfor all integers n≥0.

Question 22

Question

Consider the following recurrence relation:

an= 2an−1−2an−2+ 2n, n ≥2

with initial conditions a0= 0 and a1= 3. Find a closed-form expression for an.

Solution

To solve this recurrence relation, we first solve the associated homogeneous

recurrence relation:

a(h)

n= 2a(h)

n−1−2a(h)

n−2

Step 1: Find the characteristic equation Let a(h)

n=rn. Substitute

a(h)

n=rninto the homogeneous recurrence relation to get:

rn= 2rn−1−2rn−2

Divide by rn−2to simplify:

r2= 2r−2

This gives us the characteristic equation:

r2−2r+ 2 = 0

Step 2: Find the roots of the characteristic equation Using the

quadratic formula r=−(−2)±√(−2)2−4(1)(2)

2(1) , we get:

r=2±√4−8

2=2±√−4

2= 1 ±i

Step 3: Find the general solution of the homogeneous recurrence

relation The general solution is:

a(h)

n=c1(1 + i)n+c2(1 −i)n

Step 4: Find the particular solution of the non-homogeneous re-

currence relation Let’s assume a particular solution of the form a(p)

n=An2n.

Substitute a(p)

n=An2ninto the original recurrence relation:

An2n= 2(A(n−1)2(n−1))−2(A(n−2)2(n−2))+2n

An2n= 2A(n−1)2(n−1) −2A(n−2)2(n−2) + 2n

An = 2A(n−1) −2A(n−2) + 1

Step 5: Solve for the particular solution coefficients By comparing

coefficients we get:

A= 2A=⇒A= 0.5

Step 6: Find the general solution of the non-homogeneous recur-

rence relation The general solution is:

an=a(h)

n+a(p)

n=c1(1 + i)n+c2(1 −i)n+ 0.5n2n

Step 7: Use the initial conditions to find the values of c1and c2

Using the initial conditions a0= 0 and a1= 3:

c1+c2= 0

c1(1 + i) + c2(1 −i) + 1 = 3

Solving these equations, we get c1=3−3i

2and c2=3+3i

Step 8: Final closed-form expression for anSubstitute c1and c2back

into the general solution:

an=3−3i

2(1 + i)n+3+3i

2(1 −i)n+ 0.5n2n

Question 23

Question

Consider the following non-homogeneous recurrence relation:

an= 2an−1−an−2+n2+n+ 1

where a0= 1 and a1= 2. Find a closed-form expression for an.

Solution

Step 1: First, we find the closed-form expression for the homogeneous part of

the recurrence relation by setting the right-hand side equal to zero. This gives

us the characteristic equation:

r2−2r+ 1 = 0

(r−1)2= 0

r= 1 (double root)

So, the homogeneous solution is a(h)

n=c1·1n+c2·n·1n=c1+c2n.

Step 2: Next, we need to find a particular solution for the non-homogeneous

part of the recurrence relation. We notice that the particular solution could be

a quadratic function in ndue to the terms n2,n, and the constant 1. Let’s

assume a particular solution of the form a(p)

n=An2+Bn +C.

Step 3: Substituting a(p)

nback into the original recurrence relation:

An2+Bn +C= 2(An2+B(n−1)+C)−(An(n−1)+B(n−1) +C)+ n2+n+1

Step 4: Simplifying and equating coefficients of like terms, we get the fol-

lowing system of equations:

A= 2A−A(coefficient of n2)

B= 2B−B+ 2A(coefficient of n)

C= 2C−C+A(coefficient of 1)

Step 5: Solving the system of equations, we find A=1

2,B=−1, and C=3

Therefore, the particular solution is a(p)

n=1

2n2−n+3

Step 6: Combining the homogeneous and particular solutions, we have:

an=a(h)

n+a(p)

n=c1+c2n+1

2n2−n+3

Step 7: Applying the initial conditions a0= 1 and a1= 2 to solve for c1and

c2:

c1= 1.5 and c2= 1

Therefore, the closed-form expression for anis:

an= 1.5 + n+1

2n2−n+3

2=1

2n2+ 0.5n+ 3

Question 24

Question

Consider the non-homogeneous recurrence relation an= 3an−1−2an−2+ 2n,

where a0= 1 and a1= 2. Find a closed-form expression for an.

Solution

To solve this non-homogeneous recurrence relation, we need to find both the

general solution to the homogeneous part and a particular solution to the non-

homogeneous part.

Step 1: Find the homogeneous solution We first solve the correspond-

ing homogeneous recurrence relation an= 3an−1−2an−2by assuming an=rn

and substituting it into our recurrence relation:

rn= 3rn−1−2rn−2

Dividing by rn−2gives us the characteristic equation:

r2= 3r−2

This factors to (r−2)(r−1) = 0, so r= 2 and r= 1 are the roots. Therefore,

the general solution to the homogeneous part is:

a(h)

n=c1(2)n+c2(1)n=c1(2)n+c2

Step 2: Find the particular solution Now we look for a particular

solution to the non-homogeneous part. Since the non-homogeneous term 2nis a

geometric progression, we can try a particular solution of the form a(p)

n=A2n.

Substituting this into the original recurrence relation gives:

A2n= 3A2n−1−2A2n−2+ 2n

Simplifying, we get:

A= 3A−2A+ 1

A=A+ 1

This implies A= 1. Therefore, a particular solution is a(p)

n= 2n.

Step 3: Find the general solution The general solution to the non-

homogeneous recurrence relation is the sum of the homogeneous and particular

solutions:

an=a(h)

n+a(p)

n=c1(2)n+c2+ 2n

Step 4: Find the constants using initial conditions Using the initial

conditions a0= 1 and a1= 2, we can solve for c1and c2:

a0=c1(2)0+c2+ 20=c1+c2= 1

a1=c1(2)1+c2+ 21= 2c1+c2+ 2 = 2

Solving these equations simultaneously, we find c1=−1 and c2= 2.

Therefore, the closed-form expression for anis:

an=−2n+ 2 + 2n= 2 + (−1)n

Question 25

Question

Consider the non-homogeneous recurrence relation given by an= 2an−1−

3an−2+ 2nwith initial conditions a0= 1 and a1= 4. Find a closed-form

expression for an.

Solution

We will first solve the homogeneous part of the recurrence relation an= 2an−1−

3an−2, and then find a particular solution to incorporate the non-homogeneous

part 2n.

Step 1: Solve the homogeneous part Let a(h)

nbe the solution to the

homogeneous part of the recurrence relation. The characteristic equation is

given by:

r2= 2r−3

r2−2r+ 3 = 0

Solving this quadratic equation, we find that the roots are complex conju-

gates:

r= 1 ±i√2

Therefore, the solution to the homogeneous part is:

a(h)

n=c1(1 + i√2)n+c2(1 −i√2)n

Step 2: Find a particular solution We see that the non-homogeneous

part 2ncan be represented by a geometric progression. A particular solution

for the non-homogeneous part can be written as:

a(p)

n=A·2n

Step 3: Substitute and find the constants Substitute an=a(h)

n+a(p)

into the original recurrence relation:

c1(1+i√2)n+c2(1−i√2)n+A·2n= 2[c1(1+i√2)n−1+c2(1−i√2)n−1]−3[c1(1+i√2)n−2+c2(1−i√2)n−2]+2n

Next, substitute n= 0 and n= 1 to find values of c1,c2, and A.

Step 4: Final solution After finding the values of c1,c2, and A, the

closed-form expression for anis:

an=a(h)

n+a(p)

Question 26

Question

Consider the non-homogeneous recurrence relation defined by:

an= 2an−1+ 3n

with the initial condition a0= 4. Find a closed-form expression for anin

terms of n.

Solution

Step 1: Solve the associated homogeneous recurrence relation an= 2an−1to find

the complementary function CF . To solve the homogeneous recurrence relation,

we assume the form an=rnand substitute it into the equation an= 2an−1:

rn= 2rn−1

Dividing both sides by rn−1gives:

r= 2

So, the complementary function CF is an=A·2n, where Ais a constant to be

determined.

Step 2: Find a particular solution pnfor the non-homogeneous recurrence

relation. To find a particular solution, we guess that pnhas the form pn=B·3n,

where Bis a constant to be determined. Substituting this into the equation

an= 2an−1+ 3ngives:

B·3n= 2B·3n−1+ 3n

Solving for Bwe get B=1

Step 3: The general solution anis the sum of the complementary function

CF and the particular solution pn. Therefore, the general solution is:

an=CF +pn=A·2n+1

3·3n

Given that the initial condition is a0= 4, we can find the value of A:

4 = A·20+1

3·30

4 = A+1

A=11

Hence, the closed-form expression for anin terms of nis:

an=11

3·2n+1

3·3n

Question 27

Question

Consider the following recurrence relation:

an+2 = 2an+1 −15an+ 2n

with initial conditions a0= 1 and a1= 4. Find an explicit formula for an.

Solution

To find an explicit formula for an, we first need to solve the homogeneous part

of the recurrence relation. Then, we will find a particular solution for the non-

homogeneous part and combine the two solutions.

Step 1: Solve the homogeneous part: The homogeneous part of the

recurrence relation is an+2 = 2an+1 −15an.

Let an=rnbe the assumed form of the solution. Substituting this into the

homogeneous part, we get:

rn+2 = 2rn+1 −15rn

r2−2r−15 = 0

Factoring the quadratic equation, we have:

(r−5)(r+ 3) = 0

So, the roots are r= 5 and r=−3.

Therefore, the general solution to the homogeneous part is:

a(h)

n=A·5n+B·(−3)n

Step 2: Find a particular solution for the non-homogeneous part:

For the non-homogeneous part 2n, we will assume a solution of the form a(p)

c·2n.

Substituting into the non-homogeneous part, we get:

c·2n+2 = 2(c·2n+1)−15(c·2n)+2n

4c·2n= 2c·2·2n−15c·2n+ 2n

4c= 4c−15c+ 1

c=1

So, a particular solution is a(p)

n=1

4·2n= 2n−2.

Step 3: Combine the solutions: The general solution to the original

recurrence relation is the sum of the homogeneous and particular solutions:

an=a(h)

n+a(p)

n=A·5n+B·(−3)n+ 2n−2

Step 4: Use initial conditions to find A and B: Using the initial

conditions a0= 1 and a1= 4:

a0=A+B+1

4= 1

a1= 5A−3B+ 2 = 4

Solving these equations, we find A=17

12 and B=−1

Therefore, the explicit formula for anis:

an=17

12 ·5n−1

3·(−3)n+ 2n−2

Question 28

Question

Let ansatisfy the recurrence relation an= 3an−1−2an−2+ 2nfor n≥2, where

a0= 1 and a1= 2. Find a formula for an.

Solution

Step 1: First, we solve the homogeneous part of the recurrence relation an=

3an−1−2an−2. This corresponds to the characteristic equation r2= 3r−2,

which simplifies to r2−3r+ 2 = 0. This factors as (r−1)(r−2) = 0, so the

characteristic roots are r= 1 and r= 2.

Step 2: Thus, the general solution to the homogeneous part of the recurrence

relation is a(h)

n=A·1n+B·2n, where Aand Bare constants to be determined.

Step 3: Now, we look for a particular solution to the non-homogeneous part

of the recurrence relation an= 2n. Since our non-homogeneous term is of the

form c·2n, a possible form for the particular solution is a(p)

n=C·2n, where C

is a constant to be determined.

Step 4: Substituting a(h)

nand a(p)

nback into the original recurrence relation,

we have: A+ 2B+C·2n= 3(A+ 2B)−2(A·1n−2+B·2n−2)+2n

Step 5: Equating the coefficients of 2n, we get C= 1.

Step 6: Substituting C= 1 back into the particular solution, we have a(p)

2n.

Step 7: Combining the homogeneous and particular solutions, we have the

general solution an=A+ 2B+ 2n.

Step 8: Finally, using the initial conditions a0= 1 and a1= 2, we find A= 1

and B= 0.

Therefore, the formula for anis an= 1 + 2n.

Question 29

Question

Consider the following recurrence relation:

an= 2an−1−an−2+ 2n

Determine the particular solution to the non-homogeneous recurrence rela-

tion given that a0= 1 and a1= 3.

Solution

To solve the non-homogeneous recurrence relation, we need to find the particular

solution a(p)

nthat satisfies the given equation.

Step 1: Find the homogeneous solution Let’s first find the homo-

geneous solution to the recurrence relation an= 2an−1−an−2by assuming

an=rn. Substituting this into the homogeneous part of the recurrence relation

gives:

rn= 2rn−1−rn−2

Dividing by rn−2, we get:

r2= 2r−1

r2−2r+ 1 = 0

(r−1)2= 0

r= 1

Therefore, the homogeneous solution is a(h)

n=c1·1n+c2·n1n=c1+c2n.

Step 2: Find the particular solution We need to find a particular solu-

tion that satisfies an= 2an−1−an−2+ 2n. Since the non-homogeneous part is

2n, we guess that a particular solution is of the form a(p)

n=An2n.

Substitute a(p)

n=An2ninto the recurrence relation:

An2n= 2(A(n−1)2n−1)−A(n−2)2n−2+ 2n

Simplify:

An2n= 2An2n−2A2n−1n+ 2n

Match coefficients of 2nto get A=−1.

So, the particular solution is a(p)

n=−2n.

Step 3: Find the general solution The general solution is the sum of

the homogeneous solution and the particular solution:

an=a(h)

n+a(p)

n=c1+c2n−2n

Step 4: Find c1 and c2 using initial conditions Given that a0= 1 and

a1= 3, we can use these initial conditions to find c1and c2:

From a0= 1:

c1−20= 1

c1−1 = 1

c1= 2

From a1= 3:

c1+c2−21= 3

2 + c2−2=3

c2= 3

Therefore, the particular solution to the non-homogeneous recurrence rela-

tion is an= 2 + 3n−2n.

Question 30

Question

Consider the following recurrence relation: an= 3an−1−2an−2+ 2nwhere

a0= 1 and a1= 2. Find the explicit formula for an.

Solution

Given recurrence relation: an= 3an−1−2an−2+ 2nwith initial conditions

a0= 1 and a1= 2.

Step 1: Finding the homogeneous solution. Let’s first solve the homoge-

neous part of the recurrence relation by setting an=cn. Substituting this into

the relation, we get cn= 3cn−1−2cn−2. Dividing the above equation by cn−2

gives us the characteristic equation: c2= 3c−2. Solving the characteristic

equation, we find c= 2 and c= 1.

Therefore, the homogeneous solution is ahomogeneous =A(2n) + B(1n) =

A(2n) + B.

Step 2: Finding the particular solution. Next, let’s find a particular solution

to the non-homogeneous part. Since 2nis a polynomial of degree 1, we try a

particular solution of the form an=p·2n. Substitute this into the relation:

p·2n= 3(p·2n−1)−2(p·2n−2)+2n.

Solving for p, we find p=−1.

Therefore, the particular solution is aparticular =−2n.

Step 3: Finding the complete solution. The final solution is the sum of

the homogeneous and particular solutions: an=ahomogeneous +aparticular =

A(2n) + B+ (−2n).

Step 4: Applying initial conditions. Using a0= 1 and a1= 2, we can find

Aand B. From a0= 1: A+B−1 = 0. From a1= 2: 2A+B−2 = 0.

Solving these equations, we get A= 0.5 and B= 0.5.

Step 5: Final explicit formula. Therefore, the explicit formula for anis

an= 0.5(2n)+0.5−2n= 0.5·3n+ 0.5.

Question 31

Question

Find a closed-form expression for the sequence defined by the following recur-

rence relation:

an= 2an−1−2an−2+ 2n, with initial conditions a0= 1 and a1= 3.

Solution

To solve this recurrence relation, we need to find the characteristic polynomial

and the particular solution.

Step 1: Find the characteristic polynomial

The characteristic polynomial of the homogeneous part of the recurrence relation

is given by r2−2r+ 2 = 0. Solving this quadratic equation, we find that the

roots are r= 1 ±i. Therefore, the corresponding characteristic polynomial is

(r−1 + i)(r−1−i) = (r−1)2+ 1.

Step 2: Find the particular solution

We can guess that a particular solution for the non-homogeneous part is of the

form an=c·2n, where cis a constant to be determined. Plugging this into the

original recurrence relation, we get:

c·2n= 2(c·2n−1)−2(c·2n−2)+2n

This simplifies to c= 2c−c+ 1, which gives c= 1.

Step 3: Find the general solution

The general solution to the recurrence relation is given by:

an=A(1 + i)n+B(1 −i)n+ 2n

where Aand Bare constants.

Step 4: Use initial conditions to find Aand B

Using the initial conditions a0= 1 and a1= 3, we get the following two equa-

tions:

A+B+ 1 = 1

A(1 + i) + B(1 −i) + 2 = 3

Solving these equations simultaneously, we find A= 1/2 and B=−1/2.

Step 5: Write down the closed-form expression

Therefore, the closed-form expression for the sequence is:

an=1

2(1 + i)n−1

2(1 −i)n+ 2n

Question 32

Question

Consider the non-homogeneous recurrence relation an= 3an−1−2an−2+ 2n

with initial conditions a0= 1 and a1= 3. Determine a closed-form expression

for an.

Solution

To solve the non-homogeneous recurrence relation, we first find the general

solution to the associated homogeneous recurrence relation and a particular

solution to the non-homogeneous part.

Step 1: Find the homogeneous solution Let a(h)

nbe the solution to

the homogeneous part of the recurrence relation: a(h)

n= 3an−1−2an−2. The

characteristic equation is r2= 3r−2, which simplifies to r2−3r+ 2 = 0.

Factoring the characteristic equation gives (r−1)(r−2) = 0, so the roots are

r1= 1 and r2= 2. Therefore, the general form of the homogeneous solution is

a(h)

n=C1·1n+C2·2n, where C1and C2are constants to be determined.

Step 2: Find a particular solution Let a(p)

n=K·2nbe a particular

solution to the non-homogeneous part of the recurrence relation. Substitute

a(p)

ninto the recurrence relation:

K·2n= 3(K·2n−1)−2(K·2n−2)+2n.

Solving for K, we get K=2n

2. Therefore, a particular solution is a(p)

n= 2n+1.

Step 3: Combine solutions The general solution to the non-homogeneous

recurrence relation is the sum of the homogeneous and particular solutions:

an=a(h)

n+a(p)

n=C1·1n+C2·2n+ 2n+1.

Step 4: Apply initial conditions Using the initial conditions a0= 1 and

a1= 3:

a0=C1+C2+ 2 = 1 =⇒C1+C2=−1,

a1=C1·1 + C2·2 + 4 = 3 =⇒C1+ 2C2=−1.

Solving the system of equations, we find C1=−3 and C2= 2. Therefore, the

closed-form expression for anis:

an=−3+2·2n+ 2n+1 =−3+2n+ 2n+1.

Question 33

Question

Find a closed-form solution to the following non-homogeneous recurrence rela-

tion:

an= 2an−1+ 3n, a0= 1

Solution

To solve the non-homogeneous recurrence relation, we first solve the corre-

sponding homogeneous part and then find a particular solution for the non-

homogeneous part.

Step 1: Find the homogeneous solution We consider the homogeneous

part:

an= 2an−1

The characteristic equation is r−2 = 0, which has the root r= 2. Thus,

the homogeneous solution is:

a(h)

n=c·2n

Step 2: Find a particular solution Let’s find a particular solution for

the non-homogeneous part of the recurrence relation. We assume the particular

solution takes the form a(p)

n=A·3n.

Substitute this trial solution into the non-homogeneous recurrence relation:

A·3n= 2 ·A·3n−1+ 3n

A·3n= 2A·3n+ 3n

A=1

Therefore, the particular solution is a(p)

n=1

3·3n= 3n−1.

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=c·2n+ 3n−1

Step 4: Apply the initial condition Given a0= 1:

a0=c·20+ 30−1=c+1

3= 1

c=2

Therefore, the closed-form solution to the non-homogeneous recurrence re-

lation is:

an=2

3·2n+ 3n−1

Question 34

Question

Consider the recurrence relation defined by an= 2an−1−2an−2+nfor 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=rnand substitute it into the recurrence relation:

rn= 2rn−1−2rn−2⇒r2−2r+ 2 = 0

The characteristic equation is r2−2r+ 2 = 0, which has roots r= 1 ±i. Thus,

the homogeneous solution is of the form ah=c1(1 + i)n+c2(1 −i)n.

Step 2: Find the particular solution to the non-homogeneous part. Assume

an=An +Band substitute it into the recurrence relation:

An +B= 2(A(n−1) + B)−2(A(n−2) + B) + n

Simplify to get A=−2, B= 3. Therefore, the particular solution is ap=

−2n+ 3.

Step 3: Combine the homogeneous and particular solutions. The general

solution is given by an=ah+ap:

an=c1(1 + i)n+c2(1 −i)n−2n+ 3

Step 4: Use the initial conditions to solve for c1and c2.

a0=c1+c2−0 + 3 = 1 and a1=c1(1 + i) + c2(1 −i)−2 + 3 = 2

Solving the system of equations, we find c1=1−i

2and c2=1+i

Step 5: Substitute the values of c1and c2back into the general solution to

get the closed-form expression.

∴an=1−i

2(1 + i)n+1 + i

2(1 −i)n−2n+ 3

Question 35

Question

Let ansatisfy the following recurrence relation:

an+2 = 6an+1 −9an+ 2n

with initial conditions a0= 1 and a1= 4. Find a formula for anfor all

non-negative integers n.

Solution

To solve this recurrence relation, we first find the homogeneous solution by

setting the right-hand side equal to 0:

an+2 −6an+1 + 9an= 0

r2−6r+ 9 = 0

(r−3)2= 0

This gives us a repeated root r= 3. So, our homogeneous solution is of the

form a(h)

n=c1·3n+c2·n·3n.

Next, we find a particular solution a(p)

nfor the non-homogeneous part 2n.

Since 2nis of the form A·rnwhere r= 2 is not a root of the homogeneous part,

we can try a particular solution of the form a(p)

n=A·2n. Substituting this into

the recurrence relation, we get:

2n+2 = 6 ·2n+1 −9·2n

This gives 4A= 12 −9, so A= 1.5. Thus, our particular solution is a(p)

1.5·2n.

Therefore, the general solution to the non-homogeneous recurrence relation

is:

an=a(h)

n+a(p)

n=c1·3n+c2·n·3n+ 1.5·2n

Using the initial conditions a0= 1 and a1= 4, we can solve for c1and c2:

a0=c1+ 1.5 = 1 =⇒c1=−0.5

a1= 3c1+ 3c2+ 3 = 4 =⇒c2= 1

Thus, the formula for anfor all non-negative integers nis:

an=−0.5·3n+ 1 ·n·3n+ 1.5·2n

Question 7

Question

Consider the recurrence relation: an= 2an−1+ 3an−2where a0= 1 and a1= 2.

Find the explicit formula for the nth term of the sequence.

Solution

To find the explicit formula for the nth term of the sequence, we first need to find

the characteristic equation for the given recurrence relation. The characteristic

equation for a homogeneous linear recurrence relation of the form an=c1an−1+

c2an−2is given by r2−c1r−c2= 0.

Step 1: Find the characteristic equation The recurrence relation is

an= 2an−1+ 3an−2. Therefore, the characteristic equation is r2−2r−3 = 0.

Step 2: Solve the characteristic equation To solve the characteristic

equation r2−2r−3 = 0, we factor it as (r−3)(r+ 1) = 0. Thus, the roots are

r= 3 and r=−1.

Step 3: Write the general solution The general solution for the homoge-

neous recurrence relation an= 2an−1+3an−2is given by an=c1(3)n+c2(−1)n,

where c1and c2are constants to be determined using the initial conditions.

Step 4: Use initial conditions to find c1and c2Given initial conditions

a0= 1 and a1= 2, we have the following system of equations:

c1+c2= 1

3c1−c2= 2

Solving this system, we find c1=1

2and c2=1

Step 5: Write the explicit formula Substitute c1=1

2and c2=1

2into the

general solution to obtain the explicit formula for the nth term of the sequence:

an=1

2(3)n+1

2(−1)n

Question 8

Question

Consider the following recurrence relation:

an= 2an−1−2an−2+ 2n

Find the general solution to the given recurrence relation.

Solution

Step 1: Find the characteristic equation by assuming the solution has the form

an=rn:

rn= 2rn−1−2rn−2

Step 2: Divide the equation by rn−2:

r2= 2r−2

Step 3: Rewrite the equation as a quadratic equation:

r2−2r+ 2 = 0

Step 4: Solve the quadratic equation for rusing the quadratic formula:

r=2±p(−2)2−4(1)(2)

2(1) =2±√4−8

2=2±2i

2= 1 ±i

So the general solution to the homogeneous part of the recurrence relation

is:

an=c1(1 + i)n+c2(1 −i)n

Step 5: Find a particular solution to the non-homogeneous part of the recur-

rence relation: Let’s guess a particular solution of the form an=An2n, where

Ais a constant to be determined.

Substitute an=An2ninto the original recurrence relation:

An2n= 2(A(n−1)2n−1)−2(A(n−2)2n−2)+2n

Step 6: Simplify the equation:

An2n= 2An2n−2An2n+ 2n

An2n= 2n

Step 7: Solve for A:

A=2n

2n= 1

Step 8: So the particular solution is an=n2n.

Step 9: The general solution to the entire recurrence relation is the sum of

the homogeneous and particular solutions:

an=c1(1 + i)n+c2(1 −i)n+n2n

Question 9

Question

Consider the non-homogeneous recurrence relation given by an= 3an−1−

2an−2+ 2n. If a0= 1 and a1= 4, find a formula for anfor n≥2.

Solution

To solve the non-homogeneous recurrence relation, we will first find the general

solution to the associated homogeneous recurrence relation, and then determine

a particular solution for the non-homogeneous part.

Step 1: Find the general solution The associated homogeneous recur-

rence relation is an= 3an−1−2an−2. Let’s start by finding the characteristic

equation:

r2= 3r−2

r2−3r+ 2 = 0

(r−1)(r−2) = 0

r= 1,2

Therefore, the general solution to the homogeneous part is:

an=c1(1)n+c2(2)n

Step 2: Find a particular solution To find a particular solution to the

non-homogeneous part, let’s try a solution of the form an=k(2)n. Substitute

this into the original relation:

k(2)n= 3k(2)n−1−2k(2)n−2+ 2n

k= 3k(1/2) −2k(1/4) + 2

k=3

2k−1

2k+ 2

2k−1

2k= 2

k= 4

Therefore, a particular solution is an= 4(2)n.

Step 3: Find the full solution Combining the general solution and the

particular solution, we have:

an=c1+ 2c2+ 4(2)n

Step 4: Find the values of c1and c2Using the initial conditions a0= 1

and a1= 4, we can find c1and c2:

c1+ 2c2+ 4 = 1

c1+ 4c2+ 8 = 4

Solving these equations simultaneously, we find c1= 5 and c2=−4.

Step 5: Write the final formula Therefore, the formula for anfor n≥2

is:

an= 5 + (−4)(2)n+ 4(2)n

Question 10

Question

Consider the non-homogeneous recurrence relation:

an= 2an−1−an−2+ 3n.

Given that a0= 1 and a1= 3, find an expression for anin terms of n.

Solution

We first solve the corresponding homogeneous recurrence relation: an= 2an−1−

an−2.Step 1: Find the characteristic equation by assuming an=rn:

rn= 2rn−1−rn−2

r2= 2r−1

r2−2r+ 1 = 0

(r−1)2= 0

r= 1 (double root)

Step 2: The general solution to the homogeneous part is given by:

a(h)

n=c1·1n+c2·n·1n=c1+c2n.

Now, we find a particular solution a(p)

nto the non-homogeneous part of the

recurrence relation: an= 2an−1−an−2+ 3n.Since the non-homogeneity is 3n,

we try a particular solution of the form A·3n.Step 3: Substitute a(p)

n=A·3n

into the recurrence relation:

A·3n= 2(A·3n−1)−(A·3n−2)+3n

A·3n= 2A·3n−2A·3n−1+ 3n

0 = −A·3n+ 2A·3n−1

0 = −A+ 2A·3−1=⇒A=1

Therefore, a(p)

n=1

2·3nis a particular solution.

Step 4: The general solution to the entire recurrence relation is the sum of

the solutions to the homogeneous and non-homogeneous parts:

an=a(h)

n+a(p)

n=c1+c2n+1

2·3n.

Step 5: Using the initial conditions a0= 1 and a1= 3, we can find c1and

c2:

a0=c1+1

2= 1 =⇒c1=1

a1=c1+c2+3

2= 3 =⇒c2=5

Step 6: Finally, the expression for anin terms of nis:

an=1

2+5

2n+1

2·3n.

Question 11

Question

Consider the non-homogeneous recurrence relation given by an= 2an−1−an−2+

2nwith initial conditions a0= 0 and a1= 1. Find a closed-form expression for

an.

Solution

To solve the non-homogeneous recurrence relation, we need to find both the

particular solution and the complementary function.

Step 1: Find the complementary function

First, we solve the associated homogeneous recurrence relation ah

n= 2ah

n−1−

n−2. Assume ah

n=rn:

rn= 2rn−1−rn−2=⇒r2−2r+ 1 = 0 =⇒(r−1)2= 0

Thus, r= 1 is a repeated root. The complementary function is then given by

n=c1·1n+c2·n·1n=c1+c2n, where c1and c2are constants.

Step 2: Find the particular solution

Next, we find a particular solution for the non-homogeneous recurrence relation.

Since the term on the right-hand side is of the form 2n, we assume ap

n=A·2n:

A·2n= 2(A·2n−1)−(A·2n−2)+2n

Solving for A, we get A=−1. Therefore, the particular solution is ap

n=−2n.

Step 3: Combine the solutions

The general solution is the sum of the complementary function and the partic-

ular solution:

an=ah

n+ap

n=c1+c2n−2n

Step 4: Use initial conditions to determine c1and c2

Using the initial conditions a0= 0 and a1= 1:

(c1−1 = 0

c1+c2−2=1

Solving this system of equations, we find c1= 1 and c2= 2.

Step 5: Final closed-form solution

Therefore, the explicit formula for anis:

an= 1 + 2n−2n

Question 12

Question

Let (an) be the sequence defined by the recurrence relation an= 2an−1−

2an−2+ 2nfor n≥2 with initial conditions a0= 0 and a1= 4. Find a

closed-form expression for an.

Solution

Step 1: Characteristic equation. We first solve the characteristic equation r2−

2r+ 2 = 0 to find the homogeneous solution. The roots of the characteristic

equation are given by

r=2±p(−2)2−4·1·2

2·1= 1 ±i,

where iis the imaginary unit. Thus, the general solution to the homogeneous

recurrence relation is

a(h)

n=c1·1n·cos(n·ln(2)) + c2·1n·sin(n·ln(2)),

where c1and c2are constants to be determined.

Step 2: Particular solution. We now find a particular solution to the non-

homogeneous recurrence relation. Since 2nis a polynomial of degree 1, we try

a particular solution of the form a(p)

n=An ·2n. Substituting this form into the

original recurrence relation, we get

An ·2n= 2(An −1·2n−1)−2(An −2·2n−2)+2n.

This simplifies to A=1

2. Therefore, a particular solution is a(p)

n=n

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(h)

n+a(p)

n=c1·1n·cos(n·ln(2)) + c2·1n·sin(n·ln(2)) + n

2·2n.

Step 4: Applying initial conditions. Using the initial conditions a0= 0 and

a1= 4, we find c1=−3

2and c2= 0. Therefore, the closed-form expression for

anis

an=−3

2·cos(n·ln(2)) + n

2·2n.

Question 13

Question

Consider the non-homogeneous recurrence relation given by an= 2an−1−an−2+

2n+ 1, with initial conditions a0= 1 and a1= 2. Find the explicit formula for

an.

Solution

Step 1: First, find the homogeneous solution by solving the characteristic equa-

tion x2= 2x−1.

x2−2x+ 1 = 0

(x−1)2= 0

x= 1 (double root)

Step 2: Therefore, the homogeneous solution is given by a(h)

n=c1·1n+c2·

n·1n=c1+c2n.

Step 3: Next, find a particular solution a(p)

nby assuming it has the form

a(p)

n=An2+Bn +C. Substitute this into the original non-homogeneous recur-

rence relation.

Step 4: Substituting a(p)

n=An2+Bn+Cinto the original non-homogeneous

relation, we get:

An2+Bn +C= 2(An2+B(n−1) + C)−(An(n−1) + B(n−2) + C) + 2n+ 1

Step 5: Simplifying the above equation, we get:

An2+Bn +C= 2An2+ 2Bn + 2C−An2+An −Bn +B+ 2n+ 1

Step 6: Matching coefficients for n2:A= 2A−A, so A=−1.

Step 7: Matching coefficients for n:B= 2B+A−B=B−1, so B= 1.

Step 8: Matching constants: C= 2C+ 1, so C=−1.

Step 9: Therefore, the particular solution is a(p)

n=−n2+n−1.

Step 10: The general solution is given by an=a(h)

n+a(p)

n=c1+c2n−n2+

n−1.

Step 11: Using the initial conditions a0= 1 and a1= 2 to solve for c1and

c2:

a0=c1−1 = 1 =⇒c1= 2

a1=c1+c2−1 = 2 =⇒2 + c2−1 = 2 =⇒c2= 1

Step 12: Thus, the explicit formula for anis an= 2 + n−n2.

Question 14

Question

Let anbe defined recursively by the recurrence relation:

an= 3an−1−2an−2+ 2n

with initial conditions a0= 1 and a1= 2. Find a closed-form expression for an.

Solution

Step 1: Finding the homogeneous solution We start by setting the right-hand

side of the given recurrence relation to 0 to find the homogeneous solution:

an= 3an−1−2an−2

Step 2: Characteristic equation To find the characteristic polynomial, we

substitute an=rninto the homogeneous equation:

rn= 3rn−1−2rn−2

r2−3r+ 2 = 0

(r−1)(r−2) = 0

So, the roots of the characteristic equation are r1= 1 and r2= 2.

Step 3: General homogeneous solution The general solution of the homoge-

neous recurrence relation is given by:

an=c1(1n) + c2(2n)

an=c1+c2(2n)

Step 4: Finding the particular solution Since the non-homogeneous term is

2n, we assume a particular solution of the form A(2n):

A(2n)=3A(2n−1)−2A(2n−2)+2n

Step 5: Solving for A Substitute 2ninto the above equation and simplify:

A(2n)=3A(2n−1)−2A(2n−2)+2n

A= 3A−2A+ 2

A= 2

Step 6: Complete solution The complete solution is the sum of the homoge-

neous and particular solutions:

an=c1+c2(2n)+2n

Step 7: Using initial conditions We use the initial conditions a0= 1 and

a1= 2 to find c1and c2:

a0=c1+c2= 1

a1=c1+ 2c2+ 2 = 2

Solving the above system of equations, we find c1= 0 and c2= 1.

Step 8: Final closed-form expression Therefore, the closed-form expression

for anis:

an= 2n+ 2(2n) = 3(2n)

an= 3 ×2n

Question 15

Question

Consider the non-homogeneous recurrence relation defined by an= 3an−1−

2an−2+ 2nwith initial conditions a0= 4 and a1= 6. Find a closed-form

expression for an.

Solution

Step 1: 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 factors as r2−3r+ 2 =

(r−1)(r−2) = 0. Therefore, the characteristic roots are r1= 1 and r2= 2,

and the general solution to the homogeneous recurrence relation is

a(h)

n=c1·1n+c2·2n=c1+c2·2n.

Step 2: To find a particular solution a(p)

nto the non-homogeneous recurrence

relation, we try the form a(p)

n=A·2n, where Ais a constant to be determined.

Substituting this into the recurrence relation gives

A·2n= 3(A·2n−1)−2(A·2n−2)+2n.

Step 3: Simplifying, we get

A·2n= 3A·2n−1−2A·2n−2+ 2n.

Step 4: Divide both sides by 2nto obtain

A=3A

2−2A

4+ 1.

Step 5: Solving for Ayields A= 4. Thus, the particular solution is a(p)

4·2n.

Step 6: The general solution to the non-homogeneous recurrence relation

is the sum of the general solution to the homogeneous part and the particular

solution:

an=a(h)

n+a(p)

n=c1+c2·2n+ 4 ·2n.

Step 7: Applying the initial conditions a0= 4 and a1= 6 yields the equations

c1+4 = 4 and c1+2c2+8 = 6. Solving these equations gives c1= 0 and c2=−2.

Step 8: Therefore, the closed-form expression for anis

an=−2·2n+ 4 ·2n= 2n+2.

Question 16

Question

Consider the following recurrence relation:

an= 2an−1−an−2+ 2n

where a0= 1 and a1= 2. Determine a closed-form expression for an.

Solution

Step 1: First, let’s find the characteristic equation of the homogeneous part of

the recurrence relation:

a(h)

n= 2an−1−an−2

The characteristic equation is given by r2= 2r−1, which simplifies to r2−2r+

1=(r−1)2= 0. Thus, the characteristic root is r= 1.

Step 2: Therefore, the general solution to the homogeneous part is a(h)

c1·1n+c2·n·1n=c1+c2n.

Step 3: Now, we need to find a particular solution for the non-homogeneous

part of the recurrence relation:

a(p)

n= 2n

Since the non-homogeneous part is a constant times 2n, we can assume a par-

ticular solution of the form a(p)

n=An2n. Let’s substitute this into the original

recurrence relation:

An2n= 2(An2(n−1))−(An2(n−2))+2n

An2n= 2An2n−1−An2n−2+ 2n

An = 2An −An + 1

An =An + 1

0=1

This leads to a contradiction. Therefore, we need to multiply by n:

a(p)

n=An2·2n

A(n2−n)2n= 2(A(n−1)2·2n−1)−A(n−2)2·2n−2+ 2n

A(n2−n)=2A(n−1)2−A(n−2)2+ 1

By comparing coefficients, we find A= 1.

Step 4: Thus, the particular solution is a(p)

n=n2·2n.

Step 5: Finally, the general solution is the sum of the homogeneous and

particular solutions:

an=a(h)

n+a(p)

n=c1+c2n+n2·2n

Step 6: Using the initial conditions a0= 1 and a1= 2, we can solve for c1

and c2. Substituting these values into the general solution gives the closed-form

expression for an.

Question 17

Question

Find a closed-form expression for the solution to the following non-homogeneous

recurrence relation:

an= 3an−1−an−2+ 2n

given that a0= 1 and a1= 2.

Solution

To solve this non-homogeneous recurrence relation, we first find the general

solution to the associated homogeneous recurrence relation. Then, we find a

particular solution for the non-homogeneous term, and combine both solutions

to form the general solution.

Step 1: Find the general solution to the homogeneous recurrence

relation Consider the homogeneous part of the recurrence relation:

an= 3an−1−an−2

Assume a solution of the form an=rn. Substituting this into the equation

gives us:

rn= 3rn−1−rn−2

Dividing by rn−2, we get the characteristic equation:

r2= 3r−1

r2−3r+ 1 = 0

Solving this quadratic equation gives us the roots r1and r2.

Step 2: Find the particular solution for the non-homogeneous term

To find the particular solution, we guess a solution of the form an=Arn, where

Ais a constant to be determined.

Substitute an=Arninto the non-homogeneous part of the recurrence rela-

tion:

Arn= 3Arn−1−Arn−2+ 2n

Dividing by rn−2, we get:

r2−3r+ 1 = 2n

Determine Aby matching the terms.

Step 3: Combine the solutions The general solution anis the sum of

the general solution to the homogeneous part and the particular solution:

an=a(h)

n+a(p)

Substitute the initial conditions a0= 1 and a1= 2 to find the values of A

and any constants from the homogeneous part if necessary. Now, combine the

two solutions to find the closed-form expression for an.

Question 18

Question

Consider the non-homogeneous recurrence relation defined by an= 2an−1−

2an−2+ 2nfor n≥2, with initial conditions a0= 1 and a1= 3. Find a

closed-form expression for an.

Solution

We will first find the general solution to the associated homogeneous recurrence

relation an= 2an−1−2an−2before finding a particular solution for the non-

homogeneous term 2n.

Step 1: Find the characteristic equation For the homogeneous recur-

rence relation an= 2an−1−2an−2, we assume a solution of the form an=rn.

Substituting, we get

rn= 2rn−1−2rn−2.

Dividing by rn−2gives the characteristic equation r2= 2r−2. Simplifying, we

get r2−2r+ 2 = 0.

Step 2: Find the roots of the characteristic equation Solving the

characteristic equation r2−2r+ 2 = 0, we get

r=2±p(−2)2−4·1·2

2·1= 1 ±i.

Step 3: Find the general solution to the homogeneous part The

general solution to the associated homogeneous recurrence relation is

a(h)

n=c1(1 + i)n+c2(1 −i)n,

where c1and c2are constants determined by the initial conditions.

Step 4: Find a particular solution to the non-homogeneous term

Since 2nis a geometric series, we guess that a particular solution is of the form

a(p)

n=Crn, where Cis a constant to be determined. Substitute this into the

non-homogeneous recurrence relation to solve for C:

Crn= 2(Crn−1)−2(Crn−2)+2n.

This simplifies to C=−22, so a(p)

n=−2n+2.

Step 5: Find the general solution to the overall equation The general

solution to the non-homogeneous recurrence relation is the sum of the general

solution of the homogeneous part and the particular solution:

an=a(h)

n+a(p)

n=c1(1 + i)n+c2(1 −i)n−2n+2.

Step 6: Apply initial conditions to solve for constants Using the

initial conditions a0= 1 and a1= 3, we can solve for c1and c2.

a0= 1 = c1+c2−16,

a1= 3 = (1 + i)c1+ (1 −i)c2−32.

Solving these equations gives c1=7

2and c2=17

Step 7: Final expression for anSubstitute the values of c1and c2back

into the general solution to get the closed-form expression for an:

an=7

2(1 + i)n+17

2(1 −i)n−2n+2.

Question 19

Question

Let {an}be a sequence defined by the recurrence relation

an= 2an−1−3an−2+ 2n,

with initial conditions a0= 1 and a1=−1. Find a closed-form formula for an.

Solution

To find a closed-form formula for an, we first need to find the characteristic

equation associated with the homogeneous part of the recurrence relation. This

equation is given by xn= 2xn−1−3xn−2. Dividing by xn−2gives x2= 2x−3,

which simplifies to x2−2x+ 3 = 0.

Step 1: Find the roots of the characteristic equation The roots of

the characteristic equation x2−2x+ 3 = 0 can be found using the quadratic

formula:

x=−(−2) ±p(−2)2−4·1·3

2·1=2±√4−12

2= 1 ±i√2.

Therefore, the roots are complex: r1= 1 + i√2 and r2= 1 −i√2.

Step 2: Write the general solution for the homogeneous part The

general solution for the homogeneous part of the recurrence relation is given by

a(h)

n=c1(1 + i√2)n+c2(1 −i√2)n.

Step 3: Find a particular solution for the non-homogeneous part

Let’s assume a particular solution of the form a(p)

n=A2n, where Ais a constant

to be determined. Substitute this into the original recurrence relation:

A2n= 2(A2n−1)−3(A2n−2)+2n.

Simplifying this equation yields A=−1. Thus, a particular solution is

a(p)

n=−2n.

Step 4: Write the general solution for the entire recurrence rela-

tion The general solution for the entire recurrence relation is the sum of the

solutions of the homogeneous and non-homogeneous parts:

an=a(h)

n+a(p)

n=c1(1 + i√2)n+c2(1 −i√2)n−2n.

Step 5: Apply the initial conditions to find the values of c1and

c2Using the initial conditions a0= 1 and a1=−1, we can solve for c1and

c2. Substituting n= 0 and n= 1 into the general solution gives the system of

equations:

(c1+c2−1=0

c1(1 + i√2) + c2(1 −i√2) −2 = −1.

Solving this system of equations leads to c1=9

8−3

8i√2 and c2=9

8+3

8i√2.

Step 6: Write the closed-form formula for anFinally, substituting the

values of c1and c2into the general solution gives the closed-form formula for

an:

an=9

8−3

8i√2(1 + i√2)n+9

8+3

8i√2(1 −i√2)n−2n.

Question 20

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

Dividing by rn−2, we get:

r2= 3r−2 =⇒r2−3r+ 2 = 0

This gives us the characteristic equation r2−3r+ 2 = 0, which factors to

(r−1)(r−2) = 0. Therefore, the roots are r1= 1 and r2= 2.

Step 2: Write the general solution based on the roots:

an=c1·1n+c2·2n

Simplify to get:

an=c1+c2·2n

Step 3: Use the initial conditions to solve for c1and c2: Given a0= 1, we

have:

1 = c1+c2·20=c1+c2

Given a1= 2, we have:

2 = c1+c2·21=c1+ 2c2

Solving these two equations simultaneously, we find c1=−2 and c2= 3.

Therefore, the closed-form expression for anis:

an=−2+3·2n

Question 21

Question

Let anbe a sequence defined by the recurrence relation an+2 = 5an+1 −6anfor

all integers n≥0 with 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

associated with the given recurrence relation an+2 = 5an+1 −6an.

Step 1: Write down the characteristic equation The characteristic

equation corresponding to an+2 = 5an+1 −6anis r2= 5r−6.

Step 2: Solve the characteristic equation We can rewrite the charac-

teristic equation as r2−5r+ 6 = 0. This factors as (r−2)(r−3) = 0, so the

roots are r1= 2 and r2= 3.

Step 3: Find the general solution Since the roots are distinct, the

general solution to the recurrence relation is of the form an=c1·2n+c2·3n.

Step 4: Use initial conditions to find c1and c2Given a0= 2 and

a1= 5, we can substitute these values into the general solution:

a0=c1·20+c2·30=c1+c2= 2

a1=c1·21+c2·31= 2c1+ 3c2= 5

Solving this system of equations, we get c1= 1 and c2= 1.

Step 5: Write the final formula for anTherefore, the formula for anis

an= 2n+ 3nfor all integers n≥0.

Question 22

Question

Consider the following recurrence relation:

an= 2an−1−2an−2+ 2n, n ≥2

with initial conditions a0= 0 and a1= 3. Find a closed-form expression for an.

Solution

To solve this recurrence relation, we first solve the associated homogeneous

recurrence relation:

a(h)

n= 2a(h)

n−1−2a(h)

n−2

Step 1: Find the characteristic equation Let a(h)

n=rn. Substitute

a(h)

n=rninto the homogeneous recurrence relation to get:

rn= 2rn−1−2rn−2

Divide by rn−2to simplify:

r2= 2r−2

This gives us the characteristic equation:

r2−2r+ 2 = 0

Step 2: Find the roots of the characteristic equation Using the

quadratic formula r=−(−2)±√(−2)2−4(1)(2)

2(1) , we get:

r=2±√4−8

2=2±√−4

2= 1 ±i

Step 3: Find the general solution of the homogeneous recurrence

relation The general solution is:

a(h)

n=c1(1 + i)n+c2(1 −i)n

Step 4: Find the particular solution of the non-homogeneous re-

currence relation Let’s assume a particular solution of the form a(p)

n=An2n.

Substitute a(p)

n=An2ninto the original recurrence relation:

An2n= 2(A(n−1)2(n−1))−2(A(n−2)2(n−2))+2n

An2n= 2A(n−1)2(n−1) −2A(n−2)2(n−2) + 2n

An = 2A(n−1) −2A(n−2) + 1

Step 5: Solve for the particular solution coefficients By comparing

coefficients we get:

A= 2A=⇒A= 0.5

Step 6: Find the general solution of the non-homogeneous recur-

rence relation The general solution is:

an=a(h)

n+a(p)

n=c1(1 + i)n+c2(1 −i)n+ 0.5n2n

Step 7: Use the initial conditions to find the values of c1and c2

Using the initial conditions a0= 0 and a1= 3:

c1+c2= 0

c1(1 + i) + c2(1 −i) + 1 = 3

Solving these equations, we get c1=3−3i

2and c2=3+3i

Step 8: Final closed-form expression for anSubstitute c1and c2back

into the general solution:

an=3−3i

2(1 + i)n+3+3i

2(1 −i)n+ 0.5n2n

Question 23

Question

Consider the following non-homogeneous recurrence relation:

an= 2an−1−an−2+n2+n+ 1

where a0= 1 and a1= 2. Find a closed-form expression for an.

Solution

Step 1: First, we find the closed-form expression for the homogeneous part of

the recurrence relation by setting the right-hand side equal to zero. This gives

us the characteristic equation:

r2−2r+ 1 = 0

(r−1)2= 0

r= 1 (double root)

So, the homogeneous solution is a(h)

n=c1·1n+c2·n·1n=c1+c2n.

Step 2: Next, we need to find a particular solution for the non-homogeneous

part of the recurrence relation. We notice that the particular solution could be

a quadratic function in ndue to the terms n2,n, and the constant 1. Let’s

assume a particular solution of the form a(p)

n=An2+Bn +C.

Step 3: Substituting a(p)

nback into the original recurrence relation:

An2+Bn +C= 2(An2+B(n−1)+C)−(An(n−1)+B(n−1) +C)+ n2+n+1

Step 4: Simplifying and equating coefficients of like terms, we get the fol-

lowing system of equations:

A= 2A−A(coefficient of n2)

B= 2B−B+ 2A(coefficient of n)

C= 2C−C+A(coefficient of 1)

Step 5: Solving the system of equations, we find A=1

2,B=−1, and C=3

Therefore, the particular solution is a(p)

n=1

2n2−n+3

Step 6: Combining the homogeneous and particular solutions, we have:

an=a(h)

n+a(p)

n=c1+c2n+1

2n2−n+3

Step 7: Applying the initial conditions a0= 1 and a1= 2 to solve for c1and

c2:

c1= 1.5 and c2= 1

Therefore, the closed-form expression for anis:

an= 1.5 + n+1

2n2−n+3

2=1

2n2+ 0.5n+ 3

Question 24

Question

Consider the non-homogeneous recurrence relation an= 3an−1−2an−2+ 2n,

where a0= 1 and a1= 2. Find a closed-form expression for an.

Solution

To solve this non-homogeneous recurrence relation, we need to find both the

general solution to the homogeneous part and a particular solution to the non-

homogeneous part.

Step 1: Find the homogeneous solution We first solve the correspond-

ing homogeneous recurrence relation an= 3an−1−2an−2by assuming an=rn

and substituting it into our recurrence relation:

rn= 3rn−1−2rn−2

Dividing by rn−2gives us the characteristic equation:

r2= 3r−2

This factors to (r−2)(r−1) = 0, so r= 2 and r= 1 are the roots. Therefore,

the general solution to the homogeneous part is:

a(h)

n=c1(2)n+c2(1)n=c1(2)n+c2

Step 2: Find the particular solution Now we look for a particular

solution to the non-homogeneous part. Since the non-homogeneous term 2nis a

geometric progression, we can try a particular solution of the form a(p)

n=A2n.

Substituting this into the original recurrence relation gives:

A2n= 3A2n−1−2A2n−2+ 2n

Simplifying, we get:

A= 3A−2A+ 1

A=A+ 1

This implies A= 1. Therefore, a particular solution is a(p)

n= 2n.

Step 3: Find the general solution The general solution to the non-

homogeneous recurrence relation is the sum of the homogeneous and particular

solutions:

an=a(h)

n+a(p)

n=c1(2)n+c2+ 2n

Step 4: Find the constants using initial conditions Using the initial

conditions a0= 1 and a1= 2, we can solve for c1and c2:

a0=c1(2)0+c2+ 20=c1+c2= 1

a1=c1(2)1+c2+ 21= 2c1+c2+ 2 = 2

Solving these equations simultaneously, we find c1=−1 and c2= 2.

Therefore, the closed-form expression for anis:

an=−2n+ 2 + 2n= 2 + (−1)n

Question 25

Question

Consider the non-homogeneous recurrence relation given by an= 2an−1−

3an−2+ 2nwith initial conditions a0= 1 and a1= 4. Find a closed-form

expression for an.

Solution

We will first solve the homogeneous part of the recurrence relation an= 2an−1−

3an−2, and then find a particular solution to incorporate the non-homogeneous

part 2n.

Step 1: Solve the homogeneous part Let a(h)

nbe the solution to the

homogeneous part of the recurrence relation. The characteristic equation is

given by:

r2= 2r−3

r2−2r+ 3 = 0

Solving this quadratic equation, we find that the roots are complex conju-

gates:

r= 1 ±i√2

Therefore, the solution to the homogeneous part is:

a(h)

n=c1(1 + i√2)n+c2(1 −i√2)n

Step 2: Find a particular solution We see that the non-homogeneous

part 2ncan be represented by a geometric progression. A particular solution

for the non-homogeneous part can be written as:

a(p)

n=A·2n

Step 3: Substitute and find the constants Substitute an=a(h)

n+a(p)

into the original recurrence relation:

c1(1+i√2)n+c2(1−i√2)n+A·2n= 2[c1(1+i√2)n−1+c2(1−i√2)n−1]−3[c1(1+i√2)n−2+c2(1−i√2)n−2]+2n

Next, substitute n= 0 and n= 1 to find values of c1,c2, and A.

Step 4: Final solution After finding the values of c1,c2, and A, the

closed-form expression for anis:

an=a(h)

n+a(p)

Question 26

Question

Consider the non-homogeneous recurrence relation defined by:

an= 2an−1+ 3n

with the initial condition a0= 4. Find a closed-form expression for anin

terms of n.

Solution

Step 1: Solve the associated homogeneous recurrence relation an= 2an−1to find

the complementary function CF . To solve the homogeneous recurrence relation,

we assume the form an=rnand substitute it into the equation an= 2an−1:

rn= 2rn−1

Dividing both sides by rn−1gives:

r= 2

So, the complementary function CF is an=A·2n, where Ais a constant to be

determined.

Step 2: Find a particular solution pnfor the non-homogeneous recurrence

relation. To find a particular solution, we guess that pnhas the form pn=B·3n,

where Bis a constant to be determined. Substituting this into the equation

an= 2an−1+ 3ngives:

B·3n= 2B·3n−1+ 3n

Solving for Bwe get B=1

Step 3: The general solution anis the sum of the complementary function

CF and the particular solution pn. Therefore, the general solution is:

an=CF +pn=A·2n+1

3·3n

Given that the initial condition is a0= 4, we can find the value of A:

4 = A·20+1

3·30

4 = A+1

A=11

Hence, the closed-form expression for anin terms of nis:

an=11

3·2n+1

3·3n

Question 27

Question

Consider the following recurrence relation:

an+2 = 2an+1 −15an+ 2n

with initial conditions a0= 1 and a1= 4. Find an explicit formula for an.

Solution

To find an explicit formula for an, we first need to solve the homogeneous part

of the recurrence relation. Then, we will find a particular solution for the non-

homogeneous part and combine the two solutions.

Step 1: Solve the homogeneous part: The homogeneous part of the

recurrence relation is an+2 = 2an+1 −15an.

Let an=rnbe the assumed form of the solution. Substituting this into the

homogeneous part, we get:

rn+2 = 2rn+1 −15rn

r2−2r−15 = 0

Factoring the quadratic equation, we have:

(r−5)(r+ 3) = 0

So, the roots are r= 5 and r=−3.

Therefore, the general solution to the homogeneous part is:

a(h)

n=A·5n+B·(−3)n

Step 2: Find a particular solution for the non-homogeneous part:

For the non-homogeneous part 2n, we will assume a solution of the form a(p)

c·2n.

Substituting into the non-homogeneous part, we get:

c·2n+2 = 2(c·2n+1)−15(c·2n)+2n

4c·2n= 2c·2·2n−15c·2n+ 2n

4c= 4c−15c+ 1

c=1

So, a particular solution is a(p)

n=1

4·2n= 2n−2.

Step 3: Combine the solutions: The general solution to the original

recurrence relation is the sum of the homogeneous and particular solutions:

an=a(h)

n+a(p)

n=A·5n+B·(−3)n+ 2n−2

Step 4: Use initial conditions to find A and B: Using the initial

conditions a0= 1 and a1= 4:

a0=A+B+1

4= 1

a1= 5A−3B+ 2 = 4

Solving these equations, we find A=17

12 and B=−1

Therefore, the explicit formula for anis:

an=17

12 ·5n−1

3·(−3)n+ 2n−2

Question 28

Question

Let ansatisfy the recurrence relation an= 3an−1−2an−2+ 2nfor n≥2, where

a0= 1 and a1= 2. Find a formula for an.

Solution

Step 1: First, we solve the homogeneous part of the recurrence relation an=

3an−1−2an−2. This corresponds to the characteristic equation r2= 3r−2,

which simplifies to r2−3r+ 2 = 0. This factors as (r−1)(r−2) = 0, so the

characteristic roots are r= 1 and r= 2.

Step 2: Thus, the general solution to the homogeneous part of the recurrence

relation is a(h)

n=A·1n+B·2n, where Aand Bare constants to be determined.

Step 3: Now, we look for a particular solution to the non-homogeneous part

of the recurrence relation an= 2n. Since our non-homogeneous term is of the

form c·2n, a possible form for the particular solution is a(p)

n=C·2n, where C

is a constant to be determined.

Step 4: Substituting a(h)

nand a(p)

nback into the original recurrence relation,

we have: A+ 2B+C·2n= 3(A+ 2B)−2(A·1n−2+B·2n−2)+2n

Step 5: Equating the coefficients of 2n, we get C= 1.

Step 6: Substituting C= 1 back into the particular solution, we have a(p)

2n.

Step 7: Combining the homogeneous and particular solutions, we have the

general solution an=A+ 2B+ 2n.

Step 8: Finally, using the initial conditions a0= 1 and a1= 2, we find A= 1

and B= 0.

Therefore, the formula for anis an= 1 + 2n.

Question 29

Question

Consider the following recurrence relation:

an= 2an−1−an−2+ 2n

Determine the particular solution to the non-homogeneous recurrence rela-

tion given that a0= 1 and a1= 3.

Solution

To solve the non-homogeneous recurrence relation, we need to find the particular

solution a(p)

nthat satisfies the given equation.

Step 1: Find the homogeneous solution Let’s first find the homo-

geneous solution to the recurrence relation an= 2an−1−an−2by assuming

an=rn. Substituting this into the homogeneous part of the recurrence relation

gives:

rn= 2rn−1−rn−2

Dividing by rn−2, we get:

r2= 2r−1

r2−2r+ 1 = 0

(r−1)2= 0

r= 1

Therefore, the homogeneous solution is a(h)

n=c1·1n+c2·n1n=c1+c2n.

Step 2: Find the particular solution We need to find a particular solu-

tion that satisfies an= 2an−1−an−2+ 2n. Since the non-homogeneous part is

2n, we guess that a particular solution is of the form a(p)

n=An2n.

Substitute a(p)

n=An2ninto the recurrence relation:

An2n= 2(A(n−1)2n−1)−A(n−2)2n−2+ 2n

Simplify:

An2n= 2An2n−2A2n−1n+ 2n

Match coefficients of 2nto get A=−1.

So, the particular solution is a(p)

n=−2n.

Step 3: Find the general solution The general solution is the sum of

the homogeneous solution and the particular solution:

an=a(h)

n+a(p)

n=c1+c2n−2n

Step 4: Find c1 and c2 using initial conditions Given that a0= 1 and

a1= 3, we can use these initial conditions to find c1and c2:

From a0= 1:

c1−20= 1

c1−1 = 1

c1= 2

From a1= 3:

c1+c2−21= 3

2 + c2−2=3

c2= 3

Therefore, the particular solution to the non-homogeneous recurrence rela-

tion is an= 2 + 3n−2n.

Question 30

Question

Consider the following recurrence relation: an= 3an−1−2an−2+ 2nwhere

a0= 1 and a1= 2. Find the explicit formula for an.

Solution

Given recurrence relation: an= 3an−1−2an−2+ 2nwith initial conditions

a0= 1 and a1= 2.

Step 1: Finding the homogeneous solution. Let’s first solve the homoge-

neous part of the recurrence relation by setting an=cn. Substituting this into

the relation, we get cn= 3cn−1−2cn−2. Dividing the above equation by cn−2

gives us the characteristic equation: c2= 3c−2. Solving the characteristic

equation, we find c= 2 and c= 1.

Therefore, the homogeneous solution is ahomogeneous =A(2n) + B(1n) =

A(2n) + B.

Step 2: Finding the particular solution. Next, let’s find a particular solution

to the non-homogeneous part. Since 2nis a polynomial of degree 1, we try a

particular solution of the form an=p·2n. Substitute this into the relation:

p·2n= 3(p·2n−1)−2(p·2n−2)+2n.

Solving for p, we find p=−1.

Therefore, the particular solution is aparticular =−2n.

Step 3: Finding the complete solution. The final solution is the sum of

the homogeneous and particular solutions: an=ahomogeneous +aparticular =

A(2n) + B+ (−2n).

Step 4: Applying initial conditions. Using a0= 1 and a1= 2, we can find

Aand B. From a0= 1: A+B−1 = 0. From a1= 2: 2A+B−2 = 0.

Solving these equations, we get A= 0.5 and B= 0.5.

Step 5: Final explicit formula. Therefore, the explicit formula for anis

an= 0.5(2n)+0.5−2n= 0.5·3n+ 0.5.

Question 31

Question

Find a closed-form expression for the sequence defined by the following recur-

rence relation:

an= 2an−1−2an−2+ 2n, with initial conditions a0= 1 and a1= 3.

Solution

To solve this recurrence relation, we need to find the characteristic polynomial

and the particular solution.

Step 1: Find the characteristic polynomial

The characteristic polynomial of the homogeneous part of the recurrence relation

is given by r2−2r+ 2 = 0. Solving this quadratic equation, we find that the

roots are r= 1 ±i. Therefore, the corresponding characteristic polynomial is

(r−1 + i)(r−1−i) = (r−1)2+ 1.

Step 2: Find the particular solution

We can guess that a particular solution for the non-homogeneous part is of the

form an=c·2n, where cis a constant to be determined. Plugging this into the

original recurrence relation, we get:

c·2n= 2(c·2n−1)−2(c·2n−2)+2n

This simplifies to c= 2c−c+ 1, which gives c= 1.

Step 3: Find the general solution

The general solution to the recurrence relation is given by:

an=A(1 + i)n+B(1 −i)n+ 2n

where Aand Bare constants.

Step 4: Use initial conditions to find Aand B

Using the initial conditions a0= 1 and a1= 3, we get the following two equa-

tions:

A+B+ 1 = 1

A(1 + i) + B(1 −i) + 2 = 3

Solving these equations simultaneously, we find A= 1/2 and B=−1/2.

Step 5: Write down the closed-form expression

Therefore, the closed-form expression for the sequence is:

an=1

2(1 + i)n−1

2(1 −i)n+ 2n

Question 32

Question

Consider the non-homogeneous recurrence relation an= 3an−1−2an−2+ 2n

with initial conditions a0= 1 and a1= 3. Determine a closed-form expression

for an.

Solution

To solve the non-homogeneous recurrence relation, we first find the general

solution to the associated homogeneous recurrence relation and a particular

solution to the non-homogeneous part.

Step 1: Find the homogeneous solution Let a(h)

nbe the solution to

the homogeneous part of the recurrence relation: a(h)

n= 3an−1−2an−2. The

characteristic equation is r2= 3r−2, which simplifies to r2−3r+ 2 = 0.

Factoring the characteristic equation gives (r−1)(r−2) = 0, so the roots are

r1= 1 and r2= 2. Therefore, the general form of the homogeneous solution is

a(h)

n=C1·1n+C2·2n, where C1and C2are constants to be determined.

Step 2: Find a particular solution Let a(p)

n=K·2nbe a particular

solution to the non-homogeneous part of the recurrence relation. Substitute

a(p)

ninto the recurrence relation:

K·2n= 3(K·2n−1)−2(K·2n−2)+2n.

Solving for K, we get K=2n

2. Therefore, a particular solution is a(p)

n= 2n+1.

Step 3: Combine solutions The general solution to the non-homogeneous

recurrence relation is the sum of the homogeneous and particular solutions:

an=a(h)

n+a(p)

n=C1·1n+C2·2n+ 2n+1.

Step 4: Apply initial conditions Using the initial conditions a0= 1 and

a1= 3:

a0=C1+C2+ 2 = 1 =⇒C1+C2=−1,

a1=C1·1 + C2·2 + 4 = 3 =⇒C1+ 2C2=−1.

Solving the system of equations, we find C1=−3 and C2= 2. Therefore, the

closed-form expression for anis:

an=−3+2·2n+ 2n+1 =−3+2n+ 2n+1.

Question 33

Question

Find a closed-form solution to the following non-homogeneous recurrence rela-

tion:

an= 2an−1+ 3n, a0= 1

Solution

To solve the non-homogeneous recurrence relation, we first solve the corre-

sponding homogeneous part and then find a particular solution for the non-

homogeneous part.

Step 1: Find the homogeneous solution We consider the homogeneous

part:

an= 2an−1

The characteristic equation is r−2 = 0, which has the root r= 2. Thus,

the homogeneous solution is:

a(h)

n=c·2n

Step 2: Find a particular solution Let’s find a particular solution for

the non-homogeneous part of the recurrence relation. We assume the particular

solution takes the form a(p)

n=A·3n.

Substitute this trial solution into the non-homogeneous recurrence relation:

A·3n= 2 ·A·3n−1+ 3n

A·3n= 2A·3n+ 3n

A=1

Therefore, the particular solution is a(p)

n=1

3·3n= 3n−1.

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=c·2n+ 3n−1

Step 4: Apply the initial condition Given a0= 1:

a0=c·20+ 30−1=c+1

3= 1

c=2

Therefore, the closed-form solution to the non-homogeneous recurrence re-

lation is:

an=2

3·2n+ 3n−1

Question 34

Question

Consider the recurrence relation defined by an= 2an−1−2an−2+nfor 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=rnand substitute it into the recurrence relation:

rn= 2rn−1−2rn−2⇒r2−2r+ 2 = 0

The characteristic equation is r2−2r+ 2 = 0, which has roots r= 1 ±i. Thus,

the homogeneous solution is of the form ah=c1(1 + i)n+c2(1 −i)n.

Step 2: Find the particular solution to the non-homogeneous part. Assume

an=An +Band substitute it into the recurrence relation:

An +B= 2(A(n−1) + B)−2(A(n−2) + B) + n

Simplify to get A=−2, B= 3. Therefore, the particular solution is ap=

−2n+ 3.

Step 3: Combine the homogeneous and particular solutions. The general

solution is given by an=ah+ap:

an=c1(1 + i)n+c2(1 −i)n−2n+ 3

Step 4: Use the initial conditions to solve for c1and c2.

a0=c1+c2−0 + 3 = 1 and a1=c1(1 + i) + c2(1 −i)−2 + 3 = 2

Solving the system of equations, we find c1=1−i

2and c2=1+i

Step 5: Substitute the values of c1and c2back into the general solution to

get the closed-form expression.

∴an=1−i

2(1 + i)n+1 + i

2(1 −i)n−2n+ 3

Question 35

Question

Let ansatisfy the following recurrence relation:

an+2 = 6an+1 −9an+ 2n

with initial conditions a0= 1 and a1= 4. Find a formula for anfor all

non-negative integers n.

Solution

To solve this recurrence relation, we first find the homogeneous solution by

setting the right-hand side equal to 0:

an+2 −6an+1 + 9an= 0

r2−6r+ 9 = 0

(r−3)2= 0

This gives us a repeated root r= 3. So, our homogeneous solution is of the

form a(h)

n=c1·3n+c2·n·3n.

Next, we find a particular solution a(p)

nfor the non-homogeneous part 2n.

Since 2nis of the form A·rnwhere r= 2 is not a root of the homogeneous part,

we can try a particular solution of the form a(p)

n=A·2n. Substituting this into

the recurrence relation, we get:

2n+2 = 6 ·2n+1 −9·2n

This gives 4A= 12 −9, so A= 1.5. Thus, our particular solution is a(p)

1.5·2n.

Therefore, the general solution to the non-homogeneous recurrence relation

is:

an=a(h)

n+a(p)

n=c1·3n+c2·n·3n+ 1.5·2n

Using the initial conditions a0= 1 and a1= 4, we can solve for c1and c2:

a0=c1+ 1.5 = 1 =⇒c1=−0.5

a1= 3c1+ 3c2+ 3 = 4 =⇒c2= 1

Thus, the formula for anfor all non-negative integers nis:

an=−0.5·3n+ 1 ·n·3n+ 1.5·2n

MATH 117 - ELEMENTS OF MATHEMATICS Homogeneous and non-homogeneous recurrence relations Question Bank Set 3

Students also viewed