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.

  • 1
    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.2012-06-07
  • 0
    ah, someone else has edited it to use `\tag`, that seems nicer.2012-06-07
  • 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