Consider the two sequences $$a(n)=\sum_{k=1}^n\binom{n}k\sum_{j=1}^{k/2}\binom{k}{2j}\frac{(2j)!}{j!}$$ and $$b(n)=\sum_{k=0}^n\binom{n}k^2k!$$

QUESTION. Is this true? $$\frac{a(n)}{b(n)}\longrightarrow 0 \qquad \text{as} \qquad n\rightarrow\infty.$$


It is very much true. We may simplify the first sum by changing the order of summation: $$\sum_k \binom{n}k\binom{k}{2j}=\sum_k\binom{n}{2j}\binom{n-2j}{k-2j}=2^{n-2j}\binom{n}{2j}.$$

Now the summand for $a(n)$ is $$2^{n-2j}\binom{n}{2j}\frac{(2j)!}{j!}=2^{n-2j}\frac{n!}{(n-2j)!j!}.$$ The denominator is not less than, say, $(n/3)!$, so the fraction is less than $n!/100^n$ for large $n$, and even if we sum up $n$ such fractions we get much less than $n!<b(n)$.

  • $\begingroup$ Thanks as always. $\endgroup$ – T. Amdeberhan Mar 1 at 21:26

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.