4
$\begingroup$

Consider a sequence $(a_n)_{n\in\mathbb N}$ defined by $k$ initial values $(a_1,\dots,a_k)$ and

$$a_{n+k}=c_{k-1}a_{n+k-1}+\dots+c_0a_n$$

for all $n\in\mathbb N$.

What are some ways to get closed forms for $a_n$? What are some ways of rewriting $a_n$ that allows it to be computed without going through all previous values?

For example, we have Binet's formula:

$$F_n=\frac{\phi^n-(-\phi)^{-n}}{\sqrt5}$$

Furthermore, what about simultaneously defined linear recurrences? For example:

$$\begin{cases}a_{n+1}=2a_n+b_n\\b_{n+1}=a_n+2b_n\end{cases}$$

How can these be solved?

See also: Wikipedia: Recurrence relations.


This is being repurposed in an effort to cut down on duplicates; see here:

$\endgroup$
  • 1
    $\begingroup$ one approach involves matrices $\endgroup$ – J. W. Tanner Jan 24 '20 at 14:37
  • $\begingroup$ I am not quite sure I understand. Are you trying to get a standard "homogeneous recurrence relation with constant coefficients" question and accepted/upvoted answer, so that we can all use it to mark the endless particular questions as duplicates? $\endgroup$ – almagest Jan 24 '20 at 14:39
  • $\begingroup$ @almagest That is the purpose of faq's. See the links at the end. I did a decent search and could not find such a question, but a lot of specific cases in (recurrence-relations)'s frequent tab, so decided to make this. $\endgroup$ – Simply Beautiful Art Jan 24 '20 at 14:41
  • $\begingroup$ I would remove the ill defined "If a closed form cannot be explicitly achieved", for being false for a moderate definition of "closed form" and for the question that follows being useful regardless of its truth value. $\endgroup$ – OscarRascal Jan 24 '20 at 14:59
  • $\begingroup$ You can use generating functions. $\endgroup$ – Math1000 Jan 24 '20 at 15:15
3
$\begingroup$

Characteristic/Auxiliary Polynomials

The basic solution

  1. Suppose that $\alpha$ is a root of the associated polynomial $$x^k=c_{k-1}x^{k-1}+c_{k-2}x^{k-2}+\dots+c_0\quad(1)$$ Then it is also true that $$\alpha^{n+k}=c_1\alpha^{n+k-1}+\dots+c_0\alpha^n$$ So $a_n=\alpha^n$ satisfies the recurrence relation (but probably not the initial conditions).

  2. Since the relation is linear, if $\alpha_1,\alpha_2,\dots,\alpha_k$ are the roots of the associated polynomial, then $$a_n=A_1\alpha_1^n+\dots+A_k\alpha_k^n$$ also satisfies the recurrence relation. Provided all $k$ roots are distinct, we can then use the $k$ initial conditions to solve for $A_1,\dots,A_k$.

  3. Suppose that $\alpha$ is a repeated root. Then $\alpha$ is also a root of the derivative and so we have $$kx^{k-1}=c_{k-1}(k-1)x^{k-2}+\dots+c_0\quad(2)$$ Taking $nx^n(1)+x^{n+1}(2)$ we get $$(n+k)x^{n+k}=c_{k-1}(n+k-1)x^{n+k-1}+\dots+c_0nx^n$$ and so $a_n=n\alpha^n$ is satisfies the recurrence relation.

  4. Similarly, we find that if $\alpha$ is a root of order $h$ (so that $(x-\alpha)^h$ divides the polynomial, then $a_n=\alpha^n,n\alpha^n,n^2\alpha^n,\dots,n^{h-1}\alpha^n$ all satisfy the recurrence relation.

  5. So in all cases the associated polynomial gives us $k$ solutions to the recurrence relation. We then take a suitable linear combination of those solutions to satisfy the initial conditions.

Additional points

  1. If often happens that all but one of the roots $\alpha$ of the polynomial satisfy $|\alpha|<1$ which means that their contribution to $a_n$ is negligible except possibly for small $n$. Since the $a_n$ are usually integers, this means we can often express the solution as $\lfloor A\alpha^n\rfloor$ or $\lceil A\alpha^n\rceil$ (where $\alpha$ is the root with $|\alpha|>1$.

  2. We sometimes get simultaneous linear recurrences like the two in the question $$a_{n+1}=2a_n+b_n,b_{n+1}=a_n+2b_n$$ In this case we can eliminate all but one of the sequences, in a similar way to solving ordinary simultaneous equations. In this case we have $b_n=a_{n+1}-2a_n$. Substituting in the other relation; $a_{n+2}-2a_{n+1}=a_n+2a_{n+1}-4a_n$

$\endgroup$
2
$\begingroup$

Matrices

Such recurrences can be computed using matrices. Let $\mathbf a_n=(a_{n+k-1},\dots,a_n)^\intercal$. We can then easily see that the recurrence relation can be rewritten as

$$\mathbf a_{n+1}=C\mathbf a_n\text{ where }C=\begin{bmatrix}c_{k-1}&c_{k-2}&\cdots&c_1&c_0\\1&0&\cdots&0&0\\0&1&\cdots&0&0\\\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&\cdots&1&0\end{bmatrix}=\begin{bmatrix}\mathbf c\\\mathbf e_0\\\mathbf e_1\\\vdots\\\mathbf e_{k-1}\end{bmatrix}$$

where $\mathbf e_i$ has a $1$ at the $i$th entry and $0$ everywhere else. See also: Companion matrix.

Intuitively we're computing the next term (top row), and then setting each entry as the one above it (a rotation of the values in $\mathbf a_n$ per se).

From this we can easily solve the recurrence, as it now becomes:

$$\mathbf a_n=C^n\mathbf a_0$$

and so the problem reduces to raising $C$ to a power. As it is the case that $C$ is diagonalizable, with eigenvalues given by the roots of the characteristic equation, a closed form can then be found. Even if the roots are not nice to compute, or if one wishes to avoid non-integers for an integer sequence, this can still be computed using exponentiation by squaring.

This also easily generalizes to simultaneously defined sequences. Consider the example:

$$\begin{cases}a_{n+1}=2a_n+b_n\\b_{n+1}=a_n+2b_n\end{cases}$$

Let $\mathbf w_n=(a_n,b_n)^\intercal$. We can then rewrite this as

$$\mathbf w_{n+1}=C\mathbf w_n\text{ where }C=\begin{bmatrix}2&1\\1&2\end{bmatrix}$$

and hence

$$\mathbf w_n=C^n\mathbf w_0$$

To show how this gives an explicit solution, we may diagonalize $C$ as

$$C=VDV^{-1}\\\text{where }D=\begin{bmatrix}1&0\\0&3\end{bmatrix},~V=\begin{bmatrix}-1&1\\1&1\end{bmatrix},~V^{-1}=\frac12V$$

and hence

$$\mathbf w_n=V\begin{bmatrix}1&0\\0&3^n\end{bmatrix}V^{-1}\mathbf w_0=\frac12\begin{bmatrix}(a_0+b_0)3^n+(a_0-b_0)\\(a_0+b_0)3^n-(a_0-b_0)\end{bmatrix}$$

which strongly suggests this specific problem can be solved by observing the behavior of $V^{-1}\mathbf w_n$ i.e. $a_n-b_n$ and $a_n+b_n$.

$\endgroup$
2
$\begingroup$

Generating functions / Z-transforms

Generating functions (unilateral Z-transforms) can be used to transform the recurrence into a formal power series by defining:

$$G=\sum_{n=0}^\infty a_nx^n$$

We can then rearrange this to get

$$G=\sum_{n=0}^{k-1}a_nx^n+G\sum_{n=1}^kc_{k-n}x^{n-1}$$

Solving for $G$ then gives a rational function in $x$. By factoring the denominator (which equates to solving the characteristic equation), applying partial fractions, and using the geometric series or Newton's generalized binomial theorem, the general term in the expansion of $G$ can be computed. Alternatively, by using Taylor's series, we know that

$$a_n=\frac{G^{(n)}(0)}{n!}$$

which can be computed directly by differentiating repeatedly, using Leibniz's rule for example.

Example:

The Fibonacci sequence can be solved this way. Recall that $F_0=0$, $F_1=1$, and $F_n=F_{n-1}+F_{n-2}$. Now let us take

$$G=\sum_{n=0}^\infty F_nx^n$$

By algebraic manipulation,

$$G=x+(x+x^2)G$$

$$G=\frac x{1-x-x^2}$$

For multiple simultaneously defined sequences, this simply amounts to multiple generating functions, which when solving amounts interestingly to solving a system of equations of functions. After that the rest is the same as above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.