They say that solutions of recurrence relations are combinations of exponential functions, the series like [1 a a^2 a^3 and etc].

I know that the difference operators have a matrix like

$$\begin{bmatrix} -1 & 1 & 0 & 0 & \cdots \\ 0 & -1 & 1 & 0 & \cdots \\ 0 & 0 & -1 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$

where you have $-1 +1$ on the main diagonal. It is easy to see that any vector of the form $[1\ a\ a^2\ a^3\ a^4\ \ldots]$ is an eigenvector with eigenvalue $(a-1)$. Note that every component is $a$ times the other component. I have noted that the same is true for the solutions of difference equations. That is, as Wikipedia says, recurrence $x_n = a x_{n-1} + b x_{n-2} + \cdots$ can be represented in matrix form

$$\vec x_n = \begin{bmatrix}x_n \\ x_{n-1} \\ x_{n-2} \\ \vdots \end{bmatrix} = \begin{bmatrix} a & b & c & \cdots \\ 1 & 0& 0 &\cdots \\ 0 & 1& 0 &\cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}\, \begin{bmatrix} x_{n-1} \\ x_{n-2}\\ x_{n-3} \\ \vdots \end{bmatrix} = A \vec x_{n-1}= A^n \vec x_0.$$ You can find the eigenvalues, $\lambda$, and corresponding eigenvectors, $[\ldots\ \lambda^2 y_0\ \lambda y_0\ \ y_0]^T$, of the companion matrix A. Though Wikipedia does not say that components (or, coordinates?) of the eigenvector must be multiples of each other, I think that it is the whole point of finding the eighenvectors of the companion matrix when solving the equation. It must be so because suppose $[y_{n-1} y_{n-2} y_{n-3}]^T$ is an eigenvector then $[\lambda y_{n-1}\ \lambda y_{n-2}\ \lambda y_{n-3}]^T = [y_{n}\ y_{n-1}\ y_{n-2}]$ is also elso an eigenvector and, it must be clear now that, $$y_n = \lambda y_{n-1}.$$ So, we see again that eigenvectors of recurrence relation are exponential functions, the ones we had as solutions of differential operator.

Is this right? Is there any relationship between difference operators and recurrence relationships? What does it mean that differential operator has any exponent as its eigenvector whereas recurrence of order n has n distinct lambdas and eigenvalue is (λ-1) in first case and λ in the other?

  • $\begingroup$ Do you mean difference operator, that is $\Delta u_n=u_{n+1}-u_n$? $\endgroup$ Dec 6, 2013 at 15:06
  • $\begingroup$ Yes, the matrix with +1-1 on the main diagonal produces $u_{n+1}-u_n$ $\endgroup$
    – Val
    Dec 6, 2013 at 15:10
  • $\begingroup$ I edited: difference operators and differential operators are very different things, especially in this context. $\endgroup$ Dec 6, 2013 at 15:12
  • 1
    $\begingroup$ I'm not sure I can answer your questions in a satisfying way, but here are some observations: the matrix that appears in your method for solving recurrences contains a shift operator (neglecting the top row), not a difference operator. This, I think, explains the eigenvalue of $\lambda$ rather than $\lambda-1.$ $\endgroup$ Dec 7, 2013 at 13:20
  • $\begingroup$ As for your observation that the difference operator has infinitely many eigenvectors (uncountably many, in fact), whereas the matrix that appears in the recurrence problem has only finitely many: the latter is expected, since the matrix is finite-dimensional. When an operator acts on an infinite-dimensional space, as the difference operator does (it acts on the space of all sequences), the situation is much more complicated. See some of the comments and answers to this MO question for some useful information. $\endgroup$ Dec 7, 2013 at 13:26


Your Answer

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

Browse other questions tagged or ask your own question.