Non-linear recurrence relation with Kronecker delta

Question

I am studying a game in number theory and I have come across some non-linear (coupled) recurrence relations which involve what I've been referring to as Kronecker deltas (or unit sample functions). An example (one of the simplest) is the following.

$$ x_n = x_{n-1} + \delta(x_{n-1}) \\ y_n = y_{n-1} - \delta(x_{n-1}) + \delta(x_n) + \delta(y_{n-2}) - \delta(z_{n-2}) + \delta(z_n) \\ z_n = z_{n-1} - \delta(x_{n-1}) + \delta(x_n) + \delta(y_{n-2}) - \delta(z_{n-2}) + \delta(z_{n-1}) $$

where $\delta$ is defined by

$$ \delta(n) = \begin{cases} 1 & \text{if $n=0$}\\ 0 & \text{otherwise} \end{cases} $$

The initial values of the sequences are non-negative integers (generally 1s and 0s). The game mechanics will always ensure that the values of the $x_n, y_n, z_n$ are always themselves non-negative. In the above example the initial values are as follows.

$$ x_1 = 1 \\ y_1 = 1 \\ y_2 = 1 \\ z_1 = 1 \\ z_0 = 0 $$

Of primary interest in the game is answering the question, for each of the sequences ($s_i$) above: Does there exist exist some $i$ for which $s_i$ is zero? Or, more strongly: For which $i$ is $s_i$ equal to zero?

My question is, besides solving these by computation, is there anything we can say about these types of equations in general? Are there any similar examples in the literature which I could research in order to attack such equations?

Essentially I am looking for some insight or clues to see if looking at the problem this way is helpful at all.

Answer 1

I have no prior knowledge of, or experience with, such systems of equations, so I can't point you to any relevant literature or give you any general insights about such systems. Below is simply an analysis of this particular system.

---

The sequence $(x_n)_{n\in\Bbb{N}}$ is easiest to analyse, as it does not depend on the other two sequences:

• If $x_0>0$ then $\delta(x_0)=0$ and so $x_1=x_0$, and hence $x_n=x_0$ for all $n\in\Bbb{N}$.
• If $x_0=0$ then $\delta(x_0)=1$ and so $x_1=1$, and by the same argument $x_n=1$ for all $n\geq1$.

So $(x_n)_{n\in\Bbb{N}}$ is a constant sequence, or nearly so if $x_0=0$. In particular the answer to your question

For which $n$ is $x_n$ equal to zero?

is very simply: Only for $n=0$ and only if $x_0=0$ is given.

Now the recurrence relations for $(y_n)_{n\in\Bbb{N}}$ and $(z_n)_{n\in\Bbb{N}}$ are coupled, making the analysis a bit more involved. Fortunately, the argument above shows that $\delta(x_n)=0$ if $n>0$, and so the recurrences simplify to: \begin{eqnarray*} y_n&=&y_{n-1}+\delta(y_{n-2})-\delta(z_{n-2})+\delta(z_n),\\ z_n&=&z_{n-1}+\delta(y_{n-2})-\delta(z_{n-2})+\delta(z_{n-1}),\\ \end{eqnarray*} whenever $n\geq2$. We can distinguish the following $16$ cases: $$\begin{array}{r|c|c|c|c} \text{case}&\delta(y_{n-2})&\delta(y_{n-1})&\delta(z_{n-2})&\delta(z_{n-1})\\ \hline 0&0&0&0&0\\ 1&0&0&0&1\\ 2&0&0&1&0\\ 3&0&0&1&1\\ 4&0&1&0&0\\ 5&0&1&0&1\\ 6&0&1&1&0\\ 7&0&1&1&1\\ 8&1&0&0&0\\ 9&1&0&0&1\\ 10&1&0&1&0\\ 11&1&0&1&1\\ 12&1&1&0&0\\ 13&1&1&0&1\\ 14&1&1&1&0\\ 15&1&1&1&1 \end{array}$$ From each case we can see whether $y_{n-2}$, $y_{n-1}$, $z_{n-2}$, $z_{n-1}$ are equal to $0$ or not. So it suffices to see in which case we are for each index $n$. For example, if we are in case $5$ at index $n$, then the recurrence relations become \begin{eqnarray*} z_n&=&z_{n-1}+\delta(y_{n-2})-\delta(z_{n-2})+\delta(z_{n-1})&=&z_{n-1}+1,\\ y_n&=&y_{n-1}+\delta(y_{n-2})-\delta(z_{n-2})+\delta(z_n)&=&y_{n-1},\\ \end{eqnarray*} and so we are in case $14$ at index $n+1$. The following diagram shows how the cases progress as the index progresses:

From this you can read, with some effort, for which indices $n$ you have $y_n=0$ or $z_n=0$, given some initial values $y_0$, $y_1$, $z_0$, and $z_1$. Note that this is independent of the sequence $(x_n)_{n\in\Bbb{N}}$.

EDIT: I see now that the conditions on the arrows going out from case $6$ should be switched.