## Monday, January 12, 2015

### Initial values

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).