How can we show that $\binom{\lfloor2^{k/2}\rfloor}{k}2^{1-\binom{k}{2}}<1$ when $k\geq 3$? I tried using Stirling approximation but it turned out to be a mess, do you see a smarter proof?
More generally, this inequality arises when we want to decide for which natural numbers $n$ $$\binom{n}{k}2^{1-\binom{k}{2}}<1$$ how might one even think of something like $n=\lfloor2^{k/2}\rfloor$ and $k\geq 3$?
Just use the upper bound ${n \choose k}\leq (en/k)^k$. Applying this here with $n=\lfloor 2^{k/2}\rfloor$ gives \begin{equation} {\lfloor 2^{k/2}\rfloor \choose k}2^{1-{k \choose 2}}\leq 2\cdot \frac{e^k}{k^k} \cdot 2^{(k^2/2)-k(k-1)/2}=2\left(\frac{e\sqrt{2}}{k}\right)^k. \end{equation} This is less that $1$ for $k\geq 5$. For $k=3,4$, one can check your inequality holds by hand pretty directly.
As for how you see this quantity, the above inequality suggests you should take $n$ such that $n^k\approx 2^{k(k-1)/2}$, which suggests taking $n\approx 2^{k/2}$.