7
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Under those constraints $|x|+|y|\leq\frac54$ and your sum is bounded by $(|x|+|y|)^{2n}$, so you at least have the bound $(5/4)^{2n}$. Is this naive bound enough for your needs? $\endgroup$ Oct 31, 2014 at 8:45
  • $\begingroup$ @JoonasIlmavirta Thanks, but no - I need to show this sum decays to $0$ in the limit of large $n$. The naive bound diverges. $\endgroup$
    – teagut
    Oct 31, 2014 at 11:56
  • $\begingroup$ Closed form is $${y}^{2\,n} \left( {\frac {x+y}{y}} \right) ^{2\,n}-{2\,n\choose n+1}{x }^{n+1}{y}^{n-1}{2F1(1,-n+1;\,n+2;\,-{\frac {x}{y}})}$$ $\endgroup$
    – joro
    Oct 31, 2014 at 13:22
  • $\begingroup$ Presumably you want to avoid $x=y=1/2$ in which case clearly the sum does not tend to zero. Maybe you want $|xy|<1/4$? In this case, I can show that the sum goes to zero. $\endgroup$
    – Lucia
    Oct 31, 2014 at 13:58
  • 1
    $\begingroup$ If $x=0$ and $|y|=1$ then the sum always has absolute value $1$. Do you want some of the inequalities on $x,y$ to be strict? $\endgroup$ Oct 31, 2014 at 15:19

5 Answers 5

10
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Thanks, very nice argument. However, while I can restrict $|x+y|<1$, I do not have $|4xy|<1$ but only $|4xy|\leq1$. I wonder whether in this case the sum still decays - it does avoid the special case $x=y=1/2$ pointed out by you in a comment above. $\endgroup$
    – teagut
    Oct 31, 2014 at 23:09
  • $\begingroup$ Can you or anyone else explain why $4^{−n}(2−10\log n /n)^{2n}(n+1)$ goes to zero for large n? Also why do you choose this number $2−10(\log n)/n$ to partition the integral into two pieces? $\endgroup$
    – teagut
    Nov 1, 2014 at 8:04
  • $\begingroup$ Ok, I think one gets that $\lim_{n\rightarrow\infty} 4^{-n}(2-10 \log n /n)^{2n}(n+1)=0$ using $\lim_{n\rightarrow\infty} (1+x/n)^n = \exp(x)$. $\endgroup$
    – teagut
    Nov 1, 2014 at 8:44
  • $\begingroup$ Alternatively, $\sum_{j\le n}\binom{2n}je^{ij\alpha}$ can be bounded by partial summation. I think this is easier than the integral. $\endgroup$ Nov 1, 2014 at 11:14
  • $\begingroup$ @EmilJeřábek: It amounts to about the same. You'll have to use Stirling and compute a different integral. $\endgroup$
    – Lucia
    Nov 1, 2014 at 13:19
5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Nice finesse! $\ \ \ \ $ $\endgroup$
    – Lucia
    Nov 2, 2014 at 16:06
4
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ Are you sure you didn’t use more assumptions? I believe that if $|y|>|x|$ and $|4xy|<1<|x+y|$, the limit diverges. $\endgroup$ Oct 31, 2014 at 22:03
  • $\begingroup$ Yes, of course: always keeping |x+y|≤1 , otherwise we can't guarantee that the integrand concentrates at t=1 $\endgroup$ Oct 31, 2014 at 22:41
  • 2
    $\begingroup$ @teagut: Norm is multiplicative. @ Pietro: Thanks for the clarification. However, you need strict inequality. If $|y|>|x|$ and $|4xy|<1=|x+y|$, the limit still diverges (or converges to $1$). $\endgroup$ Oct 31, 2014 at 23:10
  • $\begingroup$ @EmilJeřábek Thanks. But the answer by Pietro still requires strictly $4|xy|<1$ which I don't have. I'm wondering if the limit does not go to zero for strict $|x+y|<1$ and weak $|4xy|\leq1$. $\endgroup$
    – teagut
    Oct 31, 2014 at 23:27
  • $\begingroup$ I edited and made a more precise statement about the limit of the integral. $\endgroup$ Nov 2, 2014 at 18:00
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Actually this is how one proves the remainder forms in the Taylor expansions: derive the Taylor polynomial $\sum_{k=0}^mf^{(k)}(x)(y-x)^k/k!$ w.r.to $x$. $\endgroup$ Nov 1, 2014 at 7:04
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks, I think this could work given restriction to $|x+y|<1$. However, I checked different asymptotic expansions for the hypergeometric function $_{2}F_{1}(a,b;c;z)$ and I can't find one where both $|b|, c\rightarrow\infty$ with $a$ fixed. Or is it ok to consider large $|b|$ limit first and then take the limit of large $c$? $\endgroup$
    – teagut
    Oct 31, 2014 at 22:54
  • $\begingroup$ You find the relevant formulas at the following links : dlmf.nist.gov/15.12.E7 , dlmf.nist.gov/12.7.E1 , dlmf.nist.gov/12.7.E5 $\endgroup$ Mar 26, 2015 at 10:05

Your Answer

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