For positive integers $n,k$, define $$f(n,k):=\sum_{i=1}^{n-1}(n-i)\binom{k}{i}.$$

What are upper and lower bounds of $f(n,k)$ by simpler terms? (e.g. finding bounds which are not a summation like this one.) How fast does $f(n,k)$ grow asymptotically in $n$ and $k$?

If we loosely bound $\binom{k}{i}\leq 2^k$, then we get $f(n,k)\leq 2^{k-1}n(n-1)<2^{k-1}n^2$.

The term $f(n,k)$ arises as an answer to the following combinatorics question.

3more comments