# How to estimate a summation?

For $v, w \in \{0,1\}^n$, denote $v w = (v_1 w_1, \ldots, v_n w_n)$ and $|v|=\sum_{i} v_i$.

Let $v_1, v_2 \in \{0,1\}^n$ and \begin{align*} f(x_1, x_2) = \sum_{d=0}^{|v_1 v_2|} \frac{1}{2^{|v_1|+|v_2|-|v_1 v_2|}} {|v_1| - |v_1 v_2| \choose x_1 - d} {|v_2| - |v_1 v_2| \choose x_2 - d}. \end{align*}

How to find the asymptotic formulas for $f(x_1, x_2)$ ($|v_1|, |v_2| \to \infty$)?

Is it possible to prove that there is a constant $\epsilon$, $0<\epsilon<1$, such that \begin{align} \sum_{x_1=0}^{|v_1|} \sum_{x_2=0}^{|v_2|} f(x_1, x_2) < 1 - \epsilon? \end{align}

These questions relate to the question.

Any help would be greatly appreciated!

• What limit do you want to consider? All binomial coefficients vanish when $x_1>\lvert \nu_1\rvert$ or $x_2>\lvert \nu_2\rvert$. So $f$ is asymptotic to $0$ as $x_i\to\infty$. Commented Aug 6, 2018 at 14:20
• @Philipp Lampe, thank you very much for your comments. I want to consider the limit $|v_1|, |v_2| \to \infty$. I have edited the post. Commented Aug 6, 2018 at 14:24
• I guess this is related to mathoverflow.net/questions/307584/… Commented Aug 6, 2018 at 15:34
• @Max Alekseyev, yes, this is a related question. I will put a link of that question in this post. Commented Aug 6, 2018 at 15:49

Put $a=|v_1|$, $b=|v_2|$, $c=|v_1v_2|$. Then we have $$\sum_{i=0}^a\sum_{j=0}^b\sum_{k=0}^c\binom{a-c}{i-k}\binom{b-c}{j-k}= \sum_{k=0}^c\left(\sum_{i=0}^a\binom{a-c}{i-k}\right)\left(\sum_{j=0}^b\binom{b-c}{j-k}\right).$$ As $i$ runs from $0$ to $a$, $i-k$ runs from $-k$ to $a-k$. Since $0\leq k\leq c$, this range covers the interval from 0 to $a-c$, thus $\sum_{i=0}^a\binom{a-c}{i-k} = \sum_{i=0}^{a-c}\binom{a-c}{i}=2^{a-c}$. Hence $$2^{a+b-c}\sum_{i=0}^a\sum_{j=0}^b f(i,j) = \sum_{k=0}^c 2^{a-c}\cdot 2^{b-c} = (c+1)2^{a+b-2c},$$ that is, $$\sum_{i=0}^a\sum_{j=0}^b f(i,j) = \frac{c+1}{2^c}.$$ Hence the answer to the last question is yes if and only if $|v_1v_2|>1$. A pointwise estimate for $f$ is more difficult, as it depends on the relative size of $a$, $b$ and $c$.