If $z \in \mathbb{Z}^+$ and $p_{z,n}$ is the number of sequences, $a_1, \dots, a_n$ of size $n$ where $a_i \in \mathbb{Z}^+$, so that for $0 \leq j \leq n$: $$0 \leq \sum_{i=1}^j (-1)^{i-1}a_i \leq z$$
I need to find a recurrence relation for $p_{z,n}$ and calculate $p_{4,4}$.
I am unable to formulate an equation for $a_n$ that could help me simplify a relation for this partial sum of an alternating series.
My recurrence is a bit complicated, but at least it works better than the brute-force enumeration...
For $\bar{a}=(a_1,\ldots,a_n)$ and $1\leqslant j\leqslant n$, let's denote $\sum_{i=1}^{j}(-1)^{i-1}a_i$ by $s_j(\bar{a})$. Thus, $$p_{z,n}=\#P_{z,n},\quad P_{z,n}:=\{\bar{a}\in\mathbb{Z}_{>0}^{n} : 0\leqslant s_j(\bar{a})\leqslant z\text{ for all }1\leqslant j\leqslant n\}.$$ Suppose $n>1$. For an element $\bar{a}$ of $P_{z,n}$, either $s_j(\bar{a})>0$ for all $1\leqslant j\leqslant n$ (then we must have $a_1>1$, and if we replace $a_1$ by $a_1-1$, we obtain an element of $P_{z-1,n}$; this is one-to-one, hence there are $p_{z-1,n}$ such elements), or $s_j(\bar{a})=0$ for some $j$ (which is clearly even); let $2d$ be the smallest such $j$. Since $s_{2d}(\bar{a})=0$, the parts $(a_1,\ldots a_{2d})$ and $(a_{2d+1},\ldots,a_n)$ can be formed (hence counted) independently.
The number of suitable parts $(a_{2d+1},\ldots,a_n)$ is clearly $p_{z,n-2d}$. As for $(a_1,\ldots,a_{2d})$, we must have $a_{2d}=s_{2d-1}(\bar{a})$ and $s_j(\bar{a})>0$ for $0<j<2d$. This is similar to the above, but here we must distinguish $d=1$ (when the number of parts is $p_{z,2d-1}=p_{z,1}=z$) and $d>1$ (when it is again $p_{z\color{red}{-1},2d-1}$).
With boundary cases $p_{z,1}=z$, $p_{1,n}=p_{z,0}=1$ (the last one to handle the case $2d=n$), the recurrence is $$\bbox[5pt,border:2pt solid]{p_{z,n}=p_{z-1,n}+zp_{z,n-2}+\sum_{d=2}^{\lfloor n/2\rfloor}p_{z-1,2d-1}p_{z,n-2d}.}\qquad(z,n>1)$$
And here is a table of $p_{z,n}$ for $1\leqslant z,n\leqslant 9$: $$\begin{array}{r|rrrrrrrrr} n=\to&1&2&3&4&5&6&7&8&9\\\hline z=1& 1& 1& 1& 1& 1& 1& 1& 1& 1\\ z=2& 2& 3& 5& 8& 13& 21& 34& 55& 89\\ z=3& 3& 6& 14& 31& 70& 157& 353& 793& 1782\\ z=4& 4& 10& 30& \color{blue}{85}& 246& 707& 2037& 5864& 16886\\ z=5& 5& 15& 55& 190& 671& 2353& 8272& 29056& 102091\\ z=6& 6& 21& 91& 371& 1547& 6405& 26585& 110254& 457379\\ z=7& 7& 28& 140& 658& 3164& 15106& 72302& 345775& 1654092\\ z=8& 8& 36& 204& 1086& 5916& 31998& 173502& 940005& 5094220\\ z=9& 9& 45& 285& 1695& 10317& 62349& 377739& 2286648& 13846117\\ \end{array}$$