# 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?

-
I made an edit to use \text where you wanted text. I'm not sure how that differs from \mbox though, which also does the job, so excuse me if I've done something wrong. I also think there's a better way to do your (a) and (b) labels, but I couldn't work out through experimentation how to get references working. –  Ben Millwood Jun 7 '12 at 9:58
ah, someone else has edited it to use \tag, that seems nicer. –  Ben Millwood Jun 7 '12 at 10:12
Cheers @benmachine! I'm fairly new to Latex so all improvements are greatly appreciated. –  Johann Jun 7 '12 at 11:12

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}$.

-
Aha!Thats done the trick. Thanks for that thorough answer @Brian. As you say, I was stuck in a mental rut and approaching the problem from the wrong angle. –  Johann Jun 7 '12 at 11:06