Linear Recurrence Relations

A linear recurrence relation is an equation that relates a term in a sequence or a multidimensional array to previous terms using recursion. The use of the word linear refers to the fact that previous terms are arranged as a 1st degree polynomial in the recurrence relation.

A linear recurrence relation is an equation that defines the \(n^\text{th}\) term in a sequence in terms of the \(k\) previous terms in the sequence. The recurrence relation is in the form:

\[x_n=c_1x_{n-1}+c_2x_{n-2}+\cdots+c_kx_{n-k}\]

Where each \(c_i\) is a constant coefficient.

A solution to a recurrence relation gives the value of \(x_n\) in terms of \(n\), and does not require the value of any previous terms.

Solve the recurrence relation: \(x_1=3,\ x_n=3x_{n-1}\)

---

Each term in the sequence can be calculated with a previous term. The first term, \(x_1=3\), is given.

The next term can be calculated using the relation: \(x_n=3x_{n-1}\)

\[x_2=3x_1=9\]

This process is repeated with subsequent terms:

\[x_3=3x_2=27\]

\[x_4=3x_3=81\]

One might notice a pattern at this point. These are powers of 3.

Thus, the solution is \(x_n=3^n\) for all positive integers \(n\).

Geometric series (or combinations, as we will see) are usually the solutions to recurrences. Now, let us say we have a recurrence \[x_n=c_1x_{n-1}+c_2x_{n-2}+\cdots+c_kx_{n-k}\] and a solution \(x_n=ar^n\).

Plugging in, we get \[ar^n=c_1ar^{n-1}+c_2ar^{n-2}+\cdots+c_kar^{n-k}.\] Since \(a,r\neq 0\), we can divide by \(ar^{n-k}:\) \[r^k=c_1r^{k-1}+c_2r^{k-2}+\cdots+c_k.\] Moving the terms over, we get \[r^k-c_1r^{k-1}-c_2r^{k-2}-\cdots-c_k=0,\] which is a polynomial in \(r\), so the solution satisfies the recurrence only if \(r\) 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:

1. Find the characteristic polynomial.
2. Find the roots \(r_1,r_2,\cdots,r_k\) of the characteristic polynomial.
3. Assuming no multiple roots, the closed-form expression will look like \[x_n=a_1(r_1)^n+a_2(r_2)^n+\cdots+a_k(r_k)^n\] for some constant \(a\)'s.
4. Use the initial values to find the values of the \(a\)'s.

Let us try an example:

The sequence \(x_n\) is defined by \(x_0=1\), \(x_1=3\), and \(x_n=5x_{n-1}+6x_{n-2}\) for all \(n\ge 2\). Find a closed-form expression for \(x_n\).

---

The characteristic polynomial is found by letting the lowest indexed term in the recurrence be \(x_k\), and replacing all \(x_i\)'s with \(x^{i-k}\). In this case, \[x_n=5x_{n-1}+6x_{n-2}\implies x^2=5x+6\implies x^2-5x-6=0.\] Factoring the characteristic polynomial, we get roots of \(-1\) and \(6\). Thus, the closed-form expression looks like \[x_n=a_1(-1)^n+a_2(6)^n.\] Plugging in \(n=0\), \[1=a_1+a_2.\] Plugging in \(n=1\), \[3=-a_1+6a_2.\] Solving, we get \(a_1=\frac{3}{7}\) and \(a_2=\frac{4}{7}\), and the closed-form expression is \[x_n=\dfrac{3}{7}(-1)^n+\dfrac{4}{7}(6)^n.\] This can be verified by plugging it into the recurrence. \(_\square\)

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 \[x_n=c_1x_{n-1}+c_2x_{n-2}+\cdots+c_kx_{n-k},\] where all the \(c\)'s are constants, and whose characteristic polynomial, \(r^k-c_1r^{k-1}-c_2r^{k-2}-\cdots-c_k,\) 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 \(x_0=0,\) \(x_1=1,\) and \(x_n=4x_{n-1}-4x_{n-2}\) for all \(n\geq 2\). Find the closed-form of \(x_n.\)

---

The characteristic polynomial of this recurrence relation is \(r^2-4r+4.\) By factoring this polynomial and making it zero, we get \(r^2-4r+4=(r-2)^2=0.\) So its only root is 2 that has multiplicity 2. As explained in Linear Recurrence Relations, the sequence \(\alpha_n=2^n\) 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 \(n,\) so the other solution can be \(\beta_n=n2^n.\) We can verify that \(\beta_n\) is also a solution by direct calculation. Indeed, substituting into the right side of the recurrence, we get \[4\beta_{n-1}- 4\beta_{n-2}=4(n-1)2^{n-1}-4(n-2)2^{n-2}=(2n-2)2^{n}-(n-2)2^n=n2^n=\beta_n.\] 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 \[x_n=a_12^n+a_2 n2^n=2^n(a_1+a_2n).\] As we saw in Linear Recurrence Relations, we can use the given initial values of \(x_n\) when \(n=0\) and \(n=1,\) to find \(a_1\) and \(a_2.\) Making \(n=0\) and \(n=1,\) respectively, in the previous equation, we get the equations \(a_1=0\) and \(2a_1+2a_2=1.\) Using the substitution method, we get that \(a_1=0\) and \(a_2=\frac{1}{2}\). So the resulting formula for \(x_n\) is \[x_n=n2^{n-1}. \ _\square\]

In the process of solving a linear recurrence with repeated roots, if \(r\) is a root of the characteristic polynomial with multiplicity \(k>1,\) then we need to consider the sequences \(r^n, \) \(nr^n, \)\(n^2r^n,\) \(\cdots,\) \(n^{k-1}r^n\) as part of the closed form of the solution of the recurrence. Now we can explain the general method.

1. Find the characteristic polynomial (degree \(k\)).

2. Find all roots of the characteristic polynomial \(r_1, r_2, \cdots, r_m,\) where \(m\leq k\) with multiplicities \(l_1, l_2, \cdots , l_m,\) respectively.

3. The closed-form expression of the solution can be expressed as a linear combination of all the sequences of the form \(n^j r_i^n,\) where \(0\leq j\leq l_i-1\) and \(1\leq i \leq m.\)

4. 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 \(3^\text{rd}\) degree characteristic polynomial and one repeated root:

A sequence \(x_n\) is defined by \(x_0=-1,\) \(x_1=0,\) \(x_2=1\) and the recurrence relation \[x_n=6x_{n-1}-12x_{n-2}+8x_{n-3}.\] Find the closed-form of \(x_n.\)

---

The characteristic polynomial of the given recurrence relation is \(r^3-6r^2+12r-8=(r-2)^3.\) So it has only one root, \(r=2,\) 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 \(x_n\) will be \(x_n=a_12^n+a_2n2^n+a_3n^22^n.\) Now, what remains to do is the step 4.

We are going to find \(a_1, \) \(a_2,\)and \( a_3\) using the initial values. Making \(n=0, 1,\) and \(2,\) respectively, in the formula of \(x_n\) obtained above, we get the equations \(a_1=-1,\) \(2a_1+2a_2+2a_3=0,\) and \(4a_1+8a_2+16a_3=1.\) Solving the system formed by these three equations, we obtain \(a_1=-1,\) \(a_2=\frac{11}{8},\) and \(a_3=-\frac{3}{8}. \) So the closed-form of \(x_n\) is \[x_n=-\frac{2^n}{8}(3n^2-11n+8).\ _\square\]

The following is an example of solving a recurrence with a \(3^\text{rd}\) degree characteristic polynomial with two roots, one of which has multiplicity 2.

A sequence \(x_n\) is defined by \(x_0=1,\) \(x_1=1,\) \(x_2=2\) and the recurrence relation \[x_n=4x_{n-1}+3x_{n-2}-18x_{n-3}.\] Find the closed-form of \(x_n.\)

---

The characteristic polynomial of the given recurrence relation is \(r^3-4r^2-3r+18=(r-3)^2(r+2).\) So it has only two roots, \(r=3\) with multiplicity 2, and \(r=-2\) with multiplicity 1. Then the closed-form of \(x_n\) will look like \(x_n=a_13^n+a_2n3^n+a_3(-2)^n.\) Using this expression and the given initial values, we can find \(a_1, \) \(a_2,\)and \( a_3\). Indeed, let us make \(n=0, 1,\) and \(2,\) respectively, in the formula obtained for \(x_n,\) then we get the equations \(x_0=a_1+a_3=1,\) \(x_1=3a_1+3a_2-2a_3=1,\) and \(x_2=9a_1+18a_2+4a_3=2.\) Solving the system formed by these three equations, we obtain \(a_1=\frac{4}{5},\) \(a_2=-\frac{1}{3},\) and \(a_3=\frac{1}{5}. \) So the closed-form of \(x_n\) is \[x_n=\frac{1}{15}\left[(12-5n)3^n+3(-2)^n\right]. \ _\square\]

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 \(x_n\) is defined by \(x_0=0,\) \(x_1=1,\) and the recurrence relation \[x_n=x_{n-1}- 4x_{n-2}.\] Find the closed-form of \(x_n.\)

---

The characteristic polynomial of the given recurrence is \(r^2=r-4\) Since the solutions of this equation are \[r=\frac{1\pm i \sqrt{15}}{2}= 2e^{\pm i \theta},\] where \(\theta= \arctan \sqrt{15}\) ( see Euler's formula here). Then the solutions of the recurrence can be expressed as linear combination of \(2^n \frac{(e^{in\theta}+e^{-in\theta})}{2}=2^n \cos{n\theta}\) and \(2^n \frac{(e^{in\theta}-e^{-in\theta})}{2i}=2^n \sin{n\theta}, \) therefore \[x_n= c_1 2^n \cos(n \theta)+c_{2} 2^n \sin (n \theta).\]

Now using that \(x_0=0,\) and \(x_1=1,\) we get the following two equations: \(c_1=0\) and \(2c_1 \cos \theta +2c_2 \sin\theta =1,\) where \(\cos \theta =1/4\) and \( \sin \theta =\sqrt{15}/4.\) By solving this system, we obtain that \(c_1=0\) and \(c_2= \frac{2}{\sqrt{15}}.\) Therefore, the closed form of the sequence is \(x_n= \frac{2^{n+1}}{\sqrt{15}} \sin{(n \theta)},\) where \(\theta= \arctan \sqrt{15}. \:\:_\square\)

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 \(x_n=px_{n-1}+qx_{n-2}\) for any natural number \(n\geq 3.\) The characteristic polynomial of this recurrence is \(r^2-pr-q\) and let us assume that \(p^2+4q<0.\) Then the characteristic polynomial has two complex conjugate solutions \(a+bi\) and \(a-bi.\) Of course, we might use the sequences \((a+bi)^n\) and \((a-bi)^n\) 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 \[c_n=\frac{(a+bi)^n+(a-bi)^n}{2} \:\text{and} \: d_n=\frac{(a+bi)^n-(a-bi)^n}{2i}. \] Those two sequences can be also written in the trigonometric form. Indeed, let us assume that \(\rho =\sqrt{a^2+b^2}\) and \(\theta\) is an angle such that \(\sin \theta=\frac{b}{\sqrt{a^2+b^2}}\) and \(\cos \theta=\frac{a}{\sqrt{a^2+b^2}}.\) Then using De Moivres Theorem, we obtain that \(c_n= \rho^n \cos(n \theta)\) and \(d_n=\rho^n\sin(n\theta).\) 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 \(c_n\) and \(d_n.\) That is, any such a sequence can be represented as \(x_n= c_1 \rho^n \cos(n \theta)+c_2\rho^n\sin(n\theta).\)

We can get a recurrence relation for a sequence \((x_n)_{n=0}^\infty\) when its closed-form is given in the form of a linear combination of terms of the form \(n^js^n,\) where \(j\) is a non-negative integer, and \(s\) is any real or complex number. For any such number \(s,\) we denote by \(j_s\) the largest value of \(j\) such that \(n^j s^n\) is one of the terms of the linear combination mentioned above, then the \(s\) is a root of multiplicity \(j_s+1\) 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 \(x_n=(-3)^n (3+4n)+n^22^n.\)

---

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 \((r+3)^2(r-2)^3.\) Expanding it, we get \( r^5-15 r^3+10 r^2+60 r-72.\) Therefore, the corresponding recurrence will be \[x_n=15x_{n-2}-10x_{n-3}-60x_{n-4}+72x_{n-5}. \ _\square\]