In the solution to the post here: Number of $h$ hop paths between two vertices with shortest path $s$ on an $n$ sided polygon., @hdighfan mentions the following recurrence and its solution.
$$ f(s, h) = \begin{cases} 1 & h = 0, s = 0 \\ 0 & h = 0, s \neq 0 \\ f(s+1, h-1) + f(s-1, h-1) & h > 0. \end{cases} $$ This recurrence has solution $$ f(s, h) = \begin{cases} \binom{h}{(h+s)/2} & h = s \bmod{2} \\ 0 & h \neq s \bmod{2}, \end{cases} $$ where $\binom{n}{r}$ is defined to be $0$ for $r < 0$ or $r > n$.
I'm still lost as to how one would go about deriving the solution for a two-dimensional recurrence like this?
Here is a solution I found in terms of generating functions. We have:
$$f(s,h)=f(h-1,s)+f(h-1,s-1)$$
Let's define the generating function:
$$F_h(x) = \sum\limits_{s=-\infty}^{\infty}f(h,s)x^s$$ $$=\sum\limits_{s=-\infty}^{\infty}(f(h-1,s)+f(h-1,s-1))x^s$$ $$=\frac{F_{h-1}(x)}{x}+xF_{h-1}(x)$$ $$F_h(x)=\frac{(1+x^2)}{x}F_{h-1}(x)$$
Now from the base case, we get: $F_0(x)=1$
So we get:
$$F_h(x)=\left(\frac{1+x^2}{x}\right)^h=\sum\limits_{k=0}^{h}{h \choose k}x^{2k-h}$$
Let $2k-h=s$. This gives us: $k=\frac{h+s}{2}$
Meaning:
$$F_h(x) = \sum\limits_{s=-\infty}^{\infty}{h \choose \frac{h+s}{2}}x^s$$
And the result follows. This method can be used also to prove the Pascal triangle recurrence has binomial terms as solution. See here: https://math.stackexchange.com/a/3718655/155881