Can anyone help me to give me a detailed proof (or disproof) of the following $\sum\limits_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right)>c\cdot n$ for some constant $c>0$, where $k=\Big[\frac{n}{2\log_2 n}\Big]$ and $[x]$ denotes the integer part of $x$, for example, $x=9.033$, then $[x]=9$.
Thanks very much for your help!!
Note that, assuming $n\geq k$
$$ \begin{align} \sum_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right) &= \log_2\left(\prod_{i=0}^{k-2}\frac{n-i}{k-i-1}\right) \\ &= \log_2\left(\frac{n!}{(k-1)!(n-(k-1))!}\right) \\ &= \log_2 {n \choose k-1 } \end{align}$$ Can you take it from here? A hint would be to use some inequalities concerning $\log_2 (n!)$ and $n$.
I would suggest looking at http://people.cs.uchicago.edu/~laci/CLASS/HANDOUTS/factorialasymp.pdf and adapting the inequalities to $\log_2$ instead of $\log_e = \ln$.
Alternative Aprroach I (Current method needs tighter lower bound)
Recall that for $1\leq m \leq n$ $$ \left(\frac{n}{m}\right)^m \leq {n \choose m} \leq \left(\frac{en}{m}\right)^m. $$ Therefore, by monotonicity of $\log_2$ and using $m=k-1$ $$ \begin{align} \log_2{n \choose k-1} \geq (k-1)\log_2\left(\frac{n}{k-1}\right). \end{align} $$ Now, recall the definition of $k$, i.e. that $k = \left[\frac{n}{2\log_2(n)}\right]$, then $$ \frac{n}{2\log_2(n)} - 1 \leq k \leq \frac{n}{2\log_2(n)} + 1, $$ thus $$ \log_2\left(\frac{n}{k-1}\right) \geq \log_2(2\log_2(n)) $$ which gives $$ \begin{align} \log_2{n \choose k-1} &\geq (k-1)\log_2(2\log_2(n)) \\ &\geq \left(\frac{n}{2\log_2(n)} - 2\right)\log_2(2\log_2(n)), \end{align} $$ which is positive for large enough $n$. Then apply various inequalities regarding logarithms to obtain your answer.
Alternative Approach II
$$ \begin{align} \sum_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right) &= \sum_{i=0}^{k-2}\log_2(n-i) - \sum_{i=0}^{k-2}\log_2(k-i-1) \end{align} $$ Then, using the fact that $$ \log(a) - \log(b) = \int_{b}^{a}\frac{1}{t} dt, $$ we have that $$ \begin{align} \sum_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right) = \frac{1}{\log(2)}\sum_{i=0}^{k-2}\log\left(\frac{n-i}{k-i-1}\right)&= \sum_{i=0}^{k-2}\int_{k-i-1}^{n-i}\frac{1}{t}dt. \end{align} $$ Then, letting $ u = t + i$, we have that $$ \begin{align} \frac{1}{\log(2)}\sum_{i=0}^{k-2}\log\left(\frac{n-i}{k-i-1}\right) &= \int_{k-1}^{n}\sum_{i=0}^{k-2}\frac{1}{u-i}dt \\ &\geq (k-1)\int_{k-1}^{n}\frac{1}{u-k+2} du \\ &= (k-1) \log\left(n-k+2\right)\\ &\geq \frac{(k-1)(n-(k-1)}{n+1-(k-1)} \end{align} $$ Which is again is not tight enough. A similar approach but with different, but tighter bounds, is advised.