3
$\begingroup$

I have the following difference of binomial coefficients: $$f(m)={m+n\choose n}-{m-d+n\choose n}$$ I believe the following two things should hold true:

  1. For $m$ large enough, $f(m)$ is a polynomial in $m$.
  2. Its degree is $n-1$.

Just expanding the expression a little bit one finds $$f(m)=\frac{(m+n)(m+n-1)\cdots(m+1)-(m-d+n)(m-d+n-1)\cdots(m-d+1)}{n!}$$ and clearly the $n!$ term pops out of both products, so $f(m)$ is actually a polynomial with integer coefficients for $m>d-1$. Also it is evident that the term $m^n$ gets canceled. However I wonder if it is obvious that the coefficient of $m^{n-1}$ is not zero (i don't see it). Does anybody see a more elegant way to do all this?

$\endgroup$
  • 1
    $\begingroup$ If $d=0$, then $f(m)=0$. $\endgroup$ – J.R. Jan 24 '14 at 18:28
3
$\begingroup$

Given any polynomial $g(x)$ of degree $n\ge1$ and any nonzero constant $d$, it's not hard to check that the expression $g(x) - g(x-d)$ is a polynomial of degree $n-1$. In fact, if the leading term of $g(x)$ is $ax^n$, then the leading term of $g(x)-g(x-d)$ is $adnx^{n-1}$. (This is one way in which this differencing operator acts like a discrete analogue of the derivative.)

In any case, your problem follows by setting $g(x) = \binom{x+n}n$.

$\endgroup$
  • $\begingroup$ That's precisely the kind of argument I was looking for. Thanks Greg. $\endgroup$ – Heitor Fontana Jan 25 '14 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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