I'm trying to solve recurrences of the type
$$a(n,m) = \sum_{k=0}^{m} a(n-k,k), \qquad a(n,0)= a(0,m)=1 \qquad (A_0)$$
with the help of generating functions, but I get stuck quite early on. If I take the usual sum (neglecting the boundary condition for a while), I get
$$ f(x,y) = \sum_{n,m \geq 0} a(n,m) x^n y^m = \sum_{n,m \geq 0} \sum_{k=0}^{m} a(n-k,k)x^n y^m \qquad (A_1)$$
If the summand would be $a(n,k)$, we'd be happy and that sum would simply be the convolution with the constant sequence, hence $f(x,y)=\frac{f(x,y)}{1-y}$, however thats not the case.
How to proceed in such a case?
PS: Is there even a general way to find the gf for linear recurrences summing over specific "paths", e.g. $a(n,m) = \sum_{k=0}^{m} a(n-ck,k), \quad c \in \mathbb{N}$
Using a convention that $a(n,m)=0$ when $n<0$ or $m<0$, and ignoring boundary conditions as you do, write $$\sum_{n\geq 0} a(n-k,k)x^n = x^k \sum_{n\geq0} a(n,k)x^n = x^k [y^k]f(x,y),$$ where $[y^k]f(x,y)$ is the coefficient of $y^k$ in $f(x,y)$. Then you can sum further: $$\sum_{0\leq k\leq m} y^m x^k [y^k] f(x,y) = \sum_{0\leq k} \frac{y^k}{1-y} x^k [y^k]f(x,y). $$ Now the sum over $k$ is just $f(x,xy)$, because it replaces every $y^k$ with $x^k y^k$, so this is $$ \frac{f(x,xy)}{1-y}. $$
Replacing $a(n-k,k)$ with $a(n-ck,k)$ in the inner sum yields the inner sum $$ \sum_{n\geq0} a(n-ck,k)x^k = x^{ck}[y^k]f(x,y), $$ using the same method as above. In the end, this gives $$ \frac{f(x, yx^c)}{1-y}. $$