2
$\begingroup$

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!

Improve this question
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Fedor Petrov Nov 9 '17 at 9:10
  • $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Nov 9 '17 at 15:19
5
$\begingroup$

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$.

Improve this answer
$\endgroup$
  • $\begingroup$ What do you think now?I edited the question. $\endgroup$ – user115608 Nov 9 '17 at 19:01
  • 1
    $\begingroup$ @user115608 This is more likely. Try letting $t$ and $m=cn$ be integers first. $\endgroup$ – Alexander Burstein Nov 9 '17 at 19:09
  • $\begingroup$ @user115608 I edited my answer now as well. It looks like $c'\le\log_2{3}$. $\endgroup$ – Alexander Burstein Nov 10 '17 at 2:50
  • $\begingroup$ 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. $\endgroup$ – user115608 Nov 10 '17 at 15:15
  • $\begingroup$ @user115608 See the other answer for why $c'<\log_2 3$. $\endgroup$ – Alexander Burstein Nov 11 '17 at 22:02
4
$\begingroup$

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.

Improve this answer
$\endgroup$

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.