Maths Olympiad Prep

Library / /42 of 62

, 2020

Combinatorics Difficulty 5.7 AIME, harder Find the answer United States

Problem:
Let a1,a2,a3,a_{1}, a_{2}, a_{3}, \ldots be a sequence of positive real numbers that satisfies
n=k(nk)an=15k \sum_{n=k}^{\infty}\binom{n}{k} a_{n}=\frac{1}{5^{k}}
for all positive integers kk. The value of a1a2+a3a4+a_{1}-a_{2}+a_{3}-a_{4}+\cdots can be expressed as ab\frac{a}{b}, where a,ba, b are relatively prime positive integers. Compute 100a+b100 a+b.

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

Solution

Solution:
Let Sk=15kS_{k}=\frac{1}{5^{k}}. In order to get the coefficient of a2a_{2} to be 1-1, we need to have S13S3S_{1}-3 S_{3}. This subtraction makes the coefficient of a3a_{3} become 6-6. Therefore, we need to add 7S37 S_{3} to make the coefficient of a4a_{4} equal to 11. The coefficient of a4a_{4} in S13S3+7S5S_{1}-3 S_{3}+7 S_{5} is 1414, so we must subtract 15S415 S_{4}. We can continue the pattern to get that we want to compute S13S2+7S315S4+31S5S_{1}-3 S_{2}+7 S_{3}-15 S_{4}+31 S_{5}-\cdots. To prove that this alternating sum equals a1a2+a3a4+a_{1}-a_{2}+a_{3}-a_{4}+\cdots, it suffices to show
i=1n((2)i+(1)i)(ni)=(1)i+1 \sum_{i=1}^{n}\left(-(-2)^{i}+(-1)^{i}\right)\binom{n}{i}=(-1)^{i+1}
To see this is true, note that the left hand side equals (12)i+(11)i=(1)i+1-(1-2)^{i}+(1-1)^{i}=(-1)^{i+1} by binomial expansion. (We may rearrange the sums since the positivity of the aia_{i}'s guarantee absolute convergence.) Now, all that is left to do is to compute

i=1(2i1)(1)i15i=i=1(1)i5ii=1(2)i5i=1511525125=542\sum_{i=1}^{\infty} \frac{\left(2^{i}-1\right)(-1)^{i-1}}{5^{i}}=\sum_{i=1}^{\infty} \frac{(-1)^{i}}{5^{i}}-\sum_{i=1}^{\infty} \frac{(-2)^{i}}{5^{i}}=\frac{\frac{-1}{5}}{1-\frac{-1}{5}}-\frac{\frac{-2}{5}}{1-\frac{-2}{5}}=\frac{5}{42}

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.