2
$\begingroup$

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.

  • 0
    Cheers @benmachine! I'm fairly new to Latex so all improvements are greatly appreciated.2012-06-07

1 Answers 1

2

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

  • 0
    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.2012-06-07