Proving a function satisfies the binomial recurrence relation and that it equals $\binom{n-k+1}{k}$ I have the recurrence relation $g(n,k)=g(n-2,k-1) + g(n-1,k)$ for all $k\geq1$
 with the boundary conditions $g(n,k)=0$ if $n<2k-1$ and $g(2k-1,k)=1$
What I'm trying to do is define a new function by the equation $ h(p,q) = g(n,k)$ where $n=p+q-1$ and $k=q$ and show that $ h(p,q)$ satisfies the binomial recurrence relation and its boundary conditions and hence deduce that $g(n,k)=\binom{n-k+1}{k}$ 
My workings are:
We have the binomial recurrence relation $$\binom{p}{q}=\binom{p-1}{q-1}+\binom{p-1}{q}$$ 
where$$\begin{align*} \\&\binom{p}{q}=0\text{ when }q>p \\&\binom{p}{q}=1\text{ when }p=q \end{align*}$$ Now if $$\begin{align*} \\&p=n-k+1 \\&q=k \end{align*}$$
Then $$\begin{align*} \\&\binom{n-k+1}{k}=0\mbox{ when }n<2k-1\text{ (the first boundary condition)}\end{align*}$$ and $$\begin{align*} \\&\binom{n-k+1}{k}=1\text{ when }n=2k-1 \text{ (the second boundary condition)}\end{align*}$$ 
Also $$\begin{align*}\\&\binom{n-k+1}{k}=\binom{n-k}{k-1}+\binom{n-k}{k}\end{align*}\tag{a}$$
Now from the recurrence relation  $g(n,k)$ we have (Is this true???): $$\binom{n}{k}=\binom{n-2}{k-1}+\binom{n-1}{k}$$ Which therefore equals: $$ \binom{n-k+1}{k}=\binom{n-k-1}{k-1}+\binom{n-k}{k}\tag{b}
$$
Setting $(a)$ equal to $(b)$ we now get: $$\begin{align*}\binom{n-k}{k-1}+\binom{n-k}{k}&=\binom{n-k-1}{k-1}+\binom{n-k}{k}\\ \binom{n-k}{k-1}&=\binom{n-k-1}{k-1}\end{align*}$$ 
However, I am not sure where to go from here. I'm rather dubious as to the veracity of this identity as I have been unable to prove that it is true. Am I on the right track? If so how do I go about proving this identity? If I'm off beam any ideas where I went wrong?
Thanks in advance.
 A: The basic problem is that you’re starting at the wrong end: you should be working with $h$.
Let’s restate the problem a little more clearly. You’re to define $h(p,q)=g(p+q-1,q)$ and prove that the function $h$ satisfies the binomial recurrence, which, stated in terms of $h$, is $$h(p,q)=h(p-1,q-1)+h(p-1,q)\tag{1}\;.$$ Let’s see what happens when we expand the righthand side of $(1)$ in terms of $g$:
$$\begin{align*}
h(p-1,q-1)+h(p-1,q)&=g(p+q-3,q-1)+g(p+q-2,q)\\
&=g(p+q-1,q)\\
&=h(p,q)\;,
\end{align*}$$
which is exactly what we wanted. The only step that might be puzzling for a moment is the second, which uses the fact that $g(n,k)=g(n-2,k-1)+g(n-1,k)$: just let $n=p+q-1$ and $k=q$.
Next, you’re to check that $h$ satisfies the same boundary conditions as the binomial coefficients. In other words, you’re to show that $g(p,q)=0$ when $p>q$, and $g(p,q)=1$ when $p=q$. When $p=q$, for instance, $g(p,q)=g(p,p)=h(2p-1,p)$, which is what? The case $p>q$ is equally easy.
Once you finish that, you’ll have shown that $h(p,q)=\binom{p}q$: they satisfy the same boundary conditions and the same recurrence, so by an easy induction they’re always equal.
Your final task is to use this to show that $g(n,k)=\binom{n+k-1}k$; this will be easy once you express $g(n,k)$ in terms of $h$. That is, just as $h(p,q)=g(p+q-1,q)$, you can express $g(n,k)$ as $h(\text{thing}_1,\text{thing}_2)$ and therefore as $\binom{\text{thing}_1}{\text{thing}_2}$.
