Find Linear Recurrence Operator Given Solutions
A solution to a recurrence relation gives the value of in terms of , and does not require the value of any previous terms.
Solve the recurrence relation:
Each term in the sequence can be calculated with a previous term. The first term, , is given.
The next term can be calculated using the relation:
This process is repeated with subsequent terms:
One might notice a pattern at this point. These are powers of 3.
Thus, the solution is for all positive integers .
Geometric series (or combinations, as we will see) are usually the solutions to recurrences. Now, let us say we have a recurrence and a solution .
Plugging in, we get Since , we can divide by Moving the terms over, we get which is a polynomial in , so the solution satisfies the recurrence only if is a root of this polynomial. This polynomial is called the characteristic polynomial of the recurrence.
Also, note that if two geometric series satisfy a recurrence, the sum of them also satisfies the recurrence. Then, we can find the following method for solving recurrences:
- Find the characteristic polynomial.
- Find the roots of the characteristic polynomial.
- Assuming no multiple roots, the closed-form expression will look like for some constant 's.
- Use the initial values to find the values of the 's.
Let us try an example:
The sequence is defined by , , and for all . Find a closed-form expression for .
The characteristic polynomial is found by letting the lowest indexed term in the recurrence be , and replacing all 's with . In this case, Factoring the characteristic polynomial, we get roots of and . Thus, the closed-form expression looks like Plugging in , Plugging in , Solving, we get and , and the closed-form expression is This can be verified by plugging it into the recurrence.
Problems:
1. Make up your own recurrences and solve them!
Click here for more on this topic. Thanks for reading!
In the wiki Linear Recurrence Relations, linear recurrence is defined and a method to solve the recurrence is described in the case when its characteristic polynomial has only roots of multiplicity one. This wiki will introduce you to a method for solving linear recurrences when its characteristic polynomial has repeated roots. That is, when some of the roots can have multiplicities higher than one.
A linear recurrence with repeated roots is a linear recurrence of the form where all the 's are constants, and whose characteristic polynomial, may have repeated roots, that is, roots with multiplicity higher than 1. We are going to explain how the method explained in Linear Recurrence Relations can be modified to solve this other linear recurrence relations too. Let us consider an example before explaining the method in general.
Recurrence Relation with only One Repeated Root
A sequence is defined by and for all . Find the closed-form of
The characteristic polynomial of this recurrence relation is By factoring this polynomial and making it zero, we get So its only root is 2 that has multiplicity 2. As explained in Linear Recurrence Relations, the sequence is one of the solutions. Since the order of the recurrence, which is also equal to the degree of the characteristic polynomial, is 2, we need to get another independent solution. In this case, the other solution can be obtained just by multiplying the given solution by so the other solution can be We can verify that is also a solution by direct calculation. Indeed, substituting into the right side of the recurrence, we get Now the closed-form solution can be expressed as a linear combination of both solutions. It means that the general solution can be written as As we saw in Linear Recurrence Relations, we can use the given initial values of when and to find and Making and respectively, in the previous equation, we get the equations and Using the substitution method, we get that and . So the resulting formula for is
In the process of solving a linear recurrence with repeated roots, if is a root of the characteristic polynomial with multiplicity then we need to consider the sequences as part of the closed form of the solution of the recurrence. Now we can explain the general method.
-
Find the characteristic polynomial (degree ).
-
Find all roots of the characteristic polynomial where with multiplicities respectively.
-
The closed-form expression of the solution can be expressed as a linear combination of all the sequences of the form where and
-
Use the initial values of to find the constants used as coefficients of the linear combination.
The following is an example of solving a recurrence with a degree characteristic polynomial and one repeated root:
A sequence is defined by and the recurrence relation Find the closed-form of
The characteristic polynomial of the given recurrence relation is So it has only one root, with multiplicity 3. So we have accomplished the steps 1 and 2 of the general method described above. According to the step 3, the closed-form of will be Now, what remains to do is the step 4.
We are going to find and using the initial values. Making and respectively, in the formula of obtained above, we get the equations and Solving the system formed by these three equations, we obtain and So the closed-form of is
The following is an example of solving a recurrence with a degree characteristic polynomial with two roots, one of which has multiplicity 2.
A sequence is defined by and the recurrence relation Find the closed-form of
The characteristic polynomial of the given recurrence relation is So it has only two roots, with multiplicity 2, and with multiplicity 1. Then the closed-form of will look like Using this expression and the given initial values, we can find and . Indeed, let us make and respectively, in the formula obtained for then we get the equations and Solving the system formed by these three equations, we obtain and So the closed-form of is
We will also explain here how to proceed in the case that some of the roots of the characteristic polynomial of a given linear recurrence are complex non-real numbers. Let us illustrate this with an example.
A sequence is defined by and the recurrence relation Find the closed-form of
The characteristic polynomial of the given recurrence is Since the solutions of this equation are where ( see Euler's formula here). Then the solutions of the recurrence can be expressed as linear combination of and therefore
Now using that and we get the following two equations: and where and By solving this system, we obtain that and Therefore, the closed form of the sequence is where
We can generalize the procedure used in the previous example to any second order linear recurrence for which the characteristic polynomial has two complex conjugate roots. Let us assume that we wish to solve the linear recurrence for any natural number The characteristic polynomial of this recurrence is and let us assume that Then the characteristic polynomial has two complex conjugate solutions and Of course, we might use the sequences and to generate all possible solutions of the recurrence. But these are complex-valued sequences. To get real-valued solutions it would more convenient to consider the sequences defined by the formulas Those two sequences can be also written in the trigonometric form. Indeed, let us assume that and is an angle such that and Then using De Moivres Theorem, we obtain that and Now it can be proved that any real-valued sequence that is a solution of the given recurrence can be express as a linear combination of and That is, any such a sequence can be represented as
We can get a recurrence relation for a sequence when its closed-form is given in the form of a linear combination of terms of the form where is a non-negative integer, and is any real or complex number. For any such number we denote by the largest value of such that is one of the terms of the linear combination mentioned above, then the is a root of multiplicity of the characteristic polynomial of the given linear recurrence. Therefore, from the closed-form of the sequence we can get all roots of the characteristic polynomial of the recurrence relation and their multiplicities, which allows us to find the characteristic polynomial, and thus the recurrence relation.
The following is an example where we have to find the recurrence given the closed-form:
Find a recurrence for the sequence
According to our comment above, the numbers -3 and 2 are roots of the characteristic polynomial of the desired recurrence with multiplicities 2 and 3, respectively. Then the polynomial can be Expanding it, we get Therefore, the corresponding recurrence will be
For the given values of the numbers for it is true that for Find
Clarification: .
For the given sequence we know that and
If where and are coprime positive integers, find
See Part 1.
Find if the real numbers , , , and satisfy the equations
Find if the numbers and satisfy the following equations: and
Inspiration.
A polynomial has degree and for
Find
Find Linear Recurrence Operator Given Solutions
Source: https://brilliant.org/wiki/linear-recurrence-relations/