Skip to main content
2 of 6
make abs value brackets bigger
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

How to compute the asymptotic of a summation which involves binomial coefficients?

Let $v_1,v_2 \in \{0,1\}^n$. Denote $v_1v_2=((v_1)_1 (v_2)_1, \ldots, (v_1)_n (v_2)_n)$ and $|v|=\sum v_{i}$. \begin{align} {\scriptsize f(v_1, v_2) = \sum_{x_1=0}^{|v_1|} \sum_{x_2=0}^{|v_2|} \sum_{d=0}^{|v_1 v_2|} \frac{1}{2^{|v_1|+|v_2|-|v_1 v_2|}} \biggl| {|v_1| - |v_1 v_2| \choose x_1 - d} {|v_2| - |v_1 v_2| \choose x_2 - d} - {|v_1| - |v_1 v_2| \choose x_1 + 1 - d} {|v_2| - |v_1 v_2| \choose x_2 + 1 - d} \biggr|,} \end{align} where $v_1, v_2$ are some positive integers and $x_1, x_2 \in $. I want to estimate $f(v_1, v_2)$ when $|v_1|, |v_2| \to \infty$.

As a first step, I obtain \begin{align} { \scriptsize f(v_1, v_2) = \sum_{x_1=0}^{|v_1|} \sum_{x_2=0}^{|v_2|} \sum_{d=0}^{|v_1v_2|} \frac{1}{2^{|v_1|+|v_2|-|v_1v_2|}} \biggl| \left( 1- \frac{(v_1-|v_1v_2|-x_1+d)(v_2-|v_1||v_2|-x_2+d)}{(x_1+1-d)(x_2+1-d)} \right) {|v_1| - |v_1v_2| \choose x_1 - d} \biggr|, } \end{align}

How to estimate $f(v_1,v_2)$? Thank you very much.

Jianrong Li
  • 6.2k
  • 2
  • 21
  • 34