Math Insight

Solving linear discrete dynamical systems

A linear discrete dynamical system is one of the form \begin{align*} x_{n+1} &= a x_n\\ x_0 &= b, \end{align*} where $a$ and $b$ are two numbers called parameters. The parameter $a$ determines how fast $x_n$ grows or shrinks. The parameter $b$ determines the initial condition. Here we show how to solve such a linear system, meaning find a formula for $x_t$ that is written just in terms of the time step $n$ and the initial condition $x_0$ (and, unlike above the above equation, doesn't depend on the value of $x$ from the previous time step).

Video

Summary of video

The solution to the linear system \begin{align} x_{n+1} &= a x_n\label{linear_function_iteration}\tag{1}\\ x_0 &= b\notag, \end{align} is \begin{align*} x_{n} = a^n b. \end{align*} According to the rule $x_{n+1}=ax_n$, one multiplies by $a$ for each time step. Therefore, to evolve from $x_0$ to $x_n$, one must multiply by $a$ a total of $n$ times, i.e., multiply by $a^n$.

Model \eqref{linear_function_iteration} was especially simple to solve because it is in function iteration form, meaning the rule is in the form $x_{n+1}=f(x_n)$ for some function $f$ (in this case $f(x)=ax$). Sometimes, it is easier to come up with a model of the form \begin{align} x_{n+1} - x_n &= ax_n\label{linear_difference}\tag{2}\\ x_0 &= b.\notag \end{align} This form is called difference form because the left hand side $x_{n+1}-x_n$ is the difference between values of the state variables between two time steps. To solve a linear discrete dynamical system \eqref{linear_difference} in difference form, the first step is to convert it to function iteration form. Simply add $x_n$ to both sides to obtain \begin{align*} x_{n+1} &= (a+1)x_n\\ x_0 &= b. \end{align*} The solution is the same as for model \eqref{linear_function_iteration} in function iteration form, only that $a$ is replaced by $a+1$: \begin{align*} x_n = (a+1)^n b. \end{align*}

You can see some examples of solving linear discrete dynamical systems.