Bound on sum of complex summands involving binomial coefficients

Question

I am trying to find the asymptotic behavior of the sum:

$$ \sum^n_{i=0} \begin{pmatrix} 2n \\ i \end{pmatrix} x^i y^{2n-i}$$

as $n\rightarrow\infty$. Here $x$, $y$ are complex numbers and I have $|x|\leq1$ and $|y|\leq1$. I also know that $|x+y|\leq1$ and $|4xy|\leq1$.

One of the approaches I thought about was to approximate the sum by an integral. However, as it turns out, this approach runs into trouble since the terms in the sum do not give a sufficiently smooth function (I think: we have complex numbers raised to non-integer powers thus giving phase ambiguities).

On the other hand this sum may be related to Hoeffding's inequality applied to binomial distribution. This inequality gives an exponential upper bound. However, since $x, y$ are complex and $|x+y|\leq1$, I don't know how to apply this inequality.

Is there a way to bound this sum? I need to show it decays to $0$ as $n\rightarrow\infty$.

Answer 1

Assuming that $|x+y|<1$ and $4|xy| \le 1$, here's a proof of the decay.

First suppose that $|x|> |y|$. The desired sum is $$ \le \binom{2n}{n} |xy|^n \sum_{j=0}^{n} |y/x|^j \le \binom{2n}{n} |xy|^n \frac{1}{1-|y/x|}. $$ Since $\binom{2n}{n}$ is of size about $4^n/\sqrt{n}$, the desired decay follows in this case.

Next suppose $|x| <|y|$. Here we flip the roles of $x$ and $y$ using $$ \sum_{k=0}^{n} \binom{2n}{k}x^k y^{2n-k} = (x+y)^{2n} - \sum_{\ell =0}^{n-1} \binom{2n}{\ell} y^{\ell} x^{2n-\ell}, $$ and now use the previous argument. In this step, to get decay, we used that $|x+y|<1$.

Finally suppose that $|x|=|y|$. If $|x|=|y|<1/2$ then the sum is $$ \le \binom{2n}{n} |y|^{2n} (n+1) $$ which decays exponentially. We are left with $|x|=|y|=1/2$ and $|x+y|<1$. It is enough to treat $x=e^{i\alpha}/2$ and $y=1/2$, with $0<\alpha<2\pi$. We need to bound $$ 4^{-n} \sum_{j=0}^{n} \binom{2n}{j}e^{ij\alpha} = \frac{4^{-n}}{2\pi} \int_0^{2\pi} (1+e^{i\alpha-i\theta})^{2n} (1+e^{i\theta}+\ldots +e^{in\theta}) d\theta, $$ by Parseval's identity. The portion of the integral with $|1+e^{i\alpha-i\theta}| \le 2 - 10 (\log n)/n$ contributes $$ \le 4^{-n} \Big(2-10\frac{\log n}{n}\Big)^{2n} (n+1), $$ which goes to zero for large $n$. The set of $\theta \in [0,2\pi]$ with $|1+e^{i\alpha-i\theta}| \ge 2-10(\log n)/n$ has measure $O(\frac{\log n}{n})$ and for such $\theta$ we see that $|1+e^{i\theta}+\ldots +e^{in\theta}|$ is bounded (since $0<\alpha <2\pi$ by assumption, and so $\theta$ is bounded away from $0$ and $2\pi$). Therefore this portion of the integral is $O(\frac{\log n}{n})$, completing the proof.

Answer 2

This is a comment to Lucia’s answer that doesn’t fit into the comment box.

In the case $|x|=|y|=1/2$, put $\omega=x/y$, and $$S_k=\sum_{j=0}^k\omega^j=\frac{1-\omega^{k+1}}{1-\omega}.$$ Then by partial summation, $$\sum_{k=0}^n\binom{2n}kx^iy^{2n-i}=y^{2n}\left[\binom{2n}nS_n-\sum_{k=0}^{n-1}S_k\left(\binom{2n}{k+1}-\binom{2n}k\right)\right],$$ the absolute value of which is bounded by $$4^{-n}\frac2{|1-\omega|}\left[\binom{2n}n+\sum_{k=0}^{n-1}\left(\binom{2n}{k+1}-\binom{2n}k\right)\right]\le\frac{4^{1-n}}{|1-\omega|}\binom{2n}{n}\le\frac{4+o(1)}{|1-\omega|\sqrt{\pi n}}.$$

Answer 3

If you write your expression as $$ \big(x+y\big)^{2n}-\sum^{ n-1}_{k=0} \bigg({2n \atop k} \bigg)\, x^{2n-k}y^k\, ,$$ you may see it as a remainder in a $(n-1)$-order Taylor expansion of the function $z^{2n}$ at $x$. By the integral form of the remainder it writes

$$ \begin{pmatrix} 2n \\ n \end{pmatrix} y ^n \int_0^1 \big(x+(1-t)y\big)^n nt^{n-1}dt\, ,$$

(One can easily cheek it directly). Changing variable we have

$$ \sum^n_{k=0} \begin{pmatrix} 2n \\ k \end{pmatrix} x^k y^{2n-k}\,=\begin{pmatrix} 2n \\ n \end{pmatrix} y ^n \int_0^1 \big(x+(1-s^{1/n})y \big)^n ds\, .$$

Making the assumption $0<4|xy|\le1$, and since $\big({2n\atop n}\Big)= 4^n(\pi n)^{-1/2}(1+o(1))$, the decay for your sum is equivalent to $$n^{-1/2} \int_0^1 \Big(1+(1-s^{1/n})z \Big)^n ds\,=o(1),$$ as $n\to\infty$, for $z:=y/x$ . Note that for $0<s\le 1$ and for all $z\in \mathbb{C}$ the integrand converge point-wise to $s^{-z}$, so that the thesis would follow by dominated convergence if $z$ is also such that the function $$g(s):=\max_{n\in\mathbb{N_+}} n^{-1/2} \Big|1+(1-s^{1/n})z \Big|^n $$ is integrable. This is not a quick computation, though feasible, that might also give precise asymptotics.

Answer 4

This is not a complete answer but could be made into one. I just want to note that a simple ODE is satisfied by partial sums of the binomial series, which is sometimes very handy.

Write $z=x+y$ and hold $z$ constant. The required sum is $$ S(x) = \sum_{i=0}^n \binom{2n}{i} x^i (z-x)^{2n-i},$$ and the nice thing is that $$ S'(x) = -n \binom{2n}{n} x^n (z-x)^{n-1}.$$ Together with $S(0)=z^{2n}$, this will give bounds by integrating along suitable paths. This is equivalent to Pietro's integral.

Also note that the original sum in $x$ and $y$ is homogeneous so you can assume that one of $x,y,x+y$ is real and positive as per convenience.

Answer 5

Mathematica evaluates the sum as $$ (x+y)^{2 n}-\frac{x \binom{2 n}{n+1} (x y)^n \, _2F_1\left(1,1-n;n+2;-\frac{x}{y}\right)}{y} $$ Since the middle binomial coefficient is approximately $4^n/\sqrt{n},$ that cancels the $(xy)^n$ term (under your assumption) leaving the $1/\sqrt{n}$, so you just need to check the asymptotics of the hypergeometric function (which are almost surely in Abramowitz and Stegun). However, the $(x+y)^{2n}$ term looks like a problem, since you don't have a strict inequality on $|x+y|.$