0
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ A better bound (probably far from sharp) is obtained using $n-i\leq n$, giving $f(n,k)\leq n2^k$. $\endgroup$
    – abx
    Dec 27 '13 at 15:18
  • 1
    $\begingroup$ 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$. $\endgroup$ Dec 27 '13 at 16:44
  • $\begingroup$ 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)$ $\endgroup$
    – Stopple
    Dec 27 '13 at 18:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ira Gessel
    Dec 27 '13 at 19:51
  • 1
    $\begingroup$ Here is the MSE duplicate: math.stackexchange.com/questions/619327/… $\endgroup$ Dec 28 '13 at 8:31
3
$\begingroup$

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, ....)

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 27 '13 at 20:33
  • $\begingroup$ Looks like I forgot a -n because of the i=0 term. Oops. $\endgroup$ Dec 27 '13 at 20:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.