How to estimate a summation?

Question

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!

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