Solving a very particular 2 variable recursion relation While solving a problem, me and a friend hit upon a particular recurrence relation that we tried solving using generating functions but failed. The relation looks like this :
$$P(n,k)=pP(n-1,k+1)+qP(n-1,k-1)$$ with the conditions
$$n\in\mathbb N\cup \{0\},\ 0\le k\le m$$
$$P(n,0)=0,\ P(0,k)=\begin{cases}0\ \ \text{if $k<m$}\\ 1\ \ \text{if $k=m$} \end{cases}$$
$$P(n,k)=0, \text{when $k>m$ or $n<0$}$$
where $m\in\mathbb N$ is a given value.
Here's what we tried. Let us look at a generating function $P(x,y)=\sum_{n,k}P(m,n)x^ny^k$ that models the recursion. Then, we note that:
\begin{multline}P(x,y)(y-px-qxy^2)=\sum_{n,k}P(n,k)(x^ny^{k+1}-px^{n+1}y^k-qx^{n+1}y^{k+2})\\ \hspace{10em}=\sum_{\substack{n\ge 1\\ k\ge 2}}P(n,k-1)-pP(n-1,k)-qP(n-1,k-2)\\ \hspace{7em}+\sum_{n=0}^\infty P(n,1)(x^ny^2-px^{n+1}y-qx^{n+1}y^3)\hspace{2em}+(y^{m+1}-pxy^m-qxy^{m+2})\end{multline}
The first summation vanishes dues to the recurrence relation, and thus we get:
\begin{multline}P(x,y)(y-px-qxy^2)=\sum_{n=0}^\infty P(n,1)(x^ny^2-px^{n+1}y-qx^{n+1}y^3)\\+(y^{m+1}-pxy^m-qxy^{m+2})\end{multline}
But after this, we are stuck.
Any help with solving this is greatly appreciated.
Edit : As lonza leggiera points out, the boundary conditions are contradictory to the fact that $p,q\ne 0$. We found out where we went wrong. The correct recursion should be:
$$P(n,k)=pP(n-1,k+1)+qP(n-1,k-1)$$ with the conditions
$$p+q=1$$
$$P(n,k)=0,\ \text{if $n<0$ or $k\le 0$}$$
$$P(0,k)=0,\ \text{if $k< m$}$$
$$P(n,k)=1,\ \text{if $k\ge m$}$$
 A: This is not really an answer, but a demonstration that your currently specified conditions are probably not quite what you want.   First, the specifications

with the conditions
$$
 n\color{red}{\in\mathbb{N}\cup\{0\}}, 0\le k\color{red}{\le m}
 $$

and

$$
  P(n,k)=0,\ \text{when }\ \color{red}{k>m}\ \text{or}\ \color{red}{n<0}
$$

are contradictory. If you ignore the red parts of the first set of conditions and impose just the second set, then I believe a solution will only exist if $\ p=q=0\ $, when the (unique) solution is $\ P(n,k)=0\ $.   From the condition
$$
P(n,k)=0\ \ \text{when }\ k>m\ ,
$$
for example, we get
$$
P(0,m+2)=P(0,m+1)=P(1,m+1)=0
$$
The recursion relation then gives us
$$
P(1,m+1)=pP(0,m+2)+qP(0,m)=q\ ,
$$
from which it follows that $\ q=0\ $.  Showing that $\ p=0\ $ requires a little more work, which I won't bother doing here.
If you instead limit the domain of the solution you're looking for to be integers satisfying
$$
n\ge0, 0\le k\le m+1\ ,
$$
and simply require $ P(n,m+1)=P(n,0)=0\ $ for all $\ n\in\mathbb{N}\cup\{0\}\ $, then I believe there will always be a non-trivial unique solution for which you may be able to obtain a fairly simple expression in closed form.  I'm not inclined to bother trying to find it, however, unless you can say definitely that it really is the solution you're looking for.
