Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
4  
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. –  Wadim Zudilin May 19 '10 at 0:25
1  
@Pencil: I won't judge. The author may have reasons for it. –  Wadim Zudilin May 19 '10 at 0:34
    
@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. –  user4535 May 19 '10 at 1:54
    
@Wadim: Thanks. –  Kerry May 19 '10 at 2:04
1  
@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". –  Wadim Zudilin May 19 '10 at 3:21
show 1 more comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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. –  user4535 May 19 '10 at 15:49
    
MathOverflow at your service :) –  Kevin O'Bryant May 19 '10 at 17:58
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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