Maths Olympiad Prep

Library / /5 of 9

Algebra Difficulty 5.5 AIME, harder Find the answer Italy

Problem:

For every positive integer nn we call f(n)f(n) the product of all odd natural numbers less than or equal to 2n+12n+1 (for example f(4)=1⋅3⋅5⋅7⋅9f(4)=1 \cdot 3 \cdot 5 \cdot 7 \cdot 9). We then set g(n)=nf(n)g(n)=\frac{n}{f(n)}. What can be said about the sum S=g(1)+g(2)+⋯+g(30)S=g(1)+g(2)+\cdots+g(30)?

Pick one

Solution

Solution:

The answer is (C)(\mathbf{C}). Let S(m)=g(1)+g(2)+⋯+g(m)S(m)=g(1)+g(2)+\cdots+g(m). Notice that
g(m)=m1⋅3⋯(2m+1)=122m1⋅3⋯(2m+1)=122m+1−11⋅3⋯(2m+1)=12(11⋅3⋯(2m−1)−11⋅3⋯(2m+1)) \begin{aligned} g(m)=\frac{m}{1 \cdot 3 \cdots (2m+1)} &=\frac{1}{2} \frac{2m}{1 \cdot 3 \cdots (2m+1)}=\frac{1}{2} \frac{2m+1-1}{1 \cdot 3 \cdots (2m+1)} \\ &=\frac{1}{2}\left(\frac{1}{1 \cdot 3 \cdots (2m-1)}-\frac{1}{1 \cdot 3 \cdots (2m+1)}\right) \end{aligned}
Calling h(m)=1211⋅3⋯(2m+1)h(m)=\frac{1}{2} \frac{1}{1 \cdot 3 \cdots (2m+1)} we have just obtained that g(m)=h(m−1)−h(m)g(m)=h(m-1)-h(m). Hence S(m)=g(1)+g(2)+g(3)+⋯+g(m−1)+g(m)=h(0)−h(1)+h(1)−h(2)+h(2)−h(3)+⋯+h(m−2)−h(m−1)+h(m−1)−h(m)S(m)=g(1)+g(2)+g(3)+\cdots+g(m-1)+g(m)=h(0)-h(1)+h(1)-h(2)+h(2)-h(3)+\cdots+h(m-2)-h(m-1)+h(m-1)-h(m), that is S(m)=h(0)−h(m)S(m)=h(0)-h(m).

In the particular case,
S(30)=12(1−11⋅3⋯(2⋅30+1)). S(30)=\frac{1}{2}\left(1-\frac{1}{1 \cdot 3 \cdots (2 \cdot 30+1)}\right).
Going back to the general case, S(30)=S<12S(30)=S<\frac{1}{2} since 11⋅3⋯(2⋅30+1)>0\frac{1}{1 \cdot 3 \cdots (2 \cdot 30+1)}>0; moreover 1211⋅3⋯(2⋅30+1)<12⋅61<\frac{1}{2} \frac{1}{1 \cdot 3 \cdots (2 \cdot 30+1)}<\frac{1}{2 \cdot 61}< 0.01 and hence S>0.49S>0.49.

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 translated into English from it; metadata (topic, difficulty) added by this project.