Putnam 2016, Problem A-2

Given a positive integer \( n \), let \( M(n) \) be the largest integer \( m \) such that
\[
\binom{m}{n-1} > \binom{m-1}{n}.
\]
Evaluate
\[
\lim_{n \to \infty} \frac{M(n)}{n}.
\]

Solution:
The answer is $\frac{3+\sqrt{5}}{2}$. Note that for $m > n+1$, both binomial coefficients are nonzero and their ratio is

$$\binom{m}{n-1}/\binom{m-1}{n} = \frac{m!n!(m-n-1)!}{(m-1)!(n-1)!(m-n+1)!} = \frac{mn}{(m-n+1)(m-n)}.$$

Thus the condition $\binom{m}{n-1} > \binom{m-1}{n}$ is equivalent to $(m-n+1)(m-n) - mn < 0$. The left hand side of this last inequality is a quadratic function of $m$ with roots

$$\alpha(n) = \frac{3n-1+\sqrt{5n^2-2n+1}}{2}, \quad \beta(n) = \frac{3n-1-\sqrt{5n^2-2n+1}}{2},$$

both of which are real since $5n^2-2n+1 = 4n^2+(n-1)^2 > 0$; it follows that $m$ satisfies the given inequality if and only if $\beta(n) < m < \alpha(n)$. (Note in particular that since $\alpha(n)-\beta(n) = \sqrt{5n^2-2n+1} > 1$, there is always some integer $m$ between $\beta(n)$ and $\alpha(n)$.)