Characteristic polynomial - 2: gen func vs matrix

I do not actually understand how it appears over and over again. But, I see two ways to get it. Suppose an equation $a_{n+1} = 3a_n + 2$. You can get $a_n$ using generating functions.

In generating functions

Let $\sum_0 {a_n x^n} = a(x)$. Then, left hand turns into $$\sum_0 {a_{n+1}x^n} = {\sum_0 {a_{n+1}x^{n+1}} \over x} = {\sum_1 {a_{n}x^{n}}\over x} = {\sum_0 {a_{n}x^{n}} - a_0 \over x} = (a(x) - a_0)/x$$ and $$2 + 2x + 2x^2 + \cdots = 2\sum_0 {x^n} = {2 \over 1-x}.$$

That is, recurrence $a_{n+1} = 3a_n + 2$ turns into

$${a(x) - a_0 \over x} = 3a(x) + {2 \over 1-x}$$

or

$$a(x) = {1 \over 1-3x} ({2x \over 1-x} + a_0) = {a_0+1 \over 1-3x} - {1 \over 1-x} = (a_0+1)\sum_0 {3^n x^n} - \sum_0{x^n}$$

which determines $a_n = (a_0+1)3^n -1.$

Please note that we had characteristic polynomial $(1-3x)(1-x)$ in the denominator. The eignevalues are also obvious from the system graph:

Feedback $s=3$ exponentiates the node $a$ while feedback $s=1$ keeps input 2 constant. But, though $2/(1-x)$ comes up from the very beginning, we had to solve for $a(x)$ for the second eigenvalue, $1-3x$ to appear in the equation.

As matrix eigenvalues

Alternatively, $x_{n+1} = 3x_n + 2$ can be written as a system

$$\begin{bmatrix}x_2\\1\end{bmatrix}  = \begin{bmatrix} 3 &2 \\0 & 1\end{bmatrix} = \begin{bmatrix} x_1 \\ 1 \end{bmatrix} = s\,\begin{bmatrix}x_1\\1\end{bmatrix} $$

The eigenvalues, $s$, can be found solving

$$\begin{vmatrix} 3-s &2 \\0 & 1-s\end{vmatrix} = 0 = (3-s)(1-s)$$
yeilding two eigenvalues. With corresponding eigenvectors,  $\begin{bmatrix} 1\\0\end{bmatrix}$ and $\begin{bmatrix} -1 \\1\end{bmatrix}$, we can form the eigenmatrix $S = \begin{bmatrix} 1 & -1 \\0 & 1\end{bmatrix}$ and its inverse $S ^{-1} = \begin{bmatrix} 1 & 1 \\0 & 1\end{bmatrix}$. This allows to compute n-th vector quickly:

$$\begin{bmatrix}x_{n}\\1\end{bmatrix} = X_{n} =  \begin{bmatrix} 3 &2 \\0 & 1\end{bmatrix}^n X_0 = S \Lambda^n S^{-1} X_0 =$$

$$ = \begin{bmatrix} 1 & -1 \\0 & 1\end{bmatrix} \, \begin{bmatrix} 3^n & 0 \\0 & 1^n\end{bmatrix} \, \begin{bmatrix} 1 & -1 \\0 & 1\end{bmatrix}  X_0 = \begin{bmatrix} 3^n & 3^n-1 \\0 & 1^n \end{bmatrix} \begin{bmatrix}x_0\\1\end{bmatrix}$$

 This gives the same result, $$x_n = x_0 3^n + 3_n - 1 = (x_0+1) 3^n - 1$$ you've seen above.

This time, characteristic polynomial appeared because of $A - \lambda I$ matrix determinant.

Analysys

In either case we have obtained $a_n = (a_0+1) 3^n - 1^n$. This corresponds to the idea that solution is a combination of eigenvalues, $x_n = x_{01} \lambda_1^n + x_{02} \lambda_2^n + \cdots$, similarly to n-th order matrix, $\vec x_n = A^n \vec x_0 = A^n [x_{01} \vec e_1 + x_{02} \vec e_2 + \cdots] = $ $ = x_{01} \lambda_1^n \vec e_1 + x_{02} \lambda_2^n \vec e_2 + \cdots = S \Lambda^n S^{-1} \vec x_0.\ \ $. I've used $x_{0i}$ for coefficients in order to highlight that they are determined by initial value). The polynomials are not exactly equal, though.  The polynomial (1-3x)(1-x), which appears in the denominator of generating function a(x)is not equal to the determinant of the matrix, (3−s)(1−s). The roots x, 1/3 and 1, are reciprocal of the real eigenvalues s = 3 and 1.  The coefficients  next to x are the  eigenvalues. GENERATING FUNCTIONS by MIGUEL A. LERMA  calls the (1-3x)(1-x) = 1-4x+3x² a reciprocal of the characteristic polynomial 3-4s+2s². The reference is worth to read because it provides a way of spotting the sequence $a_n$ generating function instead of building it. The reciprocal polynomials are also called (clique or dependence polynomials) You get it by (3-4s+2s²)x² = (3-4x⁻¹+2x⁻²)x² = 3x²-4x¹+2.

If the characteristic polynomial is a determinant of the matrix |A-sI|, the reciprocal polynomial is determinant of the matrix |I-xA|.