Maths Olympiad Prep

Library / /762 of 860

Algebra Difficulty 5.5 AIME, harder Find the answer

Evaluate the infinite sum n=0(2nn)15n\sum_{n=0}^{\infty}\binom{2 n}{n} \frac{1}{5^{n}}.

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

Solution

First Solution: Note that (2nn)=(2n)!n!n!=(2n)(2n2)(2n4)(2)n!(2n1)(2n3)(2n5)(1)n!=2n(2)nn!(12)(121)(122)(12n+1)=(4)n(12n)\binom{2 n}{n} =\frac{(2 n)!}{n!\cdot n!}=\frac{(2 n)(2 n-2)(2 n-4) \cdots(2)}{n!} \cdot \frac{(2 n-1)(2 n-3)(2 n-5) \cdots(1)}{n!} =2^{n} \cdot \frac{(-2)^{n}}{n!}(-\frac{1}{2})(-\frac{1}{2}-1)(-\frac{1}{2}-2) \cdots(-\frac{1}{2}-n+1) =(-4)^{n}\binom{-\frac{1}{2}}{n}. Then, by the binomial theorem, for any real xx with x<14|x|<\frac{1}{4}, we have (14x)1/2=n=0(12n)(4x)n=n=0(2nn)xn(1-4 x)^{-1 / 2}=\sum_{n=0}^{\infty}\binom{-\frac{1}{2}}{n}(-4 x)^{n}=\sum_{n=0}^{\infty}\binom{2 n}{n} x^{n}. Therefore, n=0(2nn)(15)n=1145=5\sum_{n=0}^{\infty}\binom{2 n}{n}(\frac{1}{5})^{n}=\frac{1}{\sqrt{1-\frac{4}{5}}}=\sqrt{5}. Second Solution: Consider the generating function f(x)=n=0(2nn)xnf(x)=\sum_{n=0}^{\infty}\binom{2 n}{n} x^{n}. It has formal integral given by g(x)=I(f(x))=n=01n+1(2nn)xn+1=n=0Cnxn+1=xn=0Cnxng(x)=I(f(x))=\sum_{n=0}^{\infty} \frac{1}{n+1}\binom{2 n}{n} x^{n+1}=\sum_{n=0}^{\infty} C_{n} x^{n+1}=x \sum_{n=0}^{\infty} C_{n} x^{n} where Cn=1n+1(2nn)C_{n}=\frac{1}{n+1}\binom{2 n}{n} is the nnth Catalan number. Let h(x)=n=0Cnxnh(x)=\sum_{n=0}^{\infty} C_{n} x^{n}; it suffices to compute this generating function. Note that 1+xh(x)2=1+xi,j0CiCjxi+j=1+xk0(i=0kCiCki)xk=1+k0Ck+1xk+1=h(x)1+x h(x)^{2}=1+x \sum_{i, j \geq 0} C_{i} C_{j} x^{i+j}=1+x \sum_{k \geq 0}(\sum_{i=0}^{k} C_{i} C_{k-i}) x^{k}=1+\sum_{k \geq 0} C_{k+1} x^{k+1}=h(x) where we've used the recurrence relation for the Catalan numbers. We now solve for h(x)h(x) with the quadratic equation to obtain h(x)=1/x±1/x24/x2=1±14x2xh(x)=\frac{1 / x \pm \sqrt{1 / x^{2}-4 / x}}{2}=\frac{1 \pm \sqrt{1-4 x}}{2 x}. Note that we must choose the - sign in the ±\pm, since the + would lead to a leading term of 1x\frac{1}{x} for hh (by expanding 14x\sqrt{1-4 x} into a power series). Therefore, we see that f(x)=D(g(x))=D(xh(x))=D(114x2)=114xf(x)=D(g(x))=D(x h(x))=D(\frac{1-\sqrt{1-4 x}}{2})=\frac{1}{\sqrt{1-4 x}} and our answer is hence f(1/5)=5f(1 / 5)=\sqrt{5}.

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.