# Estimation of a combinatorial sum when $n$ is large

Suppose $c,t$ are such that, $0< c< 1$ constant and $cn\leq t \leq n$. I want to have an estimation of

$\sum _{i=0}^{cn} {cn\choose {i}}{(1-c)n \choose t-i} 2^{t-i}$

when n goes to infinity.

Can I bound it by $2^{c'n}$ for some $0<c'<log_2(3)$?

I have no idea to do that.Is there any hint?

Thanks!

• If $c=1/2$, and $i=n/4$, the corresponding summand is about $2^{n+t-n/4}$, which is much more than $2^{c'n}$ for $c'<1$. – Fedor Petrov Nov 9 '17 at 9:10
• In general combinatorial sums such as this one, with all terms positive, can be estimated to within a factor of the length of the sum by just approximating how large an individual summand cn get. – Noam D. Elkies Nov 9 '17 at 15:19

Here is a special case where your [original] estimate [of $c'<1$] does not work. Let $c\le 1/2$, $cn\le t\le (1-c)n$, and assume that $cn$ and $t$ are integers. Let us get rid of of the second factorial. Then your sum would be $2^{t-cn}3^{cn}$. So, it cannot be bounded by $2^{c'n}$ for $c'<1$, nor can your original sum.
On the other hand, a very rough estimate (replacing $2^{t-i}$ with $2^t$) gives an upper bound of $\binom{n}{t}2^t$ whose $n$th root even in the worst case of $t=2n/3$ approaches $3$. So, I guess your $c'\le\log_2{3}$, certainly less than $2$.
• @user115608 This is more likely. Try letting $t$ and $m=cn$ be integers first. – Alexander Burstein Nov 9 '17 at 19:09
• @user115608 I edited my answer now as well. It looks like $c'\le\log_2{3}$. – Alexander Burstein Nov 10 '17 at 2:50
• sorry,I remembered sth and now I know it is certainly less than $3^n$ ,but $\log_2(3)$ is not enough for me, so I edited again. – user115608 Nov 10 '17 at 15:15
• @user115608 See the other answer for why $c'<\log_2 3$. – Alexander Burstein Nov 11 '17 at 22:02
Of course, you may estimate $\binom{cn}i$ as $2^{cn}$ and $\binom{(1-c)n}{t-i}2^{t-i}$ as $(1+2)^{(1-c)n}$, totally you get $(2^c3^{1-c})^n$, the exponent is strictly less than 3.