I came across this partial sum which I cannot find reasonable bounds on; I feel this must be known in the literature, but I do not know where to look. Here is the problem:


Let $s\in (0,1)$ and consider the binomial sum
$$
\boldsymbol{(\*)}\qquad \sum\_{k=1}^N\, \binom{N}{k}\, \frac1{k^s}
$$
are there any known good upper and lower bounds on $\boldsymbol{(\*)}$?



Two-Sided Bounds on Binomial Sum
$\newcommand{\Si}{\Sigma}$We have to lower- and upper-bound
\begin{equation\*}
 \Si\_N:=\sum\_{k=1}^N\,\binom Nk\, \frac1{k^s}. 
\end{equation\*}


Note that
\begin{equation\*}
 \Si\_N=2^N EX^{-s}\,1(X\ge1), \tag{10}\label{10}
\end{equation\*}
where $X$ is a random variable with the binomial distribution with parameters $N,1/2$.


By Jensen's inequality applied to the convex function $[1,\infty)\ni x\mapsto x^{-s}$,
\begin{equation\*}
 EX^{-s}\,1(X\ge1)=P(X\ge1)\,E(X^{-s}|X\ge1) \\ 
 \ge P(X\ge1)\,(E(X|X\ge1))^{-s}. \tag{20}\label{20}
\end{equation\*}
Also,
\begin{equation\*}
 E(X|X\ge1)=\dfrac{EX\,1(X\ge1)}{P(X\ge1)}=\dfrac{EX}{P(X\ge1)}=\dfrac{N/2}{P(X\ge1)} \tag{30}\label{30}
\end{equation\*}
and $P(X\ge1)=1-2^{-N}$. So, by \eqref{10}, \eqref{20}, and \eqref{30}, we get a lower bound on $\Si\_N$:
\begin{equation\*}
 \Si\_N\ge L\_N:=M\_N\,(1-2^{-N})^{1+s}, \tag{33}\label{33}
\end{equation\*}
where
\begin{equation\*}
 M\_N:=\frac{2^N}{(N/2)^s}. \tag{35}\label{35}
\end{equation\*}


To get an upper bound on $\Si\_N$, write
\begin{equation\*}
 EX^{-s}\,1(X\ge1)=E\_1+E\_2, \tag{40}\label{40}
\end{equation\*}
where
\begin{equation\*}
 E\_1:=EX^{-s}\,1(X\ge\tfrac N2\,(1-h)),\quad \\ E\_2:=EX^{-s}\,1(1\le X<\tfrac N2\,(1-h)), 
\end{equation\*}
and $h\in(0,1-2/N]$. Next,
\begin{equation\*}
 E\_1\le(\tfrac N2\,(1-h))^{-s}. \tag{50}\label{50}
\end{equation\*}
By Hoeffding's inequality,
\begin{equation\*}
 E\_2\le P(1\le X<\tfrac N2\,(1-h)) \\ 
\le \exp(-\tfrac2N\,(\tfrac{Nh}2)^2)=e^{-h^2 N/2}=N^{-c^2/2} \tag{60}\label{60}
\end{equation\*}
if $h=c\sqrt{\frac{\ln N}N}\in(0,1-2/N]$. So, in view of \eqref{10}, \eqref{40}, \eqref{50}, \eqref{35}, and \eqref{60}, we get an upper bound on $\Si\_N$:
\begin{equation\*}
 \Si\_N\le U\_N:=M\_N\,\Big[\Big(1-c\sqrt{\frac{\ln N}N}\,\Big)^{-s}
 +2^{-s}N^{s-c^2/2}\Big]. 
 \tag{70}\label{70}
\end{equation\*}


Fixing now any real $c>\sqrt{2s}$, letting $N\to\infty$, and looking at \eqref{33} and \eqref{70}, we see that $L\_N\sim M\_N\sim U\_N$ and hence
\begin{equation\*}
 \Si\_N\sim L\_N\sim U\_N\sim M\_N=\frac{2^N}{(N/2)^s}. 
\end{equation\*}
Thus, our lower and upper bounds $L\_N$ and $U\_N$ on $\Si\_N$ are asymptotically exact for large $N$.


