For what values of $n$ do more than two thirds of subsets of $[n]$ have size beteen $\frac{n}{3}$ and $\frac{2n}{3}$

51 Views Asked by At

My actual problem is slightly different.

For what values of $n$ do we have:

$2\sum_{i=1}^{\lfloor n/3 \rfloor}\binom{n}{i}\geq \sum\limits_{i=\lfloor n/3 \rfloor+1}^{\lceil n/2 \rceil-1} \binom{n}{i}$?

I haven't taken any probability theory yet, so I am not sure, I think we have to do some approximations using the binomial distribution curve. I think that for large values of $n$ say $n>10$ it won't hold, but i'm not sure what tools to use.


Edit: the following c++ program checks for all integers between $1$ and $50$:

#include <cstdio>
long long B[50][50];

int main(){
    for(int i=0;i<50;i++){
        B[i][0]=1;
    }
    for(int i=1;i<50;i++){
        for(int j=1;j<50;j++){
            B[i][j]=B[i-1][j]+B[i-1][j-1];
        }
    }
    for(int i=1;i<50;i++){
        long long sum1=0;
        for(int j=1;j<=i/3;j++){
            sum1+=B[i][j];
        }
        long long sum2=0;
        for(int j=i/3+1;2*j<i;j++){
            sum2+=B[i][j];
        }
        if(2*sum1>=sum2){
            printf("%d\n",i);
        }
    }
}

It appears to work only for $1,2,3,4,5,6,7,8,9,10,12$. So now we need to prove it is never true for $n>50$