Question

I was curious if anyone has a reference for a formula giving the values of n and k so that $\binom{n}{k}<\binom{n+j}{k-1}$ for a fixed $j$.

Clearly this will be true if $k>\frac{n}{2}$ because then one will have that $\binom{n}{k}\le\binom{n}{k-1}<\binom{n+j}{k-1}$. One can improve on this result, and in the case where $j=1$ I have found precise conditions on $k$ in terms of $n$, but my approach is rather blunt and it seems like the general case will be quite tedious using my methods, even though this seems like a question that likely has an elegant combinatorial solution. I was wondering if anyone knows where a solution appears.

Answer 1

It doesn't get that ugly, if you're mainly concerned with large $n$ and $k$. Simple order-of-magnitude stuff indicates that something like $k>\alpha n$ is true (where $\alpha$ depends on $j$).

The inequality $\binom{n}{k}<\binom{n+j}{k-1}$ is exactly equivalent to $$1 < \frac{k}{n-k+1} \prod_{i=1}^j \frac{n+i}{n+i-k+1}.$$ Setting $k\approx \alpha n$ and letting $n\to \infty$, this implies the inequality $$\frac{\alpha}{(1-\alpha)^{j+1}} \geq 1.$$ This is easy to solve for $j$. To solve for $\alpha$ is rougher. Since $(1-m/j)^j\to e^{-m}$, one can see that for large $j$ we must have $\alpha>m/j$ (specifically, for each $m$, if $j$ is sufficiently large then $\alpha>m/j$).

It seems to me that $$\frac 1j < \alpha_j < \frac{\log j}{j}$$ for $j\ge 5$ follows from calculus. So here's the result: Let $\alpha_j$ be the unique real solution to $\alpha=(1-\alpha)^{j+1}$ with $0<\alpha<1$. If $n,k$ are sufficiently large and $k>\alpha_j n$, then $\binom{n}{k}<\binom{n+j}{k-1}$. In particular, for each $j\ge 5$, if $n,k$ are sufficiently large with $k>\frac{\log(j)}{j} n $, then $\binom{n}{k}<\binom{n+j}{k-1}$.

Answer 2

I think some computation can be done like this(I guess that's the tedious math you mentioned):

Mark $C^{n}_{k}=P$;

and $C^{n+j}_{k-1}=Q$, we have $\frac{P}{Q}$ equal

$$\frac{(n!)}{(n-k)!k!}*\frac{(n+j-k+1)!(k-1)!}{(n+j)!}$$

Mark $n-k=S$, we have the above to be

$$\frac{(n!)}{S!k}*\frac{(S+j+1)!}{(n+j)!}=k^{-1}\frac{n!}{(n+j)!}\frac{(S+j+1)!}{S!}=k^{-1}\frac{\frac{n!}{(n+j)!}}{\frac{(S)!}{(S+j+1)!}}$$

Therefore we only need to consider the function $$A(m,j)=\frac{(m+j)!}{m!}$$ For changing $j$ we have $A(m,j+1)=A(m,j)*(m+j+1)$, for changing $m$ we have $$\frac{A(m,j)}{A(m+1,j)}=\frac{m+1}{m+j+1}<1$$

Therefore $A(m,j)$ increased by changing $m$ as well. Therefore we have the equation:

$$\frac{P}{Q}=\frac{S+j+1}{k}*\frac{A(n,j)}{A(s,j)}=(\frac{n+j+1}{k}-1)\frac{A(n,j)}{A(s,j)}$$

We consider the situation when we change $j$ or $k$. $P_{j},P_{k}$ means $P$'s value when we concern about $j$ or $k$. If we change $j$, we have $$\frac{P_{j}}{Q_{j}}/\frac{P_{j+1}}{Q_{j+1}}=\frac{1}{(S+j+2)}<1$$, moreover it has no lowerbound other than $0$ with $j$ increased. Therefore $\frac{P}{Q}$ is increasing with $j$ increased irrespective of $k$. Hence $P< Q$ will hold eventually when increasing $j$.

We consider the situation when we change $k$. In this situation $$j>\frac{P_{k}}{Q_{k}}/\frac{P_{k+1}}{Q_{k+1}}=\frac{(S+j+1)(k+1)}{(S+j)k}*\frac{S+j+1}{S+1}>1$$, therefore $\frac{P}{Q}$ decreases with one increases $k$ while fixing $j$.

The points $(j,k)$ such that $P=Q$ are satisfies this equation:

$$\frac{(n+j-k+1)(n+j-k)...(n-k+1)}{(n+j)(n+j-1)...(n+1)*n)}=\frac{k}{n}$$.This cannot hold if $k$ is a prime. I don't know how to push further at this point.