Maths Olympiad Prep

Library / /108 of 520

Combinatorics Difficulty 5.2 AIME, harder Find the answer

25. Determine
limni=0n1(ni). \lim _{n \rightarrow \infty} \sum_{i=0}^{n} \frac{1}{\binom{n}{i}} .
(Note: Here (ni)\binom{n}{i} denotes n!i!(ni)!\frac{n!}{i!(n-i)!} for i=0,1,2,3,,ni=0,1,2,3, \cdots, n.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

25. Answer. 2
Solution. Let
an=i=0n(ni)1 a_{n}=\sum_{i=0}^{n}\binom{n}{i}^{-1}

Assume that n3n \geq 3. It is clear that
an=2+i=1n1(ni)1>2 a_{n}=2+\sum_{i=1}^{n-1}\binom{n}{i}^{-1}>2

Also note that
an=2+2/n+i=2n2(ni)1 a_{n}=2+2 / n+\sum_{i=2}^{n-2}\binom{n}{i}^{-1}

Since (ni)(n2)\binom{n}{i} \geq\binom{ n}{2} for all ii with 2in22 \leq i \leq n-2,
an2+2/n+(n3)(n2)12+2/n+2/n=2+4/n. a_{n} \leq 2+2 / n+(n-3)\binom{n}{2}^{-1} \leq 2+2 / n+2 / n=2+4 / n .

So we have show that for all n3n \geq 3,
2<an2+4/n. 2<a_{n} \leq 2+4 / n .

Thus
limnan=2 \lim _{n \rightarrow \infty} a_{n}=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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.