# Asymptotic growth for $\sum_{i=1}^{n-1}(n-i)\binom{k}{i}$ [closed]

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.

• A better bound (probably far from sharp) is obtained using $n-i\leq n$, giving $f(n,k)\leq n2^k$.
– abx
Dec 27 '13 at 15:18
• I would just like to point out that Mathematica computes the closed form of the sum as $\binom{k}{n+1} \, _2F_1(2,-k+n+1;n+2;-1)+\left(2^k-1\right) n-2^{k-1} k$. Dec 27 '13 at 16:44
• Mathematica gives further the asymptotic expansion as $n\to\infty$, namely $\left(2^k-1\right) n-2^{k-1} k+O\left(\left(\frac{1}{n}\right)^2\right)$ Dec 27 '13 at 18:32
• For $n>k$ the sum is equal to $(2^k-1)n -2^{k-1}k$ (by the binomial theorem) so Mathematica's asymptotic expansion isn't very helpful. Dec 27 '13 at 19:51
• Here is the MSE duplicate: math.stackexchange.com/questions/619327/… Dec 28 '13 at 8:31

For $n$ and $k$ fixed, the sequence $\left\{(n-i){k \choose i} \right\}_{i=1}^{n-1}$ is strongly unimodal (that is, log concave), or at least a pencil and paper computation convinced me that it is. This allows one to estimate extremely well the sum, $f(n,k)$, particularly when $n$ is large. (The idea is that beyond the mode, the tails go to zero faster than geometric, and so errors are relatively easy to estimate; we just have to look at the behaviour of the ratios of consecutive terms, ....)

• Write the sum as n* sum k choose i - sum i (k choose i), and you get (2n-k)(2^(k-1))alpha, where alpha is 1 if n > k otherwise alpha < 1 is an interesting fraction you get to compute. Dec 27 '13 at 20:33
• Looks like I forgot a -n because of the i=0 term. Oops. Dec 27 '13 at 20:49