What is the general method to find an asymptotic formula for alternating sums

Question

How to find an asymptotic formula for the following sum: $$ \sum_{k=0}^n(-1)^k{n\choose k}\frac{n!2^k}{(n-k)!}(2n-2k)! $$ when $n\to\infty$?

---

If we set $S_k:={n\choose k}\frac{n!2^k}{(n-k)!}(2n-2k)!$, then we know that $S_k$ is a nonnegative decreasing sequence with regard to $k$. I have tried to bound the sum by the first three terms as upper bound and the first four terms as the lower bound but still cannot get an asymptotic formula. I mean this series goes very slow when $k$ grows larger.

And this formula is deduced from the inclusion-exclusion principle and that's why we have the alternating $1, -1$.

So in general, I am curious how to find an asymptotic formula when we use the inclusion-exclusion formula to get the explicit formula.

I have referred to this MO post but nothing in that post works to me.

---

Remark: Also, please give me a hint on the problem or you may describe the methods generally, please leave me to finish the details. Thank you!

Answer 1

$$ \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}\frac{n!2^k}{(n-k)!}(2n-2k)! &=n!^2\sum_{k=0}^n(-1)^k\frac{2^k}{k!}\binom{2n-2k}{n-k}\tag1\\ &\sim n!^2\sum_{k=0}^n(-1)^k\frac{2^k}{k!}\frac{4^{n-k}}{\sqrt{\pi\left(n-k+\frac14\right)}}\tag2\\ &=\frac{4^nn!^2}{\sqrt{\pi n}}\sum_{k=0}^n(-1)^k\frac{2^{-k}}{k!\sqrt{1-\frac kn+\frac1{4n}}}\tag3\\ &\sim\frac{4^nn!^2}{\sqrt{\pi n}}\sum_{k=0}^n(-1)^k\frac{2^{-k}}{k!}\left(1+\frac{k}{2n}-\frac1{8n}\right)\tag4\\ &\sim\frac{4^nn!^2}{\sqrt{\pi ne}}\left(1-\frac3{8n}\right)\tag5 \end{align} $$ Explanation:
$(1)$: rearrange the factorials
$(2)$: apply $(10)$ from this answer
$(3)$: move factors around
$(4)$: $(1-x)^{-1/2}\sim1+x/2$
$(5)$: apply the power series for $e^x$

Answer 2

Using Stirling's approximation, we get that

$$\sum_k (-1)^k S_k \approx -(n!)^2\sum_{k=1}^{n-1} (-2)^k\frac{\sqrt{2n-2k}}{\sqrt{k}(n-k)} \frac{(2n-2k)^{(2n-2k)}}{k^k(n-k)^{(2n-2k)}}e^k$$

$$ = -2^{2n+\frac{1}{2}}(n!)^2\sum_{k=1}^{n-1} \left(-\frac{e}{2k}\right)^k\frac{1}{\sqrt{k(n-k)}} \approx -\frac{2^{2n+\frac{1}{2}}(n!)^2}{\sqrt{n}}\sum_{k=1}^{N}\left(-\frac{e}{2k}\right)^k\frac{1}{\sqrt{k}}$$

where we consider the contribution from the terms past $N$, a large enough integer hopefully much much smaller than $n$, to be negligible. The terms of the series decay rapidly, so the approximation $n-k \approx n$ is valid. We could collect the first few terms to get a semi analytic, but messy, coefficient but the sum is approximately $1.08$. So we get

$$\sum_{k=0}^n (-1)^k S_k \approx 2.16 \pi\sqrt{2n} \left(\frac{2n}{e}\right)^{2n}$$

by Stirling's approximation again.

Answer 3

Here's a start. I am trying my usual even-odd technique for an alternating sum. I get a sum which is very messy, so I leave it at that. Perhaps someone else will continue this.

$\begin{array}\\ s(n) &=\sum_{k=0}^n(-1)^k{n\choose k}\dfrac{n!2^k}{(n-k)!}(2n-2k)!\\ &=\sum_{k=0}^n(-1)^k\dfrac{n!^22^k}{k!(n-k)!^2}(2n-2k)!\\ &=n!^2\sum_{k=0}^n(-1)^k\dfrac{(2n-2k)!2^k}{k!(n-k)!^2}\\ s(2n+1) &=(2n+1)!^2\sum_{k=0}^{2n+1}(-1)^k\dfrac{(2(2n+1)-2k)!2^k}{k!(2n+1-k)!^2}\\ &=(2n+1)!^2\sum_{k=0}^{2n+1}(-1)^k\dfrac{(4n-2k+1)!2^k}{k!(2n+1-k)!^2}\\ &=(2n+1)!^2\sum_{k=0}^{n}\left(\dfrac{(4n-2(2k)+1)!2^{2k}}{(2k)!(2n+1-(2k))!^2}-\dfrac{(4n-2(2k+1)+1)!2^{2k+1}}{(2k+1)!(2n+1-(2k+1))!^2}\right)\\ &=(2n+1)!^2\sum_{k=0}^{n}\left(\dfrac{(4n-4k+1)!2^{2k}}{(2k)!(2n+1-2k)!^2}-\dfrac{(4n-4k-1)!2^{2k+1}}{(2k+1)!(2n-2k)!^2}\right)\\ &=(2n+1)!^2\sum_{k=0}^{n}\dfrac{(4n-4k-1)!2^{2k}}{(2k+1)!(2n+1-2k)!^2}\left((4n-4k+1)(4n-4k)(2k+1)-2^2(2n+1-2k)^2\right)\\ &=(2n+1)!^2\sum_{k=0}^{n}\dfrac{(4n-4k-1)!2^{2k}}{(2k+1)!(2n+1-2k)!^2}\left(4 (8 k^3 - 16 k^2 n - 2 k^2 + 8 k n^2 + 2 k n + 3 k - 3 n - 1)\right)\\ &=4(2n+1)!^2\sum_{k=0}^{n}\dfrac{(4n-4k-1)!2^{2k}}{(2k+1)!(2n+1-2k)!^2} (8 k^3 - 16 k^2 n - 2 k^2 + 8 k n^2 + 2 k n + 3 k - 3 n - 1)\\ &=4(2n+1)!^2\sum_{k=0}^{n}\dfrac{(4n-4k-1)!2^{2k}}{(2k+1)!(2n+1-2k)!^2} (8 k^3 - k^2 (16n - 2) + k(8 n^2+2n+3) - 3 n - 1)\\ \end{array} $

So if we can get an estimate for $\sum_{k=0}^{n}\dfrac{(4n-4k-1)!2^{2k}}{(2k+1)!(2n+1-2k)!^2} k^m $ for $m=0, 1, 2, 3$, we are done.

Your turn.