Induction Use induction to verify the candidate solution to

Induction

Use induction to verify the candidate solution to each of the following recurrence equations. t_n = 4t_n-1 for n greaterthan 1 t_1 = 3 The candidate solution is t_n = 3(4^n-1). t_n = t_n-1 + n for n greaterthan 1 t_1 = 1 The candidate solution is t_n = n(n+1)/2. t_n = 3t_n-1 + 2^n for n greaterthan 1 t_1 = 1 The candidate solution is t_n = 5(3^n-1) - 2^n+1.

Solution

a)

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ⁿ

^b)

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ⁿ

^c)

The characteristic equation of the recurrence relation is

x² 2x 2 = 0

Hence, the roots are

x₁ = 1 + i andx₂ = 1 i

In polar form,

x₁ = r andx₂ = r ( ), where r = 2 and = / 4

The roots are imaginary. So, this is in the form of case 3.

Hence, the solution is

F_n = (2 )ⁿ (a cos(n. / 4) + b sin(n. / 4))

1 = F₀ = (2 )⁰ (a cos(0. / 4) + b sin(0. / 4) ) = a

3 = F₁ = (2 )¹ (a cos(1. / 4) + b sin(1. / 4) ) = 2 ( a/2 + b/2)

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

Hence, the final solution is

F_n = (2 )n (cos(n. / 4) + 2 sin(n. / 4))