Maths Olympiad Prep

Library / /21 of 64

Combinatorics Difficulty 7.8 National olympiad, round 2 Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

The answer is 3+52\frac{3+\sqrt{5}}{2}. Note that for m>n+1m > n+1, both binomial coefficients are nonzero and their ratio is (mn1)/(m1n)=m!n!(mn1)!(m1)!(n1)!(mn+1)!=mn(mn+1)(mn). {m\choose n-1}/{m-1\choose n} = \frac{m!n!(m-n-1)!}{(m-1)!(n-1)!(m-n+1)!} = \frac{mn}{(m-n+1)(m-n)}. Thus the condition (mn1)>(m1n){m\choose{n-1}} > {{m-1}\choose n} is equivalent to (mn+1)(mn)mn<0(m-n+1)(m-n)-mn < 0. The left hand side of this last inequality is a quadratic function of mm with roots α(n)=3n1+5n22n+12,β(n)=3n15n22n+12, \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 5n22n+1=4n2+(n1)2>05n^2-2n+1 = 4n^2+(n-1)^2 > 0; it follows that mm satisfies the given inequality if and only if β(n)<m<α(n)\beta(n) < m < \alpha(n). (Note in particular that since α(n)β(n)=5n22n+1>1\alpha(n)-\beta(n) = \sqrt{5n^2-2n+1} > 1, there is always some integer mm between β(n)\beta(n) and α(n)\alpha(n).) We conclude that M(n)M(n) is the greatest integer strictly less than α(n)\alpha(n), and thus that α(n)1M(n)<α(n)\alpha(n)-1 \leq M(n) < \alpha(n). Now limnα(n)n=limn31n+52n+1n22=3+52 \lim_{n\to\infty} \frac{\alpha(n)}{n} = \lim_{n\to\infty} \frac{3-\frac{1}{n}+\sqrt{5-\frac{2}{n}+\frac{1}{n^2}}}{2} = \frac{3+\sqrt{5}}{2} and similarly limnα(n)1n=3+52\lim_{n\to\infty} \frac{\alpha(n)-1}{n} = \frac{3+\sqrt{5}}{2}, and so by the sandwich theorem, limnM(n)n=3+52\lim_{n\to\infty} \frac{M(n)}{n} = \frac{3+\sqrt{5}}{2}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.