Check asymptotic of

C = $\sum_{k = 0}^{\frac{n}{2} - \sqrt{n}} k \binom{n}{k} = f(n) + O(g(n))$

In the beginning I tried to simplify the expression under the sum: $$k\binom{n}{k} = k \frac{n!}{k!(n-k)!} = \frac{n!}{(k - 1)!(n - k)!} = n \frac{(n-1)!}{(k - 1)!((n-1) - (k-1))!} = n \binom{k-1}{n-1}$$ After I wrote out the resulting expression: $$\sum_{k = 0}^{\frac{n}{2} - \sqrt{n}} k \binom{n}{k} = \sum_{k = 1}^{\frac{n}{2} - \sqrt{n}} k \binom{n}{k} = \sum_{k = 1}^{\frac{n}{2} - \sqrt{n}} n \binom{n - 1}{k -1} = n \sum_{k = 1}^{\frac{n}{2} - \sqrt{n}} \binom{n - 1}{k -1}$$

At this point, I do not know what to do next. At first, I thought about expressing something through the formula $(1+x)^n$ taking derivatives and finding functions. I also tried to get this amount through the binomial of Newton, but failed.

  • $\begingroup$ I would convert to Generalized Hypergeometric function and then try to use the standard technique. I presume you mean the asymptotic as n->\inf ? Since the sum is already finite I also presume you want to divide the terms between f(n),g(n) in some specified manner? $\endgroup$ – rrogers Apr 6 at 18:43
  • $\begingroup$ @rrogers Yes, I want to divide the terms between f(n) and g(n), using asymptotic as asymptotic as n->\inf . $\endgroup$ – Andrew Apr 7 at 10:45
  • $\begingroup$ I don't have time right now but here is an approach. 1), change the summation limit to m and solve for n for the summand. This introduces a stepwise ambiguity but does give a generating function that matches the original (sometimes). 2) change the factorials to Gamma functions. 3) write the result as partial sums of the resulting Hypergeometric function using DLMF 16.2.4 dlmf.nist.gov/16.2.E4 . 4) use DLMF 16.11 dlmf.nist.gov/16.11.iii . This has a limitation on the indexing variable but that might be able to be sidestepped by contigous identities or using even/odd part $\endgroup$ – rrogers Apr 8 at 12:27
  • $\begingroup$ My last comment: I don't know whether that's close enough to your original question but it seems to fit (mostly). $\endgroup$ – rrogers Apr 8 at 12:28

The summand has a peak at $(n - 1)/2$, where for large $n$ and constant $\xi \in (-1, 1)$ it can be approximated as $$\binom {n - 1} {\frac {n - 1} 2 + \frac {n \xi} 2} \sim \frac {2^n} {\sqrt {2 \pi n}} e^{n \phi(\xi)}, \\ \phi(\xi) = -\frac 1 2 (1 - \xi) \ln(1 - \xi) - \frac 1 2 (1 + \xi) \ln(1 + \xi).$$ The maximum of $\phi$ is located at zero, where $\phi(\xi) \sim -\xi^2/2$.

$f$ can be derived by proving that the sum is asymptotically equivalent to the corresponding integral. The integral is then amenable to Laplace's method (a variation of the method where the critical point is asymptotically close to one of the endpoints): $$n \sum_{k = 0}^{n/2 - \sqrt n - 1} \binom {n - 1} k \sim \frac {n^2} 2 \frac {2^n} {\sqrt {2 \pi n}} \int_{-\infty}^{-2/\sqrt n} e^{-n \xi^2/2} d\xi = \operatorname{erfc}(\sqrt 2) n \hspace{1.5px} 2^{n - 2}.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.