4
$\begingroup$

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.

$\endgroup$
5
  • 4
    $\begingroup$ I don't think this tiny problem is worth special investigation. I can recommend an elementary and very nice introduction to problems like this: N. G. de Bruijn, Asymptotic methods in analysis (it's presented on books.google.com). For specific $j$, you consider the quotient of your binomials which is a rational function in both $n$ and $k$, fix one of these two parameters and solve the inequality with respect to the other... This is, of course, quite standard. $\endgroup$ May 19, 2010 at 0:25
  • 1
    $\begingroup$ @Pencil: I won't judge. The author may have reasons for it. $\endgroup$ May 19, 2010 at 0:34
  • $\begingroup$ @Wadim - That is essentially the approach I had taken for j=1. Unfortunately, unless I am missing something, doing this for higher j will involve finding the roots of a degree j+1 polynomial, which is ugly for j=2 and impossible if we get much higher... And yes, this is a question that fell out of a bigger piece of research, but it seemed standard enough that the answer might be well known. $\endgroup$
    – user4535
    May 19, 2010 at 1:54
  • 1
    $\begingroup$ @DG: Yes, the resulted polynomials do not have any "nice" properties. That is why I recommend a book on asymptotic methods: there can be a nicer form for j "sufficiently large". $\endgroup$ May 19, 2010 at 3:21
  • $\begingroup$ @Wadim Thanks for the Brujin reference. I have a problem something like this and wondering how appropriate it is to post it on MO. $\endgroup$
    – user2529
    May 19, 2010 at 15:04

2 Answers 2

2
$\begingroup$

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}$.

$\endgroup$
2
  • $\begingroup$ This is quite good. I was hoping for something that worked in general and not just asymptotically, but this is more useful than what I could come up with on my own. $\endgroup$
    – user4535
    May 19, 2010 at 15:49
  • $\begingroup$ MathOverflow at your service :) $\endgroup$ May 19, 2010 at 17:58
0
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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