# How the sum $\sum_{j=0}^m {n \choose j}{2n+m-j-1\choose m-j}(-2)^j$ scales with $n$

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)

• For a given $j$, $n \choose j$ scales like $n^j$. Does this help? 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$.

• 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.
– Mah
Apr 24 '18 at 14:29
• You are correct - I meant to have a fraction over $m!$, but forgot to include it as I was formatting. I'll correct it. Apr 24 '18 at 14:35
• 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}$. May 8 '18 at 1:35