I may as well write down how I've been attacking this, although I don't have a solution yet. Sequences $(p_i)$ of nonnegative integers with sum $r$ are in bijection with weakly increasing $r$-tuples $(n_1, n_2, \ldots, n_r)$ of positive integers. Specifically, given the sequence $(p_0, p_1, p_2, \ldots)$, form the sequence of partial sums $(q_1, q_2, \ldots)$ given by $q_i:=p_0+p_1+\ldots+p_{i-1}$. Let $n_j$ be the minimal $i$ for which $q_i \geq j$. For example, $(1,0,0,1,0,0,2,0,0,\ldots)$ corresponds to $(1, 4, 7,7)$. So, we want to compute the sum over all weakly increasing $r$-tuples and prove it is equal to $1/r!$.
For each weakly increasing $r$-tuple, let us sum instead over all $r!$ permutations of the $r$-tuple. So we can view our sum as being over all $r$-tuples of nonnegative integers, and we want to prove now that the sum is $1$. One difficulty is that some $r$-tuples will appear more than once. For example, $(1,4,7,7)$ will appear twice, because the permutation which switches the $7$'s stabilizes this quadruple. It turns out that the multiplicity of an $r$-tuples is precisely $\prod (p_i)!$. So, what we want to show is that
$$\sum_{n_1, n_2, \ldots, n_r \geq 0} \frac{1}{\prod (p_i)! \prod \binom{p_{k-1}+p_k+k}{k}} =1$$
Now, when none of the $n_i$ are equal to each other, and when none of them differ by $1$, the summand is
$$\frac{1}{n_1(n_1+1)n_2(n_2+1) \cdots n_r(n_r+1)} = \left( \frac{1}{n_1} - \frac{1}{n_1+1} \right) \cdot \left( \frac{1}{n_2} - \frac{1}{n_2+1} \right) \cdots \left( \frac{1}{n_r} - \frac{1}{n_r+1} \right).$$
This is set up beautifully to telescope. If I could just find a similar nice description for when the $n_i$ collide or are adjacent ...
First, what the Stirling bound or Stanica's result give is already a $(1+O(n^{-1}))$ approximation of $\binom nk$, hence the only problem can be with the sum. I don't know how to do that with such precision, but it's easy to compute it up to a constant factor by approximating with a geometric series:
$$\sum_{i\le k}\binom ni=\begin{cases}\Theta(2^n)&k\ge n/2-\sqrt n,\\\\\Theta\left(\left(1-\frac{2k}n\right)^{-1}\binom nk\right)&k\le n/2-\sqrt n.\end{cases}$$
More generally,
$$\sum_{i\le k}\binom ni(1-\epsilon)^{n-i}\epsilon^i=\begin{cases}\Theta(1)&k\ge\epsilon n-s,\\\\\Theta\left(\frac{\epsilon(n-k)}{\epsilon n-k}\binom nk(1-\epsilon)^{n-k}\epsilon^k\right)&k\le\epsilon n-s,\end{cases}$$
where $s=\sqrt{n\epsilon(1-\epsilon)}$. Cf. the appendix to my paper http://math.cas.cz/~jerabek/papers/wphp.pdf .
Best Answer
Ira told me this interesting constant term identity.
It is not hard to see that the problem is equivalent to showing the following constant term identity: $$ \binom{n}{k} = \frac{(1-x^n)^n}{(1-x^k)^k (1-x^{n-k})^{n-k} x^{k(n-k)}} \Big|_{x^0},$$ where $0\le k \le n$. To obtain the given binomial sum identity, simply apply the binomial theorem and equate coefficients.
The proof replies on the following two key facts.
So the constant term can be regarded as an identity in $\mathbb{Q}((x))$ and also an identity in $\mathbb{Q}((x^{-1}))$.
We will use partial fraction decomposition to obtain different formula of $F(x) \big|_{x^0}$ and deduce that the constant term is equal to $\binom{n}{k}$.
Firstly notice that it is hard to work directly using partial fraction decomposition of $F(x)$. We consider the partial faction of $F(x,t)$ with $F(x)=F(x,1)$ instead. $$ F(x,t)=\frac{(1-t^2 x^n)^n}{(1-tx^k)^k (1-tx^{n-k})^{n-k} x^{k(n-k)}}$$ Now we have a unique partial fraction decomposition with respect to $x$ $$ F(x,t) =C+ P_+(x)+P_-(x^{-1}) + \frac{N_1(x)}{(1-tx^k)^k} + \frac{N_2(x)}{(1-tx^{n-k})^{n-k}},$$ where $P_{\pm}(x)$ are polynomials with $P_{\pm}(0)=0$, $\deg N_1(x)<k^2$, $\deg N_2(x)<(n-k)^2$, and every term may contain the slack variable $t$ which will be set equal to $1$, then by working in $\mathbb{Q}((x))$ and $\mathbb{Q}((x^{-1}))$, we get \begin{align*} F(x) \big|_{x^0} &=C\big|_{t=1}, \\ F(x) \big|_{x^0} &=(C+ N_1(0)+N_2(0)) \big|_{t=1}. \end{align*} Consequently $(N_1(0)+N_2(0))\big|_{t=1}=0$.
Next we split $1-t^2x^n$ as $(1-tx^k)+tx^{k}(1-tx^{n-k})$ and apply the binomial theorem. \begin{align*} F(x,t)&=\frac{(1-t^2x^n)^n}{(1-tx^k)^k (1-tx^{n-k})^{n-k} x^{k(n-k)}} \\ &= \frac{\sum_{i=0}^n \binom{n}{i}(1-tx^k)^i (tx^k(1-tx^{n-k}))^{n-i} }{(1-tx^k)^k (1-tx^{n-k})^{n-k} x^{k(n-k)}} \\ &= \binom{n}{k}t^k + \sum_{i=0}^{k-1} \binom{n}{i} \frac{t^{n-i} x^{k(k-i)} (1-tx^{n-k})^{k-i}}{(1-tx^k)^{k-i} } + \sum_{i=k+1}^{n} \binom{n}{i} \frac{t^{n-i} x^{-k(i-k)} (1-tx^k)^{i-k}}{(1-tx^{n-k})^{i-k} } \end{align*} If we work in $\mathbb{Q}((x))$, we get $F(x,1)\big|_{x^0} = \binom{n}{k} + N_2(0)\big|_{t=1},$ since the constant term of the middle term is clearly $0$.
A similar argument shows that $F(x)\big|_{x^0} = \binom{n}{k} + N_1(0)\big|_{t=1}.$ This should also follows from the observation that $F(x,t)$ is invariant under replacing $k$ by $n-k$. Thus we obtain $$ 2 F(x,1)\big|_{x^0} = 2 \binom{n}{k} + N_1(0)\big|_{t=1}+N_2(0)\big|_{t=1}= 2 \binom{n}{k}.$$ This concludes that $F(x)\big|_{x^0}=\binom{n}{k}.$