edited by
824 views
1 votes
1 votes
What will be solution of recurrence relation if roots are like this: r1=-2, r2=2, r3=-2, r4=2
is this the case of repetitive roots?
edited by

2 Answers

1 votes
1 votes
Yes, this is a case of repetitive roots because the roots r1=-2 and r3=-2 are repeated, and the roots r2=2 and r4=2 are also repeated. When a characteristic equation has repetitive roots, the solution to the corresponding homogeneous linear recurrence relation has an additional term that includes a polynomial factor of the corresponding root.

To find the solution of the recurrence relation with these roots, we can write it in the form:

a(n) = c1 * (-2)^n + c2 * n * (-2)^n + c3 * 2^n + c4 * n * 2^n

where c1, c2, c3, and c4 are constants that depend on the initial conditions of the recurrence relation.

To find the values of the constants, we need to use the initial conditions. Let's assume that the initial values of the sequence are a0, a1, a2, and a3. Then, we have:

a0 = c1 + c3 a1 = -2c1 - 2c2 + 2c3 + 2c4 a2 = 4c1 + 8c2 + 4c3 + 16c4 a3 = -8c1 - 24c2 + 8c3 + 48c4

Solving this system of linear equations for c1, c2, c3, and c4, we get:

c1 = (a0 + 2a1 + a2 - 2a3) / 16 c2 = (a3 - a2 - 4c1) / 16 c3 = (a0 - c1) c4 = (a1 - 2c1 - 2c2 - 2c3) / 4

Substituting these values into the equation for a(n), we get the solution to the recurrence relation:

a(n) = [(a0 + 2a1 + a2 - 2a3) / 16] * (-2)^n + [(a3 - a2 - 4[(a0 + 2a1 + a2 - 2a3) / 16]) / 16] * n * (-2)^n + (a0 - [(a0 + 2a1 + a2 - 2a3) / 16]) * 2^n + [(a1 - 2[(a0 + 2a1 + a2 - 2a3) / 16] - 2[(a3 - a2 - 4[(a0 + 2a1 + a2 - 2a3) / 16]) / 16] - (a0 - [(a0 + 2a1 + a2 - 2a3) / 16])) / 4] * n * 2^n

So, the solution to the recurrence relation with repetitive roots r1=-2, r2=2, r3=-2, r4=2 is:

a(n) = [(a0 + 2a1 + a2 - 2a3) / 16] * (-2)^n + [(a3 - a2 - 4[(a0 + 2a1 + a2 - 2a3) / 16]) / 16] * n * (-2)^n + (a0 - [(a0 + 2a1 + a2 - 2a3) / 16]) * 2^n + [(a1 - 2[(a0 + 2a1
0 votes
0 votes
if root 2 is repeated for 2 times then A.2^n+B.n.2^n
like that for root = -2

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
2 answers
2
Lakshman Bhaiya asked Oct 5, 2018
1,404 views
Let $T(n) = T(n-1) + \frac{1}{n} , T(1) = 1 ;$ then $T(n) = ? $$O(n^{2})$$O(logn)$$O(nlogn)$$O(n^{2}logn)$
22 votes
22 votes
1 answer
3
P C asked Dec 31, 2022
1,491 views
What is the recurrence relation for the ternary strings of length $n$ which can be constructed using 0,1 or 2 only such that the number of 0’s and number of 1's is od...
0 votes
0 votes
0 answers
4