Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.