Bounded convolutions with binomial coefficients

Question

I need to figure out a nice family of decaying functions such that

$\sum_{d=2}^k {k \choose d} f_k(d) \leq 1/k$ and $f_k(d)\geq f_k(d+1)$

How can I figure out what good candidates could be? Any leads or ideas?

Answer 1

I managed to find a few alternatives:

Binomial Theorem

$f_k(d) = x^d$ works for any $x$ such that $(1+x)^k \leq 1/k + 1 + kx$. The suggested $1/k^2$ from The Masked Avenger is one such $x$, but solving for each $k$ in turn one can see that we can do far better than $1/k^2$.

Vandermonde's Identity

From the identity ${m+n \choose r} = \sum_{d=0}^r{m\choose k}{n\choose r-k}$ we can extract the function families

$f_k^m(d) = \frac{{m\choose k-d}}{{k+m\choose k}\cdot k}$

that provide a viable family of functions for each $m\geq k$. These functions are not monotonic, but they are only really needed for an upper bound, so that still works. The $m$ forms a kind of a shape parameter -- higher $m$ means more mass is concentrated early on, while a lower value for $m$ means larger mass allowed in the middle of the sequence.

In particular, the Vandermonde-derived bounds allow for a much slower decay, while the exponential bounds allow for a large amount of mass used early in the sequence.