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!

  • $\begingroup$ 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$. $\endgroup$ Commented Aug 6, 2018 at 14:20
  • $\begingroup$ @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. $\endgroup$ Commented Aug 6, 2018 at 14:24
  • $\begingroup$ I guess this is related to mathoverflow.net/questions/307584/… $\endgroup$ Commented Aug 6, 2018 at 15:34
  • $\begingroup$ @Max Alekseyev, yes, this is a related question. I will put a link of that question in this post. $\endgroup$ Commented Aug 6, 2018 at 15:49

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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