0
$\begingroup$

We have the recursive relation $x_n = a_{n-1}x_{n-1} + a_{n-2}x_{n-2} + \dots + a_1x_1 + a_0x_0$. Prove that if the polynomial $t^n - a_{n-1}t^{n-1} - a_{n-2}t^{n-2} - \dots - a_1t - a_0$ has distinct roots $\lambda_1, \lambda_2, \dots, \lambda_n$ then $$x_n = c_1\lambda_1^n + c_1\lambda_2^n + \dots + c_n\lambda_n^n$$

Here, coefficients $c_1, c_2, \dots, c_n$ may be calculated from initial values $x_0, x_1, \dots, x_n$.

I'm thinking of finding some matrix $A$ then looking for eigenvalues and eigenvectors so that we can do $A^n$ but I'm stuck.

$\endgroup$
1
  • $\begingroup$ This is a basic result from the theory of linear homogeneous recurrence relations. As $\lambda_i$ is a zero of that polynomial $x_n=\lambda_i^n$ is a solution of the recurrence. Because the $\lambda_i$s are distinct, those $n$ solutions are linearly independent (Vandermonde). Therefore you can write any initial segment $(x_0,x_1,\ldots,x_{n-1})$ as a linear combination. After that we are basically done. $\endgroup$ – Jyrki Lahtonen Nov 25 '18 at 8:03
1
$\begingroup$

One of the easiest approach: observe that the sequence space $$S =\{(x_n)_{n\geq 0}\;|\;x_{k+n} = a_{n-1}x_{n+k-1} + \cdots + a_0 x_k, \;\forall k\geq 0\}$$ is of dimension $n$ since the whole sequence is determined by $n$-data, $x_0,\ldots x_{n-1}$. And show that $\lambda_j^n, n\geq 0$ forms a linearly independent subset of $S$, and thus forms a basis.
Matrix approach is also valid. Let $y_k = (x_k, \ldots,x_{k-n+1})'$ for $k\geq n-1$. Then for companion matrix $C = (c_{ij})$ s.t. $c_{1j} = a_{n-j}$ and $c_{ij} = 1$ if $i-1 = j$ and $0$ otherwise, for $i\geq 2$, it holds that $$y_{k+1} = C y_k.$$ Then the set of eigenvalues of $C$ is exactly $\{\lambda_j, 1\leq j \leq n\}$ and $C$ is diagonalizable. That is, there is a basis consisting of its eigenvectors. You can see that $y_{n+k-1} = \sum_j c_j \lambda_j^k v_j$ where $v_j$'s are eigenvectors forming basis corresponding to $\lambda_j$ and $y_{n-1}$ is represented as $\sum_j c_j v_j$.

$\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.