The recurrence
$$f_n = a f_{n-1} + b f_{n-2}$$
has generating function
$$f(x) = {f_0+x(f_1 - a f_0) \over 1-ax - bx^2} = \sum_0^\infty (C_1 \lambda_1 + C_2\lambda_2)x^n = \\ = {1\over \lambda_1 - \lambda_2} ({f_1-f_0\lambda_2 \over 1-\lambda_1 x} + {f_0\lambda_1 - f_1 \over 1-\lambda_2 x}) = {C_1+C_2+x(\lambda_1 C_2 + C_1 \lambda_2) \over 1-(\lambda_1+ \lambda_2)x - \lambda_1\lambda_2\ x^2}$$
which allows to relate initial values with eigendecomposition
$$\begin{matrix}C_1 = {f_1-f_0\lambda_2\over\lambda_1-\lambda_2} & C_2 = {f_0\lambda_1 - f_1\over\lambda_1-\lambda_2} \\
f_0 = C_1 + C_2 & f_1 = C_1\lambda_1 + C_2\lambda_2\end{matrix}.$$
Eigencoordinaces $C_1$ and $C_2$ can be computed either this way or in the course of partial fraction decomposition.
Identifying initial values with inputs
We have just got that our linear system produces non-causal sequence (the output is 0 for n < 0). This sequence is also a solution of the recurrence. It is curious that initial values, $a_0$ and $a_1$ can be identified with inputs. Let's first define left and right shift:
$$R(y) = R(y_0 + y_1 z + y_2 z^2 + \cdots) = 0 + y_0 z + y_1 z^2 + \cdots = a y,$$
$$L(y) = L(y_0 + y_1 z + y_2 z^2 + \cdots) = y_1 + y_2 z + y_3 z^2 + \cdots = (y-y_0)/a,$$
$$R(y)_n = y_{y-1}$$
$$L(y)_n = y_{y+1}$$
Therefore, $y_n = a y_{n-1} + x_n$ can be rewritten as z-transform $Y = y(z) = azy(z) + x(z) = X/(1-az)$ where x is input at time t and output, our sequence, is identically zero if no input is applied. Same result can be obtained from eq $y_{n+1} = a y_{n} + x_{n+1}$:
$$(Y - y_0)/z = aY + (x(z)-x_0)/z \Rightarrow Y - y_0 = azY + (X - x_0) $$
$$\Rightarrow Y = {X + y_0-x_0 \over 1-az} = = {X + y_{-1} \over 1-az} = {X \over 1-az}.$$
The latter is because $y_{-1} = 0$ since we have causal sequences. For the second order system,
$$y_n = a y_{n-1} + b y_{n-2}$$
we have
$$y = a (zy + y_{-1}) + b (z^2y + zy_{-1} + y_{-2}) = {a y_{-1} + by_{-2} + b zy_{-1} \over 1 - az - bz^2} = {y_0 + bzy_{-1} \over 1 - az - bz^2} = 0$$
since $y_{-1} = y_{-1} = 0$ again and we again can add some input X to kick the sequence off zero.
With $y_0 = x_0$ and $y_1 = a y_0 + x_1 \Rightarrow x_1 = y_1 - a y_0$ given,
$$y = {x \over 1 - az - bz^2} = {x_0 + x_1z \over 1 - az - bz^2} = {y_0 + (y_1 - a y_0)z \over 1 - az - bz^2}.$$
$y_1 - a y_0 = b y_{-1},$ which we have before.
In general, equation $a_n y^n + a_{n-1} y^{n-1} + \cdots + a_0 y_0 = b_m x^m + b_{m-1} y^{m-1} + b_0 x_0$ translates into
$Y = {\sum_0^m x_i z_i \over \sum_0^{n-1} a_i z_i} = X\cdot H$ where nominator X can be interpreted as either as input delta-pulses (in case of zero-state interpretation) or initial values (in case of zero-input interpretation).
Consider a system $$y_{n+2} = ay_{n+1} + by_n$$
It is not surprising there for that the system has state representation
You see how every next value of y is computed by summing two previous states. This means that we do not need to store all previous values to compute the next. Two is sufficient. Therefore, we can allocate two numeric registers for two state variables
That is, we initialize registers with $a_0$ and $a_1$. At every clock we update the values. Instead of writing result of $new_value(a_0, a_1)$ into $a_2$, we store it into second register. Value $a_1$ is shifted into the first register, overwriting $a_0$ there. We can do this since we do not need $a_0$ anymore (neither for computing $a_3$, nor $a_4$ and so on), and must do it since $a_1$ is needed for computing $a_3$. Effectively, register values $(a_n, a_{n+1})$ are updated with $(a_{n+1}, a_{n+2})$ at every clock cycle. The order of the system is the number of variables/registers that we need. It is also known as space complexity.
Since transition function is linear, it may be represented in matrix form
$$\begin{bmatrix}y_{n+2} \\ y_{n+1}\end{bmatrix} = \begin{bmatrix} a & b \\ 1 & 0 \end{bmatrix}\, \begin{bmatrix}y_{n+1} \\ y_{n}\end{bmatrix}$$
Space complexity is reduced from n to two. At every clock cycle, newly computed value is written into the most significant register. The less significant registers take their values from the more significant ones (we slide the window: head is computed, tail is discarded). In this example we have only two state registers. They are initialized with initial values, $y_0$ and $y_1$ and we say that "the system has order 2."
1+ox |1-x1- x 1+x+x²+x³+...
x+ox²
x-x²x²+ox³
x²-x³
x³
Ok, you see the pattern, $$\begin{equation} \label{eq:1} {1\over 1-x} = 1 + x + x^2 + x^3 + \ldots \end{equation}.$$ Similarly, we prove that $$\begin{equation}\label{eq:2}{1\over 1+x} = 1-x+x^2-x^3+x^4-x^5+\ldots\end{equation}.$$ What if we add two series together? Yes, $$\begin{equation}\label{eq:3} 2(1+x^2+x^4+x^6+\ldots) = {1\over 1-x} + {1\over 1+x} = {2 \over 1-x^2}.\end{equation}$$ The latter can also be obtained by substitution $a$ for $x^2$ in $2(1+x^2+x^4+x^6+\ldots) = 1 +a +a^2+a^3+\ldots) ={2\over 1-a}= {2\over 1-x^2}$.
In the same vain, we can compute
$$\begin{matrix} \Biggl({1\over 1-x}\Biggr)^2 = {1\over 1-x}\cdot {1\over 1-x} = (1+x+x^2+x^3+\ldots)(1+x+x^2+x^3+\ldots) = \\
(1+x+x^2+x^3+\ldots) +\\ (x+x^2+x^3+x^4+\ldots) +\\ (x^2+x^3+x^4+x^5+\ldots) + \ldots = \\ 1 + 2x + 3x^2 \ldots = \sum_0^\infty{{d\over dx}(x^n)} = \sum_0^\infty{nx^{n-1}} \end{matrix}$$
Similarly, we can prove that $(1-a)\sum_0^{n-1}{a^i} = 1 + a + a^2 + \ldots + a ^ {n-1}- a - a^2 - a^3 - \ldots - a^n = 1-a^n$ or ${1 - a^n \over 1-a} = \sum_0^{n-1}{a^i}.$
Note that $1+x+x^2+x^3+\ldots$ maintains a constant value of 1. That is, \eqref{eq:1} corresponds to a linear system. What is a corresponding linear system?
has a transfer function
which has transfer function $$y = k(F_b\cdot z^{-1}y + x) = {kx \over 1 - z^{-1}kF_b}.$$ Here, $z^{-1}$ is a righward shit $R[a_0, a_1, a_2,\ldots] = z^{-1}[a_0, a_1, a_2,\ldots] = [0,a_0,a_1,a_2,\ldots]$ and $H = {k\over 1-z^{-1}kF_b}$ is the transfer function. Well, the specification is redundant. I can set simply k=1. We have already seen this system for the feedback amplifier Fb=3 and constant input x=2. Here is the generalized matrix form for x=1 and arbitrary Fb
$$\begin{bmatrix} y_n \\ 1\end{bmatrix} = \begin{bmatrix} F_b^n & 1 \\0 & 1\end{bmatrix}^n \, \begin{bmatrix} y_0 \\ 1\end{bmatrix} = S \Lambda^n S^{-1} Y_0 = \begin{bmatrix} 1 & 1\\0 & 1-F_b\end{bmatrix} \, \begin{bmatrix} F_b^n & 0\\0 & 1^n\end{bmatrix} \, \begin{bmatrix} 1 & {-1\over 1-F_b}\\0 & {1\over 1-F_b}\end{bmatrix}\, \begin{bmatrix} y_0 \\ 1\end{bmatrix}$$
You see how y receives constant input, 2 from another state variable, 1, which maintains itself constant. The eigendecomposition fails when y's feedback is 1 because of $1\over 1-Fb$, which is infinite. Yet, the transfer function-based solution, $Y = {X\over 1-z^{-1}} = {2\over (1-z^{-1})^2}$, is still valid. It simply means that $y_n = 1*y_0 + 2$. The system implements a perfect integrator in this case. It does not exponentiate the accumulated value but adds inputs received from x together. The diagram is also valid in this case. If we want, we can also draw the system using nodes for the state variables
Again, input to the y is 2 from node "constant 1".
The state varying over time t can be represented as a vector $y_1, y_2, \cdots, y_t, \cdots$. The coefficients of polynomial are used to represent such vectors. For instance $1+2y+1y^2 + 5x^3$ represents vector 1,2,1,5. Now, series \eqref{eq:1} represents variable stuck at state $1,1,1,1,1,\cdots$. This can be represented by a diagram
You see, it was in state 1 and next state is 1*1=1, so is the next state. It evolves by staying constant. It was sequence ${1\over 1-y} = 1+y+y^2+y^3 + \ldots$. Do you remember that ${1\over 1+y}$ was alternating $1,-1,+1-1,\ldots$? That is because feedback -1 in the denominator!
When we add two together,
we read output from the summation node (it does not feedback anything and thus, is not a state variable). You see that at first time step, both accumulators are 1, so the output is 2. On the next step, the integrators are in counterphase, -1 and 1, so they cancel out for y^1. In the next step, they are in phase again, and output 2 is repeated. The sequence is $[2,0,2,0\ldots]$ The corresponding matrix for sequence $[2,0,2,0,\ldots]$
$$ y_n = a_n + b_n = \begin{bmatrix} 1 & 1 \end{bmatrix} \, \begin{bmatrix} a_n \\ b_n\end{bmatrix} = \begin{bmatrix} 1 & 1 \end{bmatrix} \, \begin{bmatrix} 1 & 0 \\0 & -1\end{bmatrix} \begin{bmatrix} a_{n-1} \\ b_{n-1}\end{bmatrix} = \begin{bmatrix} 1 & 1 \end{bmatrix} \, \begin{bmatrix} 1 & 0 \\0 & -1\end{bmatrix}^n \begin{bmatrix} a_{0} \\ b_{0}\end{bmatrix} $$
is diagonal right away.
The interesting thing is that transfer function approach implies 0 initial values. Laplace way to solve diff eq do use the initial values.
This post was aided by Finite State Machine Designer
