I want to find out how the function: $$f(m)=\sum_{j=0}^m {n \choose j}{2n+m-j-1\choose m-j}(-2)^j$$ ($m$ is an integer and $n\gg m> 0$), scales with $n$, as $n\to\infty$. I am not good at combinatorics formulas, but from naive calculation of $f(m)$ for different values of $m$, I think it should scale like $n^{\lfloor{m/2} \rfloor }$.

(This function $f(m)$ is from the answer to my previous question)

  • 1
    $\begingroup$ For a given $j$, $n \choose j$ scales like $n^j$. Does this help? $\endgroup$
    – René Gy
    Apr 23 '18 at 18:07

As René Gy points out, $${n \choose j} = \frac{n(n-1)...(n-j+1)}{j!}$$

is a polynomial of degree $j$ in the variable $n$. As $n \to \infty$, a polynomial becomes dominated by its leading (highest degree) term, which eventually dwarfs all the other terms. The leading term in $n \choose j$ is $\frac 1{j!}n^j$.

Similarly, $${2n+m-j-1\choose m-j}= \frac{(2n+m-j-1)(2n+m-j-2)...(2n)}{(m-j)!}$$ is a polynomial of degree $m-j$, with leading term $\frac {2^{m-j}}{(m-j)!}n^{m-j}$

So ${n \choose j}{2n+m-j-1\choose m-j}(-2)^j$ will be a polynomial with leading term $$\left(\frac 1{j!}n^j\right)\left(\frac {2^{m-j}}{(m-j)!}n^{m-j}\right)(-2)^j = \frac{(-1)^j}{j!(m-j)!}2^mn^m = {m\choose j}(-1)^j\frac{2^mn^m}{m!}$$

and finally, as a polynomial in $n$, $f$ will have leading coefficient $$\sum_{j=0}^m {m\choose j}(-1)^j\frac{2^mn^m}{m!}= \frac{2^mn^m}{m!}\sum_{j=0}^m {m\choose j}(-1)^j = \frac{2^mn^m}{m!}(1 - 1)^m = 0$$

Well, don't that beat all. The leading coefficient from individual terms disappears in the sum.

The 2nd leading term of the individual terms will have degree $m-1$, but its coefficient is more complex. I don't have time to pursue it further tonight, but you can work through the algebra to determine it in a fairly straight-forward manner.

I suspect that the degree $m-1$ terms do not cancel out, which would mean that $f$ grows as $Kn^{m-1}$ as $n \to \infty$ for some constant $K$.

  • $\begingroup$ Thanks for your answer. I just don't understand why $\frac{(-1)^j}{j!(m-j)!}2^mn^m = {m\choose j}(-1)^j2^mn^m$. it seems an $m!$ is missing here. $\endgroup$
    – Mah
    Apr 24 '18 at 14:29
  • $\begingroup$ You are correct - I meant to have a fraction over $m!$, but forgot to include it as I was formatting. I'll correct it. $\endgroup$ Apr 24 '18 at 14:35
  • $\begingroup$ The leading term can easily be guessed, it's $$\sum_{j = 0}^m \binom n j \binom {2 n + m - j - 1} {m - j}(-2)^j \sim \frac {(-n)^{\lfloor m/2 \rfloor}} {\lfloor m/2 \rfloor!} \cases {1 & $m$ even \\ m - 1 & $m$ odd}, \quad m \geqslant 2.$$ Thus the problem is that the powers of $n$ are going to cancel all the way down to $n^{\lfloor m/2 \rfloor}$. $\endgroup$
    – Maxim
    May 8 '18 at 1:35

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.