Bound for $\sum_{k=0}^{n}(-1)^k{3n\choose k}{n\choose k}$.

Question

In the book Complex analysis by Bak J. & Newman J., chapter 11, talks about Sums Involving Binomial coefficients and find a bound $\frac{16}{9}\sqrt{3}$ for $|(z-1)^2(z+1)|$ in the "Example 3" on the unit circle, my way was using lagrange multipliers in this form:

We want find $\max{|(z-1)^2(z+1)|}$ ahnd have that $|z-1|^2+|z+1|^2=4$. Let be $a=|z-1|$ and $b=|z+1|$ and then the exercise is: "Maximize $f(a,b)=a^2b$ subject to $a^2+b^2=4$" then $\nabla f=\lambda\nabla g$ so $\begin{cases}2ab=\lambda(2a)\\a^2=\lambda(2b)\end{cases}$, i.e., $ab=\lambda a$ if $a(b-\lambda)=0$ therefore

i)$a=0$ or $b=\lambda$, $b^2=4$ then $b=2$ then $|z+1|=2$ or $|z-1|=0$ then $z=1$ and $a^2b=0$.

ii)$b=\lambda$, $a^2=2b^2$ then $4=a^2+b^2=3b^2$ then $b^2=4/3$ then $b=\frac{2\sqrt{3}}{3}$ then $a^2=\frac{8}{3}$ then $a=\frac{2\sqrt{2}}{\sqrt{3}}$

So $a^2b=\frac{8}{3}\frac{2\sqrt{3}}{3}=\frac{16}{9}\sqrt{3}$.

After i want to use this idea for exercise 17.b with $\sum_{k=0}^{n}(-1)^k{3n\choose k}{n\choose k}$ but, i don´t see what should be $a$ and $b$.

Edit: this exercise says that $|\sum_{k=0}^{n}(-1)^k{3n\choose k}{n\choose k}|\leq4^n$.

Answer 1

Using the "coefficient-of" notation, we have $$S_n:=\sum_{k=0}^{n}(-1)^k\binom{3n}{k}\binom{n}{k}=\sum_{k=0}^{n}[z^k](1-z)^{3n}\times[z^{n-k}](1+z)^n=[z^n]\big((1-z)^3(1+z)\big)^n.$$ Let $f(z)=(1-z)^3(1+z)/z$; then, by Cauchy integral formula, for any $r>0$ we have $$S_n=\frac{1}{2\pi\mathrm{i}}\oint_{|z|=r}\big(f(z)\big)^n\frac{dz}{z}\implies|S_n|\leqslant\Big(\max_{|z|=r}\big|f(z)\big|\Big)^n.$$ The key to a solution is to choose $\color{blue}{r=1/\sqrt{3}}$ (this is suggested by saddle points of $\big|f(z)\big|$, that is, the solutions $z=(-1\pm\mathrm{i}\sqrt{2})/3$ of $f'(z)=0$; alternatively, we can let $r$ be arbitrary, and minimize the result w.r.t. $r$ in the end). Using $|1+z|^2+|1-z|^2=2(1+|z|^2)$ again, we arrive at $$\text{maximize}\quad a^3 b\quad\text{subject to}\quad a^2+b^2=8/3.$$ Solving it the way you know, we find $a^2=2$, $b^2=2/3$, $a^3 b=4/\sqrt{3}$ and $\color{blue}{\max\limits_{|z|=r}\big|f(z)\big|=4}$.

Answer 2

The first term in the asymptotic expansion follows from the analysis given by 'Asymptotics of a Family of Binomial Sums' by R. Noble. Putting this in a form for comparison one gets

$$ \sum_{k=0}^n (-1)^k\binom{3n}{k} \binom{n}{k} \sim (-4)^n \frac{2^{1/4}}{\sqrt{\pi n}} \cos(n \tan^{-1}(10\sqrt{2}/23) + \tan^{-1}((1-\sqrt{2})/(1+\sqrt{2})) $$

This is not a bound, of course. However, when $n$ is large enough,

$$ \Big|\sum_{k=0}^n (-1)^k\binom{3n}{k} \binom{n}{k} \Big| < C\frac{4^n}{\sqrt{n}}.$$ Is $C=2^{1/4}/\sqrt{\pi} \approx 0.671$ ? Checking up through $n=1000$ says it is. To be rigorous the next term in the asymptotic expansion needs to be generated.

For comparison of the asymptotic formula and the exact: n=200, true=-1.2130 x $10^{119},$ appx=-1.2145 x $10^{119},$ and absolute % error between them is 0.12%.