write $x^{(k)} = x^{(0)} + \sum_{i=0}^{k-1} \big(c_1y_1^{(i)} + \dotsi + c_ny_n^{(i)} + b\big)$. By our induction hypothesis, each $y_j^{(i)}$ can be written as a linear term with coefficients from $\mathbb{Q}[k]$. It follows that there exists $p_0,...,p_n \in \mathbb{Q}[k]$ so that $$c_1y_1^{(i)} + \dotsi + c_ny_n^{(i)} + b = p_0(i) + p_1(i)y_{1}^{(0)} + \dotsi + p_n(i)y_n^{(0)}$$ Thus we have $$\begin{aligned}
  x^{(k)} &= x^{(0)} + \sum_{i=0}^{k-1} p_0(i) + p_1(i)y_{1}^{(0)} + \dotsi + p_n(i)y_n^{(0)}\\
  &= x^{(0)} + \sum_{i=0}^{k-1} p_0(i) + y_{1}^{(0)}\sum_{i=0}^{k-1} p_1(i) + \dotsi + y_{n}^{(0)}\sum_{i=0}^{k-1} p_n(i)\end{aligned}$$

The closed form of a summation of a polynomial of degree $m$ is a polynomial of degree $m+1$. We can find this polynomial via curve fitting (i.e., we compute the first $m+1$ terms of the summation and then solve the corresponding linear system of equations for the coefficients of the polynomial).

Linear recurrence (in)equations {#sec:lr_ineq}
-------------------------------

Recurrence equations (such as the simple and stratified varieties) yield very accurate approximations for *some* variables, but what about variables which do not satisfy *any* recurrence equation? For example, consider that neither `x` nor `y` satisfy a recurrence equation in the loop to the right. However, they *do* satisfy recurrence *inequations*: $\texttt{x}-1 \leq \texttt{x}'$, $\texttt{x}' \leq
\texttt{x}$, $\texttt{y}-1 \leq \texttt{y}'$, 