Using Recurrence Characteristic Equation Write a recurrence

Using Recurrence (Characteristic Equation)

Write a recurrence equation for the nth term of the sequence 2, 6, 18, 54, ..., and use induction to verify the candidate solution s_n = 2(3^n-1). Solve the following recurrence equations using the characteristic equation. t_n = 4t_n-1 - 3t_n-2 for n > 1 t_0 = 0 t_1 = 1 t_n = 5t_n-1 - 6t_n-2 + 5^n for n > 1 t_0 = 0 t_1 = 1 Solve the following recurrence equations using the characteristic equation. t_n = 6t_n-1 - 9t_n-2 for n > 1 t_0 = 0 t_1 = 1 Solve the following recurrence equations using the characteristic equation. T(n) = 2T(n/3) + log_3 n for n > 1, n a power of 3 T(1) = 0

Solution

2)

The characteristic equation of the recurrence relation is

x² 5x + 6 = 0,

So, (x 3) (x 2) = 0

Hence, the roots are

x₁ = 3 and x₂ = 2

The roots are real and distinct. So, this is in the form of case 1

Hence, the solution is

F_n = ax₁ⁿ + bx₂ⁿ

Here, F_n = a3ⁿ + b2ⁿ (As x₁ = 3 and x₂ = 2)

Therefore,

1 = F₀ = a3⁰ + b2⁰ = a+b

4 = F₁ = a3¹ + b2¹ = 3a+2b

Solving these two equations, we get a = 2 and b = 1

Hence, the final solution is

F_n = 2.3ⁿ + (1) . 2ⁿ = 2.3ⁿ 2ⁿ

¹²⁾

The characteristic equation of the recurrence relation is

x² 10x 25 = 0,

So, (x 5)² = 0

Hence, there is single real root x₁ = 5

As there is single real valued root, this is in the form of case 2

Hence, the solution is

F_n = ax₁ⁿ + bnx₁ⁿ

3 = F₀ = a.5⁰ + b.0.5⁰ = a

17 = F₁ = a.5¹ + b.1.5¹ = 5a+5b

Solving these two equations, we get a = 3 and b = 2/5

Hence, the final solution is

F_n = 3.5ⁿ + (2/5) .n.2ⁿ