Question

Can anyone help me to solve this recurrence? Thanks a lot!

Answer 1

Answer:

S(n) = -(2ⁿ) + 3/5 (-2)ⁿ + 12/5 (3)ⁿ

Step-by-step explanation:

Rearrange:

S(n) − S(n−1) − 6S(n−2) = 2ⁿ

Since the non-homogenous term on the right side is 2ⁿ, we can guess that S(n) has the form a(2ⁿ) + b.

Substitute:

a(2ⁿ) + b − (a(2ⁿ⁻¹) + b) − 6(a(2ⁿ⁻²) + b) = 2ⁿ

a(2ⁿ) + b − a(2ⁿ⁻¹) − b − 6a(2ⁿ⁻²) − 6b = 2ⁿ

a(2ⁿ) − a(2ⁿ⁻¹) − 6a(2ⁿ⁻²) − 6b = 2ⁿ

a(2ⁿ) − 1/2 a(2ⁿ) − 6/4 a(2ⁿ) − 6b = 2ⁿ

(a − 1/2 a − 3/2 a − 1) (2ⁿ) − 6b = 0

(-a − 1) (2ⁿ) − 6b = 0

Matching the coefficients:

a = -1, b = 0

So the general solution is: S(n) = -(2ⁿ).

To find the particular solution, let's first write the characteristic equation:

s² − s − 6 = 0

(s + 2) (s − 3) = 0

s = -2, 3

So the particular solutions are c(-2)ⁿ and d(3)ⁿ.

The whole solution is the sum of the general and particular solutions:

S(n) = -(2ⁿ) + c(-2)ⁿ + d(3)ⁿ

Use the initial conditions to find the coefficients:

S(0) = 2 = -(2⁰) + c(-2)⁰ + d(3)⁰

2 = -1 + c + d

3 = c + d

S(1) = 4 = -(2¹) + c(-2)¹ + d(3)¹

4 = -2 − 2c + 3d

6 = 3d − 2c

Solving the system of equations:

6 = 3(3 − c) − 2c

6 = 9 − 3c − 2c

5c = 3

c = 3/5

d = 12/5

Therefore:

S(n) = -(2ⁿ) + 3/5 (-2)ⁿ + 12/5 (3)ⁿ

Let's check by finding S(2) using both equations.

S(n) = S(n−1) + 6S(n−2) + 2ⁿ

S(2) = S(1) + 6S(0) + 2²

S(2) = 4 + 6(2) + 4

S(2) = 20

S(n) = -(2ⁿ) + 3/5 (-2)ⁿ + 12/5 (3)ⁿ

S(2) = -(2²) + 3/5 (-2)² + 12/5 (3)²

S(2) = -4 + 3/5 (4) + 12/5 (9)

S(2) = -4 + 12/5 + 108/5

S(2) = 20

Looks like it works!